Cherry & Cherish

기본문제 def binary_search(array, target, start, end) : while start target : end = mid - 1 #중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else : start = mid + 1 ​ return None ​ #n(원소의 개수)과 target(찾고자 하는 문자열)을 입력 받기 n, target = list(map(int, input().split())) #전체 원소 입력받기 array = list(map(int, input().split())) ​ #이진 탐색 수행 결과 출력 result = binary_search(array, target, 0, n-1) if result == None: print("존재하지 않음") else :..

기본문제 from collections import deque ​ def bfs(graph, start, visited): queue = deque([start]) visited[start] = True while queue: v = queue.popleft() print(v, end=' ') for i in graph[v]: if not visited[i]: queue.append(i) visited[i] = True ​ graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] ​ visited = [False] * 9 bfs(graph, 1, visited) 미로탈출 from collections impor..

기본문제 graph = [ [], [2, 3, 8], [1, 7], [1, 4, 5], [3, 5], [3, 4], [7], [2, 6, 8], [1, 7] ] visited = [False] * 9 ​ ​ def dfs(graph, v, visited) : visited[v] = True print(v, end = ' ') for i in graph[v] : if not visited[i] : dfs(graph, i, visited) ​ ​ dfs(graph, 1, visited) 음료수 얼려 먹기 def dfs(x, y): if x = n or y = m: return False if graph[x][y] == 0: graph[x][y] = 1 dfs(x-1, y) dfs(x, y-1) dfs(x+1..

다이나믹 프로그래밍은 동적계획법, DP라고도 한다. 메모리 공간을 더 사용해서 연산 속도를 비약적으로 증가시킬 수 있는 대표적인 방법 중 하나다. 다이나믹 프로그래밍은 구현의 특별한 코드가 있다기 보다는, 두 가지 방식(탑다운, 바텀업)이 존재한다. 1. 다이나믹 프로그래밍 사용 문제 DP 알고리즘을 적용해 풀어야 하는 문제는 대표적으로 피보나치 수열을 예시로 들 수 있다. 피보나치 수열은 이전 두 항의 합을 현재의 항으로 다시 설정한다. 다시 말해, 점화식으로 문제를 풀어야 하는 것이다. 피보나치 수열은 손쉽게 재귀 문제로 풀 수 있는데, 이렇게 되면 주어진 숫자 n이 커질수록, 기하급수적으로 수행시간이 늘어나게 된다. 따라서 이러한 문제는 다이나믹 프로그래밍으로 해결해야 한다. 2. 다이나믹 프로그래..

그래프 알고리즘은 코딩 테스트 단골 출제 문제는 아니다. 하지만 꼭 알아야 하는 알고리즘 중 하나라고 할 수 있다. 그래프 알고리즘에 대한 팁은 “서로 다른 객체가 연결되어 있다(여러 개의 도시가 연결되어 있다)”라는 표현이 들어가면 대체로 그래프 알고리즘을 활용해야 하는 문제일 가능성이 높다. 또, 트리 자료구조는 다양한 알고리즘에서 사용되므로 꼭 암기해야 한다. 트리 자료구조는 부모에서 자식으로 내려오는 계층적인 모델에 속한다. 최소힙은 항상 부모 노드가 자식 노드보다 크기가 작은 자료구조로서 트리 자료구조에 속한다. 그래프의 구현 방법은 2가지 방식이 존재한다. 인접 행렬 : 2차원 배열을 사용하는 방식 인접 리스트 : 리스트를 사용하는 방식 2가지 모두 사용된다. 1. 서로소 집합 1-1. 서로소..

최단경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘이다. 보통 그래프를 이용해서 표현하고, 각 지점은 그래프에서 노드로 표현되고 지점간 연결된 도로는 그래프에서 간선으로 표현된다. ‘한 지점에서 특정 지점까지의 최단 경로를 구해야하는 경우’, ‘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우’ 등 다양한 사례가 존재한다. 일반적으로 사용하는 최단거리 알고리즘은 ‘다익스트라 알고리즘’, ‘플로이드 워셜 알고리즘’, ‘벨만 포드 알고리즘’ 등 여러 가지가 존재한다. 그러나 코딩 테스트에서 가장 많이 등장하는 유형은 ‘다익스트라’, ‘플로이드 워셜’ 알고리즘이다. 최단 경로 알고리즘은 DP와 그리디가 그대로 적용된다는 특징이 있다. 따라서, 그리디와 DP 유형의 하나로 보는 경우도 있다..

문제 : 서로 다른 정수 N개가 주어지면 정렬한 상태로 리스트 A에 저장한다. 그런 다음 리스트 B에 저장된 M개의 정수에 대해 A에 들어있는 수인지 이진 탐색을 통해 확인하려고 한다. 전체 탐색 구간의 시작과 끝 인덱스를 l과 r이라고 하면, 중심 원소의 인덱스 m=(l+r)//2 이고, 이진 탐색의 왼쪽 구간은 l부터 m-1, 오른쪽 구간은 m+1부터 r이 된다. 이때 B에 속한 어떤 수가 A에 들어있으면서, 동시에 탐색 과정에서 양쪽구간을 번갈아 선택하게 되는 숫자의 개수를 알아보려고 한다. 다음은 10개의 정수가 저장된 리스트 A에서 이진 탐색으로 6을 찾는 예이다. 6은 탐색 과정에서 양쪽을 번갈아 가며 선택하게 된다. 예를 들어 10을 찾는 경우 오른쪽-오른쪽 구간을 선택하므로 조건에 맞지 않..

문제 : 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, ..