백준 13 문제. 1. BOJ 31430 : A+B - 투 스텝 - B1 A + B가 최대 2*10^18까지 가능하다. 그런데 'a' = 0, 'b' = 1, ... 이렇게 매핑하면 26진법으로 표현이 되면서도 26^13 이 2*10^18보다 더 크므로 26진법 인코딩을 해주면 된다. 이후에 다음 프로그램 에서는 26진법 표현을 받고 이를 다시 10진법으로 변환하면 된다. 처음으로 푼 투 스텝 문제라서 리뷰해보았다. 투 스텝 문제를 이해하고 입문하기 매우 좋은 문제라 생각한다. 2. BOJ 15651 : N과 M (3) - S3 Backtracking 문제다. 그냥 N^M 가지의 경우의 수를 전부 돌려보면 된다. 다른 N과 M 문제들과 비슷한 문제였다. 3. BOJ 5347 : LCM - S5 Numbe..

백준 19 문제. 1. BOJ 11502 : 세 개의 소수 문제 - S4 Number Theory(Primality Test) + Bruteforcing 문제. 1000 이하의 모든 소수를 찾는 건 그냥 O(N^2)로도 찾을 수 있다. 1000 이하의 소수는 대략 200 개 미만일 것이라 생각해서 세 수를 찾는 건 O(N^3)로 모든 조합을 찾아보았다. 앞에 소수 찾는 걸 Sieve로 좀 더 빠르게 찾을 수는 있는데... 귀찮아서 구현을 안 했다. 2. BOJ 11332 : 시간 초과 - S3 Implementation + Case-working 문제. 시간복잡도를 나타내는 문자열에 따라서 로직을 전부 다르게 구현해야 한다. O(N^2), O(N^3), O(2^N), O(N!)은 오버플로우가 나타날 가능..

백준 16~17문제. 1. BOJ 23760 : 까다로운 아이들과 선물 상자 - P5 (업다운 랜덤디펜스 성공! Solved - 18:01) Segment Tree + Binary Search 문제. 쿼리 순서대로 K 번째로 큰 수를 Segment Tree에 쿼리를 날려서 찾고 이를 업데이트 해주는 문제였다. 쿼리는 Binary Search를 응용하면 된다. 처음에 쿼리 순서를 마음대로 바꿔도 되는가 싶어서 예제가 이해 안 되었는데, 나중에보니 순서가 고정이라서 쉽게 풀었던 문제. 2. BOJ 23757 : 아이들과 선물 상자 - S2 Priority Queue 문제. 위의 BOJ 23760을 푼 김에 같이 풀어본 문제였는데, K=1이 고정인 문제여서 PQ로 풀 수 있었다. PQ 공부하기 좋은 문제라 생..

제가 지금까지 PS 문제를 풀 때 깨달은 유용한 팁들을 한 번 공유해보고자 합니다. 들어가기 앞서서, 여기에 적은 내용들은 전부 지극히 저의 주관적인 생각들입니다. 따라서 제 생각이 틀렸을 수 있으니 참고만 하시면 좋습니다. 그리고 피드백은 언제나 환영이니 댓글로 마음껏 해주시면 감사하겠습니다 :) 1. 시간 제한은 1초에 1억(10^8)번 연산이 가능하다고 생각하는게 편합니다. 저는 '1초 = 1억번의 연산'이라는 가정을 세우고 가능한 시간복잡도를 계산해봅니다. 주로 정해의 시간복잡도에 따른 연산 횟수를 계산해보면 이 공식이 맞는 것 같습니다. 물론 연산이 간단한가 어려운가에 따라서나 붙는 상수에 따라서 1초에 가능한 연산의 횟수가 커질 수 있긴 합니다. (그래서 저도 계산을 해보았을 때, 1억번을 '..

이번 글에서는 Dijkstra 알고리즘을 역추적하는 방법에 대해서 설명해보고자 합니다. Dijkstra 관련 문제들을 풀다보면 가끔씩 최단 경로를 출력하라는 문제들을 볼 수 있습니다. 이럴 때에는 도착 노드부터 시작 노드까지 역으로 추적하는 방법으로도 최단 경로를 찾을 수 있습니다. 그러면 어떻게 역추적을 하면 될까요? 일단 최단 경로의 특성에 대해서 알아보도록 합시다. 노드 A, B가 각각 시작 노드와 도착 노드라 합시다. 그리고 A와 B간의 최단 경로에 K라는 노드가 속할 수 있다고 합시다. 그렇다면 다음과 같은 식이 성립합니다. A -> B의 최단 거리 = (A -> K의 최단 거리) + (K -> B의 최단 거리) 이러한 식은 A -> B의 최단 경로에 속하는 모든 노드들에 대해서 적용할 수 있습..

이번에는 Dijkstra 알고리즘에 대해서 설명을 해볼건데, 제가 이해한 방식으로 한 번 설명을 해보려고 합니다. 따라서 이게 옳은 설명인지에 대해서는 엄청 확신이 들지는 않지만 그래도 알고리즘 기본적인 작동방식을 이해하기는 쉽지 않을까 생각해봅니다. (그래서 정확한 증명보다는 이해하는데에 좀 더 집중을 하면 좋을 것 같습니다!) 그 전에 앞서서 일단 BFS 알고리즘의 특성에 대해서 설명해보도록 하겠습니다. BFSBFS(Breadth First Search)는 그래프 탐색 방법 중 하나인데, 특정 노드부터 시작해서 근처에 있는 순서대로 탐색을 하는 방법입니다. 구현을 할 때에는 주로 Queue로 구현을 하는데, Queue에 나오는 순서는 시작한 노드에 근처에 있을 수록 더 빨리 나옵니다. 이러한 특징 때..