-
[BOJ] 이진 탐색 트리
BOJ2957 이진 탐색 트리 이진 탐색 트리를 그냥 구현하면 당연히 TLE를 받습니다. 플래티넘 5에 이렇게 단순한 구현을 시킬 일은 없습니다. 이진 탐색 트리를 만들었다고 가정하고, 이를 아래로 눌러 일렬로 만들어봅시다. 이 그림에서 잘 살펴보다 보면, 각 노드의 부모는 일렬로 만든 상태에서 각 노드에 인접해있고, 인접한 노드 중 깊이가 깊은 노드임을 알 수 있습니다. 따라서 배열을 항상 정렬된 상태로 유지하고 노드를 삽입할 때 인접한 칸의 깊이를 빠르게 알 수 있다면, 문제를 해결할 수 있는 것입니다. 문제는,...
-
[BOJ] 소가 길을 건너간 이유 9
BOJ14463 소가 길을 건너간 이유 9 다음과 같은 관찰만 할 수 있다면 아이디어는 간단합니다. A<B를 만족하는 네 정수 A, B, C, D와 A, B를 잇는 선분 X와 C, D를 잇는 선분 Y에 대해 다음과 같은 명제가 성립합니다. Lemma 1. X와 Y가 교차함은 A<C<B<D와 동치이다. 이 두 명제는, 몇가지 케이스를 나눠 살펴봄으로써 관찰할 수 있습니다. Lemma 1에 의해 같은 소가 지나는 점을 잇는 선분을 번호가 작은 점을 기준으로 정렬한다면, 어떤 선분 K에 대해 K와 교차하며 K보다...
-
[BOJ] 등산
BOJ1486 등산 그래프의 간선 가중치에 대해 조금만 생각해보면 핵심적인 아이디어를 떠올릴 수 있습니다. 간선의 존재여부 및 그 가중치를 인접행렬이나 인접리스트로 저장하는 대신, 인접한 두 위치와 그 높이를 갖고 간선 존재여부 및 가중치를 O(1)에 계산할 수 있습니다. 이 격자 그래프에서 노드의 개수는 최대 625개이고, 간선의 수도 이에 선형비례하므로 다익스트라 알고리즘을 사용해 준다면 시작점에서 모든 노드로 가는 최단시간을 파악할 수 있습니다. 한 가지 문제점은 우리가 고려할 경로는 가는 경로뿐만 아니라 오는 경로도 있다는 것이지만, 이는 간선 가중치를...
-
20210709 BOJ 연습
서론 그냥 심심해서 몇 문제 풀었는데 좀 괜찮은 문제 얻어간거 같아서 괜찮은 하루였던 듯. 1. BOJ1043 거짓말 만약 두 파티에 공통된 인원이 있다면, 그 두 파티에서 거짓말을 할 수 있는지는 서로 동일하다. 따라서 두 파티 중 하나에라도 속하는 인원들은 두 파티짜리의 한 덩어리(=독립집합) 인원으로 볼 수 있고, 이 점에서 Union-Find를 쓰면 각각의 독립집합을 형성할 수 있다. 약간의 Union-Find 기술을 쓸 수 있는데, 각 독립집합이 하나의 음 아닌 정수로 표현할 수 있는 특정을 갖는다면 -1배하여 독립집합의...
-
[LEETCODE] LeetCoding Challenge - Find All Anagrams in a String
LeetCoding Challenge - Find All Anagrams in a String 문자열 S와 P가 주어지는데, S의 연속 부분 문자열 중 P와 애너그램 관계인 문자열의 시작 인덱스를 모두 담은 벡터를 반환하는 문제입니다. 길이가 N인 문자열의 애너그램 개수는 N! 개이므로 모든 애너그램에 대해 판별하는 것은 조금 무리가 있어보입니다. 그렇다면 애너그램 전부에 대해 값이 같은 방식의 해싱을 사용해서 비교하면 어떨까요? 이런 해싱 중 가장 쉽게 떠올릴 수 있는 건 연속한 len(P)개의 문자의 아스키코드 값을 모두 곱하면 문자의 배치 순서와는 무관하고,...