카카오 코딩테스트 후기
2022. 10. 7. 18:41
진로/취업
구글 부트캠프 전형으로 서류 전형에 합격하여 코딩테스트에 응시할 수 있는 귀한 기회를 얻었다. 사실 코딩테스트 자체를 준비하기 시작한 지 한 달도 되지 않아서 큰 기대가 없었다. 3시간 30분 동안 문제를 풀면서 느낀 바를 정리해보겠다. [1] 문제 해결에 어떤 알고리즘이 필요한지 접근하는 법은 조금 알 것 같다. 문제에서 주어진 데이터를 그래프로 바꾸면 풀 수 있겠구나. 스패닝 그래프를 그리는 식으로 풀면 되겠구나. 등등. 감이 오기 시작했다. 나는 이것만으로도 매우 대단한 성과라고 생각한다. 그것도 짧은 기간 동안 공부해서 얻어낸 직관이다! 희망이 조금 생겼다. 이대로 계속 공부하면 되겠다는 생각이 들었다. [2] 알고리즘을 이해하는 것과 알고리즘을 문제에 맞게 구현하는 건 다른 차원이다. 문제를 보..
그래프 탐색 : BFS(너비 우선 탐색)
2022. 10. 7. 13:19
컴퓨터/알고리즘&자료구조
지난 글에서 DFS(깊이 우선 탐색)에 대해 알아보았다. 오늘은 BFS(너비 우선 탐색)에 대해 알아보자. BFS(너비 우선 탐색) - 임의의 노드에서 시작해 인접 노드를 먼저 탐색한다. - 두 노드 사이의 최단 경로를 알고 싶을 때 실시할 수 있다. (DFS의 경우 모든 그래프를 살펴봐야 할 수 있음) 방문 순서 A → B → C → D → E → F → G → H → I → J → K 큐를 활용한 구현 BFS는 큐를 활용할 수 있다. 큐는 선입선출의 자료구조로, 먼저 들어온 데이터가 먼저 나가게 된다. BFS에서는 지금 시점에서 방문할 수 있는 노드들을 큐에 넣게 된다. A를 출력하면서, A의 인접 노드들을 쌓는다. 그 다음은 먼저 들어갔던 노드가 출력된다. 반복. 먼저 인접리스트 형식으로 그래프를 ..
그래프 탐색 : DFS(깊이 우선 탐색)
2022. 10. 7. 12:34
컴퓨터/알고리즘&자료구조
그래프를 탐색하는 알고리즘에는 DFS(Depth-First Search, 깊이 우선 탐색)과 BFS(Breadth-First Search, 너비 우선 탐색)이 있다. 오늘은 DFS 알고리즘에 대해 알아보자. 그래프를 탐색한다는 것 = 하나의 정점에서 시작하여 그래프의 모든 정점들을 방문하는 것 알아야 할 용어 : 루트 노드 (뿌리), 형제 노드 (같은 레벨에 놓은 노드들), 자식 노드 (어떤 노드 아래에 속한 노드) DFS(깊이 우선 탐색) "한 놈만 팬다" - 임의의 노드에서 시작해 자식 노드를 타고 제일 깊숙히 내려간다. 다시 돌아와 다른 형제 노드의 자식 노드를 타고 제일 깊숙히 내려간다. - DFS가 언제 필요할까? 모든 노드를 방문하고자 할 때 (모든 경우의 수를 구할 때 쓰기에 좋겠다!) - ..
[백준/약점체크] 16916번: 부분문자열
2022. 10. 7. 09:39
컴퓨터/코딩테스트
[문제] 링크: https://www.acmicpc.net/problem/16916 [내 코드] 문제를 해결하기 위해서 KMP 알고리즘을 공부하고 구현했다. 자세한 내용은 이 글을 참고. def LPS(pat, lps): leng = 0 i = 1 while i < len(pat): if pat[i] == pat[leng]: leng += 1 lps[i] = leng i += 1 else: if leng == 0: lps[i] = 0 i += 1 else: leng = lps[leng-1] def KMP(txt, pat): N = len(txt) M = len(pat) lps = [0] * M LPS(pat, lps) i = j = 0 while i < N: if pat[j] == txt[i]: j +=..
ADsP 시험 접수..
2022. 10. 6. 20:42
수학과 통계/통계
통계 공부를 위해 ADsP 시험을 접수했다. 내 5만원 안녕~ 시험은 10월 29일, 3주 남았다. 열심히 해서 합격 후기를 남겨야겠다~
문자열 검색 : LPS와 KMP 알고리즘
2022. 10. 6. 19:16
컴퓨터/알고리즘&자료구조
문자열을 검색하는 문제를 해결하려고 한다. LPS와 KMP 알고리즘에 대해서 알아보자. 문제 'soo'가 'yunsoowoo'의 부분 문자열인지 알고 싶다면? 나이브하게 한 문자씩 대조해가며 알아보는 방법이 있다. 하지만 원본 문자열 yunsoo의 길이가 N이고 탐색 문자열 soo의 길이가 M일 때 시간복잡도가 최악의 경우 $O(NM)$으로 비효율적이다. LPS(Longest Prefix Suffix) 접두사(Prefix)와 접미사(Suffix) LPS 를 위해서는 문자열 맨앞에 있는 접두사와 맨뒤에 있는 접미사가 같은 경우를 먼저 찾아야 한다! 아래 문자열에서 서로 일치하는 접두사와 접미사를 찾아보자. 'AB'라는 문자열이 앞과 뒤에서 반복되는 것을 볼 수 있다. LPS는 서로 동일한 접두사와 접미사가..
최소 신장 트리 구하기 : 프림(Prim's) 알고리즘
2022. 10. 5. 19:04
컴퓨터/알고리즘&자료구조
프림 알고리즘은 최소 신장 트리를 구하는 데 사용한다. (최소 신장 트리를 구하는 또다른 방법으로 크루스칼 알고리즘이 있는데, 이에 대한 글은 여기서 보면 된다.) https://woo-niverse.tistory.com/227 최소 신장 트리 구하기 : 크루스칼(Kruskal) 알고리즘 신장 트리(Spanning Tree) 모든 정점을 연결하되, 사이클이 존재하지 않는 그래프 위 그래프에서 신장 트리를 찾는다면? 아래와 같이 다양한 신장 트리를 만들 수 있다!!! 원본 그래프의 부분 그래프 woo-niverse.tistory.com 프림 알고리즘 - 매순간의 최선의 조건을 선택하는 그리디 알고리즘 - 인접 정점들 중에서 가중치가 가장 작은 간선으로 연결된 정점을 찾는다 - 간선을 중심으로 하는 크루스칼..
[백준/약점체크] 1197번: 최소 스패닝 트리
2022. 10. 5. 18:27
컴퓨터/코딩테스트
[문제] [정답] 최소 신장 트리는 크루스칼 알고리즘이나 프림 알고리즘으로 찾을 수 있다. 크루스칼 알고리즘과 이를 위한 합집합 찾기 알고리즘 그리고 프림 알고리즘에 대한 글을 별도로 작성했으니 참고하면 되겠다. 크루스칼 알고리즘 import sys input = sys.stdin.readline V, E = map(int, input().split()) Vroot = [i for i in range(V+1)] Elist = [] for _ in range(E): Elist.append(list(map(int, input().split()))) Elist.sort(key=lambda x: x[2]) def find(x): if x != Vroot[x]: Vroot[x] = find(Vroot[x]) r..