본문 바로가기

자료 구조

 (13)
[C++] 25832번 Making Connections https://www.acmicpc.net/problem/25832 25/01/01  약간의 트릭을 가미한 유니온 파인드 문제다. 이 문제를 참 많이 틀렸었는데... 허무하게 원인을 찾아버려서 글로도 남겨보고, 복습도 해보고자 한다. 문제 접근 방식:  결론적으로 틀린 원인만 말하면 long long이슈다. long long자료형을 써야하는데 int를 써서 값이 이상하게 나왔다. 문제는 두 가지 쿼리를 처리해야한다. 첫번째로 두 노드를 합치는 연산. 두 노드를 합친다면 두 노드는 같은 그룹에 속해있게 된다. 두번째로 그래프의 복잡도를 구하는 연산. 이때 모든 그룹의 크기와 그룹의 개수를 구해야 한다. 유파로 처리해보이는건 당연하고, 두번째를 어떻게 빠르게 처리할 지가 의문일 것이다. 따라서 나는 그룹의 ..
[Python] 32387번 충전하기 https://www.acmicpc.net/problem/32387 24/10/06   KCPC 당시, 파이썬으로 검수했던 문제다. 다양한 풀이가 있어서 나름 연습해보기 적절한 문제라고 생각한다. 문제 접근 방식:  문제의 요구 사항은 다음과 같다. 크기가 $N$인 Bool 배열 $A$가 주어지고, 두 종류의 쿼리가 주어진다. 쿼리의 개수는 최대 $10^6$개이며, 배열의 최대 크기는 $10^6$이다. 또한, 배열의 초기 상태는 모두 False로 초기화되어있는 상황이다. 1번 쿼리는 인덱스 $i$가 주어진다. $i$보다 크거나 같은 인덱스 $k$중에서, $A[k]$ = False로 되어있는 가장 작은 인덱스를 True로 바꾸는 것이다. 만약 이것이 불가능하다면 $-1$을 출력한다. 2번 쿼리는 인덱스 $..
[Python] 2357번 최솟값과 최댓값 (추후 보강 예정) https://www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 24/03/15 대다수의 사람들이 해결한 방식인 세그먼트 트리로 해결하지 않고, 제곱근 분할법으로 해결한 문제이다. 세그먼트 트리로 해결한다면 이후 세그먼트 트리 풀이를 작성할 예정이다. 첫 번째 문제 접근 방식: 제곱근 분할법으로 해결했다. 제곱근 분할법은, 길이 $N$짜리 배열이 있다면 그 배열을 $\sqrt{N}$크기로 적당히 분할하여 시간 복잡도를 줄여..
[Python] 18116번 로봇 조립 https://www.acmicpc.net/problem/18116 18116번: 로봇 조립 성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 www.acmicpc.net 24/02/21 분리 집합 문제로, 집합의 크기를 바로 내보내는 쿼리를 어떻게 구현해야 할 지 집중해야 해결할 수 있는 문제다. 문제 접근 방식: 결론부터 말하면, 집합의 크기를 바로 내보내는 리스트를 따로 관리해주면 된다. 기존 분리 집합 코드에서는 배열의 인덱스는 해당 노드의 값, 배열의 값은 해당 노드를 자식 노드로 가지는 노드의 값, 즉, 부모 노드의 값을 저장한다. 나는 여기에서 집합의 개수..
[Python] 5588번 별자리 찾기 https://www.acmicpc.net/problem/5588 5588번: 별자리 찾기 상근이는 밤하늘 사진에서 별자리를 찾고 있다. 사진에는 꼭 찾고 싶은 별자리와 같은 형태, 방향, 크기의 도형이 한 개가 포함되어 있다. 하지만, 상근이가 가지고 있는 사진 속에는 별자리를 www.acmicpc.net 24/02/01 간단한 브루트포스 문제로, 집합을 사용해 적절히 구현하면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 별자리를 구성하는 별들은 리스트로 받고, 사진 속 별 들의 위치는 집합에 넣어주었다. 이후 사진 속의 모든 별들 마다 그 별이 옮겨진 별자리의 중심이 된다고 가정하고 이동량을 구해주었다. 옮기기 전 별자리에 있는 모든 별 마다 그 이동량을 적용해 주었다. 즉, 옮겨진 별의 좌표를..
[Python] 23309번 철도 공사 https://www.acmicpc.net/problem/23309 23309번: 철도 공사 첫 번째 줄에 공사를 시작하기 이전에 있는 역의 개수를 나타내는 양의 정수 $N$과 공사 횟수를 나타내는 양의 정수 $M$이 주어진다. ($1 \le N \le 500\,000$, $1 \le M \le 1\,500\,000$) 두 번째 줄에는 공사 www.acmicpc.net 24/02/13 파이썬으로 해결하기 정말 힘든 문제로, C++을 사용할 수 있는 사람이라면 웬만해서는 C++로 해결하기를 권장하는 문제다. 주어진 그대로 잘 구현을 했음에도 불구하고 여러 기술들을 활용해야만 시간 초과를 면할 수 있다. Python3로는 통과한 사람이 없는 것으로 보아, Pypy를 사용해야만 풀 수 있는 문제로 보인다. 문..
[Python] 2295번 세 수의 합 https://www.acmicpc.net/problem/2295 2295번: 세 수의 합 우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최 www.acmicpc.net 23/12/28 중간에서 만나기(MITM)으로 안 풀어도 집합으로 쉽게 풀 수 있는 문제이다. 나는 중간에서 만나기 알고리즘 연습을 위해 그 방법으로 문제를 해결했다. 첫번째 문제 접근 방식: MITM으로 해결했다. 세 수의 합이 최대가 되도록 하려는 것이 우리의 목적이고, 그 세 수의 합 또한 기존 배열에 존재해야 한다. 나는 두 개로 분할했는데,..
[Python] 11478번 서로 다른 부분 문자열의 개수 https://www.acmicpc.net/problem/11478 11478번: 서로 다른 부분 문자열의 개수 첫째 줄에 문자열 S가 주어진다. S는 알파벳 소문자로만 이루어져 있고, 길이는 1,000 이하이다. www.acmicpc.net 22/11/30 단계별로 풀어보기에서 풀은 문제로, 부분 문자열을 찾아내는 방법과 집합 자료구조에 대한 사용법만 알고 있다면 쉽게 풀 수 있는 문제이다. 문제 접근 방식: 모든 부분 문자열을 찾아내고, 이를 부분 문자열 집합에 넣어서 그 집합의 크기를 구하면 끝나는 문제이다. 부분 문자열을 찾아내는 방법은, 문자열 슬라이싱을 이용하여 찾아낼 수 있다. 부분 문자열의 길이가 될 수 있는 $len \ sub \ string$을 $1$부터 $len(S)$까지 for문으로..

티스토리툴바