본문 바로가기

백준8

[백준] 2261번: 가장 가까운 두 점 | C++ 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 브루트포스로 O(N^2) 시간에 해결할 수 있지만, O(NlogN)으로 푸는 방법을 알아보고자 한다. 정답코드 1. x좌표 기준으로 오름차순 정렬한다. 2. 0번째와 1번째 거리를 최소 거리(min_d)라고 가정한다. 3. 현재 살펴보는 좌표가 i번째 (x, y)라고 하면 [x - min_d, x] 범위에 해당하는 좌표를 "더 가까울 수 있는" 좌표 후보에 추가한다. 4. [y - min_d, y + min_d] 에 해당하는 좌표.. 2023. 6. 5.
[백준] 2150번: Strongly Connected Component (타잔 알고리즘) | C++ 2150번: Strongly Connected Component첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정www.acmicpc.net 정답코드타잔 알고리즘은 크게 세 가지 경우로 나뉜다. 1. 아직 방문하지 않은 노드 → 방문한다. 2. 방문했지만 SCC가 아직 아닌 노드 → id값이 더 작은 걸 저장한다. 3. 방문했고 SCC가 형성된 노드 → through 한다. 이런 경우를 거치고 현재 노드(id[cur]) id값과 저장된(remember) id 값이 같으면 스택에서 현재 노드를 만날 때까지 pop한다. 2번, 3번 경.. 2023. 6. 4.
[백준] 2957번: 이진 탐색 트리, 1539번: 이진 검색 트리 | C++ 2957번: 이진 탐색 트리 이진 탐색 트리는 모든 노드가 많아야 2개의 자식 노드를 가지고 있는 트리이고, 각 노드에는 수가 하나씩 쓰여있다. 만약 어떤 노드에 쓰여 있는 수가 X라면, 그 노드의 왼쪽 서브트리에는 X보다 www.acmicpc.net 1539번: 이진 검색 트리 P는 크기가 N인 배열이다. P에는 0보다 크거나 같고, N-1보다 작거나 같은 정수가 중복 없이 채워져 있다. 이진 검색 트리는 루트가 있는 이진 트리로, 각각의 노드에 정수 값이 저장되어 있는 트 www.acmicpc.net 거의 같은 문제! 틀린 이유 처음에 2957번 문제를 풀 때 그냥 BST를 구현했었다. #include #include #include #define MAX 100000 #define fse(A,B,C).. 2023. 5. 27.
[백준] 2887번: 행성 터널 | C++ https://www.acmicpc.net/problem/2887 2887번: 행성 터널첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이www.acmicpc.net 접근방법1. MST문제다. union-find 써야 할 것 2. 모든 행성 간 가중치를 구하려면 N! 인데? 3. 행성 간 가중치는 행성 간 3차원 거리가 아니라 min(|xA-xB|, |yA-yB|, |zA-zB|) 이다. 4. x, y, z 대로 정렬 3번 수행하고 인접한 행성의 거리를 구한다. 5. 힙에 넣어 가중치 최솟값을 구한다면? 라고 생각회로 거쳤다. 정렬.. 2023. 5. 22.
[백준] 12015번: 가장 긴 증가하는 부분 수열 2 | C++ 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 정답코드 C++의 lower_bound, upper_bound C++에서는 이진탐색으로 원소를 탐색하는 lower_bound, upper_bound 메서드를 제공한다. lower_bound : 찾으려는 key 값보다 같거나 큰 숫자가 등장하는 인덱스를 반환한다. upper_bound : 찾으려는 key 값을 초과하는 숫자가가 등장하는 인덱스를 반환한다. int arr[]={0,1,2,3,4,5,5,5,6,7}; lower_bound(arr.begin(), arr... 2023. 2. 23.
[백준] 10971번: 외판원 순회 2 | C++ https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 1. 외판원 순회 알고리즘 - 가중치가 양의 정수이고 N이 작을 경우 (Sliver 2) 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.. 2022. 12. 25.
[백준] 18430번: 무기 공학 | C++ https://www.acmicpc.net/problem/18430 18430번: 무기 공학 첫째 줄에는 길동이가 가지고 있는 나무 재료의 세로, 가로 크기를 의미하는 두 자연수 N, M이 주어진다. (1 ≤ N, M ≤ 5) 다음 N개의 줄에 걸쳐서, 매 줄마다 나무 재료의 각 위치의 강도를 나타내 www.acmicpc.net 틀린 이유 안 쓰려다가 날 너무 괴롭혀서 쓴다... 1. 처음 접근 때는 백트랙킹 메서드 안에 for 문을 두 개 돌렸었다. 인수로 x, y 좌표를 입력 받고 인수에서 시작하는 for 문 두 개.... (이것이 근본적으로 틀린 접근이었다.) 아무튼 처음 틀린 이유는 (1) for 문을 돌릴 때 p,q,x,y 변수를 아예 틀리게 써서 틀렸다. → 오타를 인지 못했다는 뜻 2. 오타.. 2022. 12. 19.
이것이 취업을 위한 코딩 테스트다 with Python 독서기간_2022년 11월 25일 ~ 2022년 12월 1일 저자_나동빈 코딩 테스트 알고리즘 입문 도서로 추천한다. 언어 선택 기준부터 시작해 기본적인 알고리즘을 코드 예제와 함께 쉽게 설명한다. 나는 백준을 어느정도 풀었었고, 이 책을 읽기 앞서 빡빡한 이론서 두 권을 읽었더니 쉽게 느껴졌다. 입문자에게도 Python의 직관성 덕분에 코드 해석하는 데 어렵지 않을 것이다. 책에서 어려운 알고리즘이라고 해봤자 위상정렬 정도이다. 백준 문제를 풀면서 Union-Find, MST, 크루스칼 이론을 따로 따로 공부했었는데, 세 가지 모두 연관되어 있다는 것을 알았다. 수준이 높아질수록 각 알고리즘의 연관 관계를 생각하며 공부하자. 아직 그리디스러운 발상이 어려운데... 많은 문제를 접하다보면 연상할 수 있을.. 2022. 12. 3.

티스토리툴바