공부/PS

[BOJ 1949] 우수 마을 (Gold II)

1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 위 문제를 풀고 나서 되돌아보며 부족했던 부분을 채우고자 합니다. 저의 풀이와 다른 사람들의 풀이를 보고 느낀 점을 서술합니다. 나의 풀이 처음에 문제를 대충 읽었다가 주어지는 게 그냥 그래프인 줄 알았는데, 간선 입력이 N-1개 주어진다는 걸 보고 문제를 다시 읽어 보니 트리인 걸 알아차렸다. 문제를 보면 일단 어디가 루트 노드인지 알 수 없기 때문에 기본적으로 1번 노드를 루트 노드로 하여금 트리를 형성하고, 트리를 순회하면서 값을 계산하도록 한다...

백준 64일 스트릭 회고

오늘을 기점으로 백준에서 제공하는 문제들을 64일 연속으로 풀게 된 날이다. 백준 문제들의 난이도를 알려 주는 solved.ac를 이용하면 매 2^N일 스트릭을 기록할 때마다 배지를 주는데, 64일 배지를 받은 기념으로 지금까지 풀어온 감상에 대해 얘기하려 한다. PS에 제대로 관심을 가직 시작한 것은 2021년으로, 개인 사정으로 휴학을 했을 때 뭔가 공부를 하는 게 낫지 않을까 싶어서 시작했던 것이 PS였다. 지금 돌이켜보면 그때 웹 개발이나 열심히 했으면 좋았을걸 싶긴 하지만 웹에 대해서는 좀 더 나중에 흥미를 붙이게 되었기 때문에... 책과 함께 시작하기 사실, PS를 시작했을 때부터 백준에서 문제를 푼 것은 아니다. 정확히 말하자면, 가장 처음에 남들도 하니까 따라서 백준 계정을 만들어서 고작 ..

PS에 편한 C++ 문법

나는 C++로 PS를 하는데, 참고했던 책도 그렇게 최신 책은 아니고 컴파일 환경도 C++14였어서 이런저런 화려한 문법들을 쓰지 않고 PS를 진행했다. 그런데, 다른 사람들의 코드를 읽어 보니 각종 편리한 문법들을 많이 사용하고 있는 것 같아서 나름 사람들 어깨 너머로 배운 내용들이나 편법(?)등을 정리해 놓고자 한다. 다른 사람들의 PS 코드야 예전부터 가끔 읽었지만, 그때는 딱히 내가 저 사람들이 쓰는 문법을 따라 할 필요가 없었다고 느꼈다. 그런데 언젠가부터 이런 마인드를 바꾸기로 결심했는데, 바로 취업을 위한 코딩 테스트를 준비할 때였다. 평소에 PS를 할 때에는 한 문제에 수십 분부터 몇 시간, 며칠을 매달리든 내 자유였지만 코딩 테스트는 그 시간이 정해져 있기 때문에 효율적인 알고리즘을 빠르..

최단 거리 알고리즘의 이해

최단 거리 알고리즘에 대해 정리해 본다. 책을 참고했음을 밝힌다. 최단 거리 알고리즘은 말 그대로 시작 지점에서 도착 지점까지 이동하는 경로 중 가장 짧은 경로의 거리를 구하는 알고리즘이다. 장소와 길은 그래프로 나타내기 때문에, 그래프 이론과 밀접한 관련이 있다. 1. 다익스트라 알고리즘 (Dijkstra's algorithm) 가장 스탠다드한 최단 거리 알고리즘이다. 시작 정점을 지정하면 해당 정점에서 출발해서 다른 정점으로 도착할 때의 최단 거리를 알 수 있다. 길찾기 알고리즘을 적용하는 가장 흔한 예는 가중치(weight)가 있는 weighted graph이므로, 나중에 발견된 정점이 최단 거리일 수 있다. 즉, 단순한 BFS로는 최단 거리를 찾지 못하는 경우가 수없이 많다는 것이다. 다르게 말하..

KMP 알고리즘

KMP 알고리즘에 대해 공부하다가 헷갈리는 것들이 있어 자세히 정리했다. 책을 참고했음을 밝힌다. 먼저, KMP 알고리즘이란 문자열 검색을 보다 효율적으로 실행하는 알고리즘으로, 전체 문자열의 모든 부분에서 문자열 비교를 행하지 않으면서 대상 문자열을 빠르게 검색해 낸다. 전체 문자열이 짧으면 몰라도, 수천 수만 줄로 이루어진 문서에서 단어를 검색하는 작업은 모든 글자에서 하나하나 단어를 확인하기에는 무리가 있을 수 있다. 그래서 우리는 naive한 방법보다 훨씬 효율적인 KMP 알고리즘을 사용한다. 가장 간단한 알고리즘부터 떠올려 보자 먼저, 우리가 문자열 검색을 수행하고자 하는 전체 문자열을 '짚더미(haystack)', 그리고 찾아내고자 하는 대상 문자열을 '바늘(needle)'이라고 칭하자. 짚더..