관심이 가는 개발 보물창고

미루고 미뤘던 자료구조, 이번 기회에 트라이에 대해서 공부하게 됐다. 내가 여러 사이트를 검색하면서 공부한 것을 정리했다. 트라이(Trie) 자료구조란? 쉽게 생각해서 문자열을 빠르게 탐색할 수 있는 자료구조다. 얼마나 빠르길래 이렇게 따로 명칭까지 있는 것일까? 결론부터 말하자면 M이 최대 문자열의 길이라고 했을 때, O(M)만에 검색할 수 있다. 트라이를 표현하는 특징은 여러 가지가 있다. 1) 집합에 포함된 문자열의 접두사들에 대응되는 노드들이 서로 연결된 트리구조 2) 루트에서부터 내려가면서 만나는 글자들을 모으면 찾고자 하는 문자열의 접두사를 얻을 수 있다. 3) 문자열 트리 구조 트라이 작동 원리 트라이는 주어진 문자열을 이루고 있는 문자를 앞에서부터 하나씩 노드를 생성해가면서 만들어진다. 이..

위상 정렬이란? 사전 작업, 선행 작업 등 순서가 정해진 작업을 차례대로 수행해야 할 때, 그 순서를 나열한 것. 사이클이 존재하지 않는 방향 그래프의 모든 노드를 순서에 거스르지 않도록 나열한 것. '스타크래프트' 게임을 생각하면 쉽게 이해할 수 있다. '서플', '배럭'을 짓기 위해서는 선행 작업으로 '커맨트 센터'를 먼저 만들어야 한다. 이 순서를 어기게 되면, 영원히 '서플'과 '배럭'을 건설할 수 없게 된다. 이렇듯, 선행이 필수인 것부터 나열해서 정렬하는 것이 위상 정렬이다. 위상 정렬의 동작 과정 진입 차수가 0인 노드 먼저 큐에 넣는다. 큐가 빌 때까지 반복한다. 큐에서 원소를 꺼내고, 그 노드에서 출발하는 간선들을 모두 제거한다. 이때 새롭게 진입 차수가 0인 노드들은 큐에 넣어준다. 큐..

간단하게 행렬을 표현하는 방법에서 코딩 테스트에서 자주 나오는 행렬에 대한 몇 가지 구현 방법을 공부해보자. 행렬의 표현 행렬의 표현은 자료구조에서 보통 2차원 배열로 표현하게 된다. 만약에 큐브라면 3차원 배열로 구현하면 된다. //2 x 2 행렬 int a[2][2] = { {1, 1}, {1, 1} }; //3 x 3 행렬 int b[3][3] = { {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }; // 2 x 5 행렬 int c[2][5] = { {1, 2}, {3, 4}, {5, 6}, {7, 8}, {9, 10} }; 행렬의 곱셈 "A의 행렬 x B의 행렬" 를 물어보는 문제가 간간히 등장한다. 이럴 때 행렬의 곱셈을 구현하는 방법을 따로 연습하지 않았더라면 꽤나 시간을 잡아먹을..

이번에는 최단 경로 알고리즘 중 하나인 플로이드 워셜에 대해서 공부해보자. 모든 지점에서 다른 모든 지점까지의 최단경로를 모두 구해주는 알고리즘에 대해서 배워보자. 플로이드 워셜 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해주는 알고리즘이다. 쉽게 설명하면, A 노드에서 B 노드로 가는 최단 경로가 A -> B (한 번에 가는 것) A -> K -> B (어떤 노드를 거쳐서 가는 것) 가 있을 텐데 이중 우리는 더 짧은 경로를 원하므로 min(A -> B, A -> K -> B)를 갱신하면 된다. 단계마다 거쳐 가는 노드를 기준으로 더 짧은 경로를 선택하며 반복하는 것이다. 이때 단계마다 비용이 O(N^2)이다. 거쳐 가는 노드를 기준으로 시작 노드에서 도착 노드까지 모든 경로를 검사하는데 ..

오늘은 투 포인터 알고리즘에 대해서 공부해보자. 이 투 포인터를 모르면 코테에서 낭패를 볼 수 있다?라고 말할 정도로 생각보다 중요한 알고리즘 테크닉이다. 남들도 다 아는 알고리즘을 나만 몰라서 틀린다.. 이거 매우 억울한 일이다. 얼른 공부해서 습득하자! 투 포인터 (Two pointer) 이름과 똑같이 두 개의 포인터를 가지고 문제를 해결하는 알고리즘이다. 문제를 풀다보면 배열의 길이가 2중 포문으로 해결을 할 수 없을 정도로 큰 배열이 주어지게 됐을 때, 구간의 합이 M인 곳이 몇 개 인지? 물어보는 문제에서는 완전 탐색으로는 시간 초과로 해결할 수 없는 문제가 있다. 대표적으로 BOJ2003 수들의 합2 문제와 BOJ2470 두 용액 문제다. 이런 문제들의 특징은 입력 크기가 너무 커서 완전 탐색..

이번에는 최단 경로 알고리즘 하면 떠오르는 알고리즘 중 하나인 다익스트라 알고리즘에 대해서 정리해보자. 다익스트라 알고리즘 (Dijkstra Algorithm) 다익스트라 알고리즘의 정의부터 보자. 하나의 정점에서 출발해서 다른 노드들로 가는 각각의 최단 경로를 모두 구해주는 알고리즘이다. 용어로는 '단일 출발 최단 경로' 라고도 한다. 또, '단일 도착 최단 경로' 도 뒤집으면 똑같은 말이기도 하다. 모든 정점에서 출발해서 어떤 하나의 정점까지의 최단 경로를 찾는 문제로 뒤집어서 생각하면 다익스트라와 똑같기 때문이다. 다만, 음의 간선에서는 사용할 수 없다. 이 때는 벨만-포드 알고리즘을 사용해야 한다. (아직 안 배웠다..) 사실 다익스트라 알고리즘 단계별 그림은 다른 블로그들의 설명도 너무 좋아서 ..

오늘은 최단 경로 알고리즘에 대해서 간단하게 개요를 정리하자. 최단 경로란? 그래프 상에서 가장 짧은 경로를 찾는 경로, 가중치 그래프에서는 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제다. 그런데, 최단 경로라고 해도 문제마다 다르다. 어떤 경우들이 있을까? 단일 출발 최단 경로 : 어떤 하나의 정점에서 출발하여 나머지 모든 정점까지의 최단 경로 단일 도착 최단 경로 : 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로 (뒤집어서 생각하면 단일 출발 최단 경로다) 단일 쌍 최단 경로 : 모든 정점에서 모든 정점까지의 최단 경로 최단 경로 알고리즘 최단 경로 문제가 나오게 되면 이를 해결할 알고리즘들이 있다. BFS(완전 탐색) 가중치가 없거나 가중치가 모두 동일한 경우(미로 탐색 문제)에서..

최근 코테에서 자주 나오는 부분이 모듈러 연산, 최대 공약수, 소수다. 자주 풀어보지 않기 때문에 막상 나오면 헤매는 경우가 잦기 때문에 오늘 정리하려고 한다. 아래의 정리는 백준의 강의를 듣고 감명받은 점들과 나의 생각을 정리해서 적어놓았다. 모듈러 연산(나머지 연산, modular) 말 자체가 처음에는 와닿지 않는 용어지만 % 기호를 보면 한 번에 이해하기 쉽다. 10 % 7 => 3 6 % 7 => 6 0 % 7 => 0 7 % 7 => 0 어떤 수를 7로 모듈러 연산한다고 하면 나올 수 있는 경우의 수는 0 ~ 6 다. 아무리 큰 수가 와도 저 안에 머무른다는 소리다. 응용 어떤 물고기가 (1,1) 에서 5 x 5 격자 안에서 움직인다고 할 때 5의 속력으로 동쪽으로 이동한다고 하면? (1,1) ..

백트래킹(Backtracking) 알고리즘을 어느 정도 공부하게 되면 백트래킹이라는 용어를 많이 들어봤을 것이다. 가끔 백트래킹이랑 완전 탐색을 같은 용어로 사용하게 되는데 오늘 확실히 정리해서 이해하도록 하자. 많은 블로그들을 검색하면서 공부했지만 이게 가장 나에게는 이해가 되는 정의였다. 해를 찾는 도중 다음의 경우가 해가 아니라면 되돌아가서 다시 해를 구하는 기법 무슨 말이냐면 분명 이 길로 가면 막히는 곳이 나오는데?라고 생각되면 다른 곳으로 방향을 트는 것이다. 이미 그 길은 내가 끝까지 가보지 않더라도 막힌 길을 알기 때문이다. DFS 기법으로 하게 되면 막힌 곳을 알더라도 끝까지 가서 확인한다. -무식한 방법- 백트래킹 기법으로 하게 되면 "아 이 길은 막힌 곳이니까 다른 곳으로 가자." -..

파라메트릭 서치 생각보다 받아들이는데 어려운 개념이다. 이 알고리즘은 최적화 문제를 결정 문제로 바꾸는 기법이다. 조건을 만족하면서도 최대한 많이 가져갈 수 있는 방법을 찾는 느낌?? 혹은 조건을 만족하면서도 최대한 적게 가져갈 수 있는 방법을 찾는 느낌이라고 생각하면 좋다. 예시를 들어보면 아래의 문제를 인용해서 생각해보자. BOJ2110 공유기 설치 대표적인 파라메트릭 서치 문제다. 공유기 C개를 설치해야 하는데 두 공유기 사이의 거리를 최대한으로 하려면 어느 정도쯤에 설치해야 할까?라는 문제다. (아래의 예시는 위의 문제 스포가 될 수 있어서 임의로 그냥 생각한 풀이입니다.) 예를 들어보자. 공유기 3개를 설치해야 하는데 만약에 내가 두 공유기 사이의 거리를 2로 설치한다고 가정했을 때, 2씩 공유..