제가 지금까지 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에 나오는 순서는 시작한 노드에 근처에 있을 수록 더 빨리 나옵니다. 이러한 특징 때..

백준 21 문제. 1. BOJ 31287 : 장난감 강아지 - S3 Simulation + Bruteforcing 문제. min(N,K)번 반복시에 (0,0)으로 돌아오는 경우가 있는지를 알아보면 된다. 2. BOJ 13076 : Distinct rational numbers - G1 [업다운 랜덤디펜스 성공! Solved - 11:08] Math + Euler Phi function 문제. a/b가 다른 경우의 수들을 구하라면 a,b가 서로 서로소인 경우들을 전부 더해주면 된다. 그리고 0도 포함해야하니 +1. 오일러 피 함수 문제를 오랜만에 봐서 다른 문제에 제출한거 가져다가 썼다. 3. BOJ 1854 : K번째 최단경로 찾기 - P4 Dijkstra 문제. 그냥 각 노드가 i번째로 우선순위 큐에서..

백준 14 문제. 1. BOJ 14588 : Line Friends (Small) - G5 Floyd-Warshall 문제. 각 선분에 대해서 겹치면 1로 두고, 이후에 Floyd-Warshall 실행. 그러면 각 쿼리별로 O(1)만에 대답 가능하니 총 시간복잡도는 O(N^3+Q)가 된다. 2. BOJ 1525 : 퍼즐 - G2 BFS + Tree Set / Hash Set 문제. 메모리 제한 때문에 보드의 상태를 최대한 효율적으로 표현해야 했는데, 각 보드의 상태를 9자리 수로 표현함으로써 해결하였다. (예 : [[1,2,3],[4,5,6],[7,0,8]] -> 123456708) 이후에 BFS를 돌리면 되는데, visited 배열은 tree_set이나 hash_set을 써서 하면 된다. 나는 메모리 ..

2회 이후로 소식이 딱히 없던 보라매컵이 무사히 3회까지 열렸습니다! 솔직히 저는 2회 이후로 아무 소식도 못 받았어서 그냥 2회가 마지막일 줄 알았는데, 언제보니 홍보 탭에서 제 3회도 열린다고 하더라구요. 제 1회때는 실제 대회 참가자로써, 제 2회는 운영진으로써, 그리고 이번 제 3회때는 오픈컨테스트 참가자로써 개근하게 되었습니다. 이번 대회 예선도 지난번 대회와 동일하게 서브태스크 문제들로 출제했습니다. 서브태스크 문제들만 출제했다는 뜻은 전체적인 문제 난이도 분포가 상당히 어려울 것일거라 예상했었습니다. 그래서 이틀동안 진행되는 실제 대회에서는 문제들을 효율적으로 잘 긁어 부분점수들을 최대한 따가는게 본선을 가기 위한 전략이었을 것이라 예상했습니다. (일단 저라면 저렇게 예선을 참가했을 것 같아..