취업 준비 및 일상

바킹독님이 트라이 강의를 올려서 다시 공부했습니다. 트라이 문제를 좀 풀어본 적이 있어서 복습일 줄 알았는데, 트라이 구현 방식이 달라서 좀 새로웠네요. 이 방법을 알았다면 현대모비스 알고리즘 경진대회에 나온 트라이 쓰는 2문제에서 더 높은 점수를 받을 수 있지 않았을까? 싶기도 합니다. 기존에 트라이를 블로그를 통해 공부했을 때, 다들 구현 방법으로 Trie class를 만들어 사용하는 방법을 제시하더라고요. 그리고 Trie내의 자식 노드를 구현을 1) Map으로 하는 방법, 2) 적당한 크기의 Trie배열을 선언하는 방법으로 나눌 수 있었습니다. 위 강의에서는 처음부터 2차원 배열을 크게 선언한 다음 사용하라고 했는데, 처음 보니까 조금 생소하기도 하고 비효율적이다는 느낌(되게 안쓰는 칸이 많아요)을..

링크: 설명 / 문제집 처음 KMP 알고리즘을 접했을 땐, 이해하는데 1시간 반이 걸렸습니다. 그래도 한번 공부해서 그런지, 오랜만에 봐도 이해하는데 30분밖에(?) 걸리지 않았네요. 되돌아서면 헷갈리는 알고리즘입니다. 문제 풀이 백준 16916번 부분 문자열, 백준 16172번 나는 친구가 적다 (Large) - 기본적인 KMP 활용 문제입니다. Python에서 in 연산이 O(N)이라, 코테에서 이런 유형의 문제가 나오면 python 및 C++의 library를 활용하는 것이 낫습니다. 백준 1786번 찾기 - 기본 KMP 문제인데, 위 두 문제와 다르게 '부분 문자열이 몇 번 나왔으며, 시작 위치가 어디인지'를 구해야 합니다. KMP 알고리즘을 활용해서 풀었다면 위 문제에서 '부분 문자열을 찾은 순..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 개념 최단 경로 알고리즘 중 다익스트라는 음의 가중치를 갖는 간선, 플로이드는 음의 사이클을 가지면 제대로 된 답을 내지 않을 수 습니다. 구체적으로, 다익스트라는 '음의 가중치를 갖는 간선이 있을 경우 현재 갈 수 있는 정점 중에서 가장 가까운 정점까지의 거리를 확정지을 수 없기'에, 1) 음의 사이클이 있을 경우 무한 루프가 발생하며..