반응형 분류 전체보기584 [C/C++] 백준 #2696 중앙값 구하기(힙) 힙(heap) 자료구조는 알고리즘에서 다양한 곳에서 사용할 수 있습니다. 우선순위큐가 대표적이고, 이 문제와 같이 중앙값을 찾는 용도로도 사용할 수 있습니다. 검색, 삽입, 삭제가 모두 \(O(\log N)\) 의 시간 복잡도를 가지므로, 큰 N에 대해서도 매우 빠르게 검색, 삽입, 삭제를 할 수 있습니다. 아래는 문제의 링크입니다.https://www.acmicpc.net/problem/2696 주요 포인트는 다음과 같습니다. 1. 입력과 출력 관리 • scanf를 사용하여 입력을 받고, printf와 putchar를 사용하여 출력을 합니다. • 여러 테스트 케이스를 지원합니다. 2. 힙(heap)을 이용한 중간값 찾기 • 최대 힙(max-heap)과 최소 힙(min-heap)을 사용하여 중간값을.. 2024. 8. 7. [C/C++] 백준 #2673 교차하지 않는 원의 현들의 최대집합(깊이우선탐색) 일단 이 문제는 추천하는 알고리즘은 동적 계획법(Dynamic Programming)입니다.저는 깊이우선탐색(Depth First Search)를 이용해서 문제를 풀었고, 경과시간은 4ms를 얻었네요. 아마 동적 계획법을 이용해서 풀면 더 나은 결과가 있었을 것이라고 생각은 합니다. https://www.acmicpc.net/problem/2673 제가 한 방법은 다음과 같습니다.1) 모든 현들과 서로 교차하지 않는 현들을 구해서 그 결과를 비트 플래그로 저장 \(O(N^2)\)2) 1번 현부터 시작해서 모든 현에 대해서 2-1) 교차하지 않는 현들을 방문하여 최대 길이를 구한다. 이 프로그램은 원 위에 주어진 여러 개의 현(chord) 중에서 서로 교차하지 않는 최대 개수의 현을 찾는 문제를 해결.. 2024. 7. 8. 수학문제집 풀이 ---\( MM_p = 2^{2^p-1} - 1 \)\( MM_{M_p} = 2^{2^{2^p-1}-1} - 1 \)---\( \left(\frac{3}{MM_p}\right) = -1 \) 일 때 \( \left(\frac{3}{MM_{M_p}}\right) = -1 \) 임을 보여라.---**Proof**:\( MM_p = 2^{2^p-1} - 1 \)\( MM_{M_p} = 2^{MM_p} - 1 \)---\( \left(\frac{3}{MM_p}\right) = -1 \) 이므로 만족하는 \( MM_p \)를 찾는다. 이 때, \( x = 12k \pm 5 \) (k는 정수)---\( 2^x - 1 = 2^{12k \pm 5} - 1 \)---\( 2^{12k + 5} - 1 = 1 + 2^1 +.. 2024. 6. 7. [C/C++] 백준 #2668 숫자고르기(순환구조 탐색) 이번 문제는 양면에 숫자가 적인 숫자 카드를 적절하게 골라서, 한면에 있는 숫자들 집합과 다른 한면에 있는 숫자들 집합이 같은 최대의 카드수를 찾아내야 합니다. 그래프 연결이 맞기는 하지만, 이것을 깊이 우선 탐색이라고 하기에는 적절하지 않아서, 순환구조 탐색이라는 말을 사용했습니다. 카드들의 앞에 있는 숫자는 모든 1부터 N까지 모든 숫자들이 있고, 뒤의 숫자들은 1부터 N까지 수중에 임의 수들이 적혀 있습니다. 여기에 적당한 카드들을 선택하면, 앞의 숫자들은 서로 겹치지 않기 때문에 뽑은 카드수만큼의 숫자들이 집합이 되지만, 뒤의 숫자는 겹치는 경우도 있을 수도 있죠. 그래서 같은 집합이 되려면, 각각의 뒤에 있는 숫자들이 다음 카드들을 가르키고 있고, 맨 처음 카드까지 순환을 이룬다면, 이 하.. 2024. 6. 4. [C/C++] 백준 #2667 단지번호붙이기(깊이우선탐색) 제가 회사에서 개발자를 뽑을 때, 코테를 실시해서 그 결과를 가지고 1차에서 거르고 면접을 보게 되는데, 이 문제와 같은 유형은 단골 메뉴로 들어가 있습니다. 보통은 섬의 갯수 구하기 문제입니다. 이 문제도 거의 같지만, 섬의 크기, 여기서는 단지의 크기를 정렬하고, 그 결과를 출력하는 것만 다릅니다. 이런 문제는 너비우선탐색을 이용해서 풀어도 되겠지만, 프로그램의 복잡도상 깊이 우선탐색이 보다 편리합니다. 그리고 방문 기록을 지도에 바로 활용하면 추가적으로 필요한 저장 공간 \(O(N^2)\)을 잡지 않아도 됩니다. https://www.acmicpc.net/problem/2667 ### 주요 변수- `q`: 각 노드가 가리키는 다음 노드를 저장하는 배열.- `v`: 각 노드의 방문 상태를 저장.. 2024. 6. 3. [C/C++] 백준 #2665 미로만들기(다익스트라) 이번 문제는 얼듯 보면 미로를 백트래킹(또는 깊이우선탐색) 등으로 풀어나갈 것 같지만, 벽을 가는 곳을 간선 웨이트를 1로, 벽이 없는 곳을 간선 웨이트 0으로 생각하고 다익스트라 알고리즘을 적용하면 풀기 편합니다. https://www.acmicpc.net/problem/2665 제가 작성한 소스의 설명입니다. 일반적인 다익스트라 알고리즘을 이용했는데, 우선순위큐에 저장될 값들을 비트연산을 통해서 정수형(int)로 만들어서 했습니다. 1. **입력 받기**: 사용자로부터 미로의 크기 \( n \)과 미로의 지도를 입력받습니다.2. **우선순위 큐 사용**: 미로의 각 방을 탐색하기 위해 우선순위 큐를 사용합니다. 이 큐는 현재 경로에서 흰 방으로 바꿔야 할 검은 방의 수를 우선순위로 사용합니다.3... 2024. 6. 1. 이전 1 ··· 8 9 10 11 12 13 14 ··· 98 다음 728x90
