기록

문제 보기 [사용한 알고리즘] 슬라이딩 윈도우 (Sliding Window) [설명] 사실 문제 봤을 때 슬라이딩 윈도우 알고리즘이 떠오르지 않았다. 뭔가 풀어본 문제인데 '어떻게 풀었지?'를 5번 이상 반복했다. 결국 집합(set)과 left, right 인덱스 두 개를 활용하도록 나만의 설계를 작성한 후 코드를 구현하였다. 하지만, 구현 후 코드를 다시 확인해보니 나만의 설계가 아니라 그냥 슬라이딩 윈도우 그 자체였다. 그래도 약 2년 전에 열심히 코딩 테스트 준비하였던 경험들이 아직 머릿속에 조금은 남아있는 듯하다. 알고리즘은 크게 어렵지 않다. 문자열 s의 길이가 2미만인 경우 문자열 s의 길이를 반환한다. 문자열 s의 길이가 2이상인 경우 중복 없는 최대 부분 문자열을 찾기 위해서 반복문을 수행..

문제 보기 [사용한 알고리즘] x [설명] 연결 리스트의 개념을 이해하고 있으면 크게 어렵지 않은 문제라고 생각한다. l1, l2 각 값을 더한 후 해당 값을 역순으로 저장하는 연결 리스트를 구현하면 된다. 1. l1 연결리스트 값을 추출한다. 2. l2 연결리스트 값을 추출한다. 3. 추출한 두 값을 더한다. 4. 더한 값을 역순으로 연결 리스트에 저장한다. [코드] # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def addTwoNumbers(self, l1: Optional[ListNo..

문제 보기 [사용한 알고리즘] x [설명] nums 리스트에 있는 원소 중 두 원소의 합이 target 이 되는 경우는 1가지가 존재한다. 따라서, 2중 반복문을 수행하면 쉽게 두 원소를 찾을 수 있다. [코드] class Solution: def twoSum(self, nums: List[int], target: int) -> List[int]: for i in range(len(nums)): for j in range(i + 1, len(nums)): if nums[i] + nums[j] == target: return [i, j]

문제 보기 [사용한 알고리즘] - 정렬 [알고리즘] - 내부 라이브러리 sort, set 사용 [코드] import sys if __name__ == "__main__": n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) # 중복 제거 arr = list(set(arr)) # 정렬 arr.sort() print(" ".join(map(str, arr)))

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색), 브루트 포스 [알고리즘] 1. BFS 알고리즘을 사용하여 평면상에 존재하는 모든 섬에 해당하는 좌표를 구합니다. - island[0] : 0번 섬에 해당하는 좌표값 저장 2. 각 섬들 사이에 발생할 수 있는 모든 거리를 탐색하여 최소 거리 값을 구합니다. 3. 최소 거리 값 - 1을 출력합니다. [코드] from collections import deque import sys dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(start): q = deque() result = list() q.append((start[0], start[1])) result.append((start[0], start[1])) maps[..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색) [알고리즘] 1. 로봇의 현재 위치와 바라보는 방향을 큐에 삽입합니다. 2. 현재 위치와 바라보는 방향을 기준으로 명령 1(Go k)을 수행합니다. - 1, 2, 3칸 이동이 가능한지 확인하고 이동이 가능하다면 이동한 위치와 현재 방향을 큐에 삽입합니다. 3. 현재 위치와 바라보는 방향을 기준으로 명령 2(Turn dir)를 수행합니다. - 동, 서, 남, 북 중 현재 방향을 제외한 방향 중 방문하지 않은 곳이 있다면 방향을 바꾼 후 큐에 삽입합니다. 4. 위 과정을 도착 지점을 찾을 때까지 수행합니다. [코드] from collections import deque import sys dx = [None, 0, 0, 1, -1] dy = [None,..

문제 보기 [사용한 알고리즘] 플로이드-워셜(Floyld-Warshall) [알고리즘] 1. 입력값을 이용해 무방향 그래프를 구현합니다. 2. 플로이드-워셜 알고리즘을 통해 각 회원들이 모든 회원가 친구가 되기 위한 최소 단계를 구합니다. 3. 각 회원 중 모든 회원가 친구가 되기 위한 최소 점수를 가진 회원들을 찾습니다. 4. 회장 후보의 점수와 후보의 수를 출력하고, 다음 줄에 회장 후보를 오름차순으로 모두 출력합니다. [코드] import sys INF = 1e10 if __name__ == "__main__": n = int(sys.stdin.readline()) graph = [[INF for _ in range(n + 1)] for _ in range(n + 1)] for i in range(..

문제 보기 [사용한 알고리즘] 위상 정렬(Topological) [알고리즘] 1. 선행 관계가 없는 작업을 큐에 삽입합니다. 2. 큐에 있는 원소를 하나씩 꺼내어 연결된 선행 관계를 제거합니다. - 선행 관계를 제거한 결과 해당 작업이 더 이상 선행 관계가 없으면 큐에 삽입합니다. - 최대 시간 저장 배열에 저장된 시간과 현재까지 사용한 시간 중 최댓값을 저장합니다. 3. 모든 선행 관계가 사라질 때까지 위 과정을 반복합니다. ※ 최대 시간 저장 배열을 따로 두는 이유 예를 들어 3번 작업이 1번, 2번 작업과 선행 관계가 있을 때 1번 + 3번, 1번 + 2번 작업 중 최댓값이 3번 작업 처리 시간입니다. 만약 최대 시간 저장 배열을 따로 두지 않으면 가장 마지막에 계산한 값이 최종 시간이 되기 때문에..

문제 보기 [사용한 알고리즘] BFS(너비 우선 탐색) [알고리즘] 1. 빨간 구슬과 파란색 구슬의 위치를 찾습니다. 2. 현재 구슬 위치에서 상, 하, 좌, 우로 움직일 수 있는 모든 상황을 탐색합니다. - 파란색이 구멍에 빠지는 경우 무시합니다. - 빨간색만 구멍에 빠지면 1을 리턴합니다. - 모두 구멍에 빠지지 않으면 움직인 위치를 큐에 삽입하여 계속 탐색할 수 있도록 합니다. 3. 위 과정을 10번 이하로 움직일 때까지 반복합니다. [코드] from collections import deque import sys dx = [-1, 1, 0, 0] dy = [0, 0, -1, 1] def bfs(red_x, red_y, blue_x, blue_y): q = deque() q.append((red_x..

문제 보기 [사용한 알고리즘] 다익스트라, 이분 탐색 [알고리즘] 알고리즘 전체 과정을 대략적으로 말씀드리면 이분 탐색을 통해 케이블 기준 가격을 정한 후 다익스트라를 수행함으로써 1번과 N번 컴퓨터를 이을 수 있는지 판단합니다. 세부적인 과정은 다음과 같습니다. 1. 이분 탐색을 수행하기 위해 left, right 값을 0과 1000001로 초기화합니다. 2. left와 right를 통해 mid 값을 구한 후 다익스트라를 수행합니다. 3. 다익스트라 수행은 기존의 다익스트라와 달리 최소 거리를 구하는 것이 아니라 1번과 N번을 연결할 수 있는지 구하는 것이 핵심입니다. 따라서 거리 값은 mid 값을 넘긴 케이블의 수입니다. - 만약 distance[n] 값이 k보다 크면 공짜로 제공하는 케이블선 k개로..