알고리즘 문제풀이210 [프로그래머스] 경주로 건설 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 초기에 DFS 를 재귀로 탐색하여 모든 경우를 탐색을 시도하였으나, 시간초과로 통과하지 못하였습니다. 그래서 BFS 탐색을 하며 DP를 이용하는 방식으로 접근하였습니다. 2) 알고리즘 BFS DP 3) 풀이 코드 사용 언어 - Python from collections import deque def solution(board): dr = [-1, 0, 1, 0] # 상 우 하 좌 dc = [0, 1, 0, -1] N = len(board) # 보드판의 길이 cost = [[1e10] * N for _ in range(N)] # 각 좌표로 이동하는데 발생하는 비용 def BFS(): q = deque([(0, 0, 0, -1)]) # 행 열 좌표, 해당.. 2022. 2. 21. [프로그래머스] 합승 택시 요금 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 최소 요금을 구해야 하므로 다익스트라를 이용하였습니다. 출발지에서 각 지점으로 최소 요금으로 갈 수 있는 값을 구하였습니다. 그 이후 각 지점에서 a, b 지점으로 이동하는 요금을 구하여 비교하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import heapq def solution(n, s, a, b, fares): answer = 0 # 최소 요금 linked = [[] for _ in range(n+1)] # 도로 정보들 start_distance = [] # 시작 지점에서 각 지점으로 이동하는데 필요한 요금 for fare in fares: # 양방향으로 도로 정보를 저장함 linked[fare[0]].appe.. 2022. 2. 20. [프로그래머스] 셔틀버스 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 사람들이 기다리기 시작할떄 시간을 분으로 변경하여버스 시간이 올때마다 몇명의 대기 사람이 있는지 구했습니다. 무조건 마지막 버스에 탑승하면 되므로, 마지막 버스의 마지막으로 탑승한 사람보다 먼저 도착하면 되도록 접근하였습니다. 2) 알고리즘 문자열 구현 3) 풀이 코드 사용 언어 - Python def solution(n, t, m, timetable): answer = 0 bus = 540 # 버스의 첫 시작 시간 (분) waiting = 0 # 기다리는 사람의 수 time_line = [] # 사람들이 기다리기 시작하는 시간 리스트 for time in timetable: # 사람들 줄서는 시간들을 분으로 계산하여 분으로 바꾸어 저장 minute .. 2022. 2. 19. [프로그래머스] 추석 트래픽 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 입력으로 주어진 문자열을 가공하여 요청 시작 시간과 응답하는 시간을 ms 단위로 변환시켰습니다. 딕셔너리 변수를 이용하여 키값을 ms 시간으로 하여 처리하는 요청의 최대 개수를 구하였습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - Python def solution(lines): answer = 0 # 초당 최대 처리량 cnt = 0 # 특정 시간대 처리량 time_line = {} # 시간 테이블 - 키: 시간(ms) / 값: 시작 또는 완료 여부 (-1, 1) for line in lines: # 로그 데이터 date, time, duration = line.split(' ') # 날짜, 시간, 처리 시간 end_ms = int(tim.. 2022. 2. 18. [프로그래머스] 표 편집 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 표의 각 행을 가르키는 커서를 이리저리 움직이며 행을 삭제하거나, 삭제한 행을 원위치로 복구를 하게 되는데, 단순 리스트 구현시 각 요소들의 이동이 무수히 많아질 수 있으므로, 이중연결 리스트를 이용하였습니다. 2) 알고리즘 이중연결 리스트 3) 풀이 코드 사용 언어 - Python def solution(n, k, cmds): answer = [] # 행 삭제 여부를 저장할 정답 리스트 history = [] # 삭제된 행이 저장될 스택 table = [] # 연결 리스트 def create_item(idx): # 연결 리스트 초기 생성 item = [[idx-1, -1], idx] # [이전 인덱스, 이후 인덱스], 현재 인덱스(데이터) if id.. 2022. 2. 17. [프로그래머스] 불량 사용자 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 불량 사용자를 응모자 아이디와 비교하여 제재 가능한 아이디 목록을 만들어 주었습니다. 이때 좀 더 빠른 탐색을 위해, 응모자 아이디를 길이순, 알파벳순으로 정렬하여 앞에서 탐색하였고, 길이를 초과하면 탐색을 멈추도록 하였습니다. 재귀를 이용하여 제재 아이디를 만들 수 있는 경우를 구해주었습니다. 2) 알고리즘 문자열 3) 풀이 코드 사용 언어 - Python def solution(user_id, banned_id): answer = set() # 제재 아이디 가능한 경우들 집합 user_id = list(sorted(user_id, key=lambda x: (len(x), x))) # 유저 아이디를 길이순, 알파벳순으로 정렬 cases = [[] f.. 2022. 2. 16. [프로그래머스] 보석 쇼핑 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 하나의 배열에서 조건을 만족하는 구간을 구해야 했으므로 투포인터로 접근하였습니다. 시작점을 기준으로 하여, 조건을 찾은 후에 시작점을 한칸만 이동하여 다음 구간을 찾게 되면 시간초과 문제가 발생할것으로 생각했습니다. 또한, 짧은 구간이 여러개일 경우 시작 진열대 번호가 작은 구간을 출력하여야 했으므로 배열의 오른쪽에서 왼쪽으로 탐색을 시도하였습니다. 우선, 오른쪽 포인터를 기준으로 하여 왼쪽 포인터를 이동 시키며 조건을 만족하는 구간을 구했습니다. 그리고 왼쪽 포인터를 기준으로 오른쪽 방향으로 진행하여 더 짧은 구간이 존재하는지 탐색하였습니다. 구간의 길이를 구했다면, 다음 탐색을 위해 오른쪽 포인터보다 한칸 앞에서 기준을 잡아 탐색하였습니다. 2) .. 2022. 2. 15. [프로그래머스] 자물쇠와 열쇠 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 키가 회전이 가능하므로 회전했을때 모습을 구하였습니다. 키를 자물쇠 가장 오른쪽 하단부터 한칸씩 이동하며 열수 있는지 없는지 판별하였습니다. 2) 알고리즘 구현 3) 풀이 코드 사용 언어 - Python def solution(key, lock): K, L = len(key), len(lock) # 키와 자물쇠의 한변의 길이 keys = [[[0] * K for _ in range(K)] for _ in range(4)] # 회전한 키의 모양들을 담을 리스트 for i in range(K): for j in range(K): keys[0][i][j] = key[i][j] # 정방향 keys[1][i][j] = key[K-1-j][i] # 90도 회전 .. 2022. 2. 14. [프로그래머스] 길 찾기 게임 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 주어진 노드의 정보들을 이용하여 트리를 만들어내려 하였습니다. 그러나 트리를 만드는 과정에 다소 조건이 많았기에, 트리를 생성하지 않고 이진트리의 순회하는 방식의 특징을 이용하였습니다. 순회를 할때 현재 노드를 중심으로 하여 왼쪽 자식 노드와 오른쪽 자식 노드를 구하여 순회를 하였습니다. 2) 알고리즘 트리 3) 풀이 코드 사용 언어 - Python import sys sys.setrecursionlimit(10000) def solution(nodeinfo): answer = [[], []] # 전위 순회, 후위 순회 nodeinfo = list(sorted(enumerate(nodeinfo, start=1), key=lambda x: (x[1][1.. 2022. 2. 13. [백준] 13549 숨바꼭질 3 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 수빈이가 동생의 위치로 이동하는데 걸리는 최소의 시간을 구해야 하므로 다익스트라를 이용하였습니다. 2) 알고리즘 다익스트라 3) 풀이 코드 사용 언어 - Python import sys import heapq sys.stdin = open('input.txt') def solution(start): heap = [(0, start)] # 처음에 시작은 0초, 처음에 출발하는 수빈이 위치 while heap: if road[K] != -1: # 동생한테 도착했다면 종료 return node = heapq.heappop(heap) if 0 2022. 2. 12. [백준] 1701 Cubeditor 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 KMP 알고리즘으로 접근하여 주어진 문자열에서 가능한 패턴을 추출하여 2번 이상 포함되는 경우를 반환하도록 접근하였습니다. 그러나 제한시간을 초과하여 KMP 알고리즘을 이용할때 사용하는 접두사와 접미사가 일치하는 길이를 저장하는 테이블로 접근하였습니다. 이 테이블은 접두사와 접미사가 어느 길이로 일치하는지 저장하는 테이블로, 특정 패턴(접두사)이 문자열의 가장 뒤쪽(접미사)와 일치하므로 문장에 패턴이 두번 이상 나오게 되어 문제의 조건에 부합합니다. 그리하여 테이블의 값에서 가장 큰 값을 반환하도록 하였습니다. 2) 알고리즘 KMP 3) 풀이 코드 사용 언어 - Python import sys sys.stdin = open('input.txt') de.. 2022. 2. 11. [프로그래머스] 방금그곡 📖 문제 🧑🏻💻 풀이 과정 1) 문제 이해 및 접근 특정 패턴이 여러 문자들 중 포함되는지 여부를 판별해야 하므로 KMP 알고리즘으로 접근하였습니다. 2) 알고리즘 KMP 3) 풀이 코드 사용 언어 - Python def solution(m, musicinfos): def separate(s): # 문자열 음을 리스트 형태로 나누어주는 함수 result = [] # 리스트로 변형된 음 for c in s: if c == '#': # 현재 인덱스가 # 이라면, 이전에 기록한 음에 # 이 붙어야하므로 result.append(f'{result.pop()}{c}') # 마지막 요소를 꺼낸 후 뒤에 붙여서 다시 추가 else: # 현재 문자가 # 이 아니라면 반환할 리스트에 항목 추가 result.append.. 2022. 2. 10. 이전 1 ··· 8 9 10 11 12 13 14 ··· 18 다음
