https://www.acmicpc.net/problem/2056 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net - 그래프 이론(Graph Theory) - 위상 정렬 (Topological Sort) - 다이나믹 프로그래밍(Dynamic Programming) 1. 위상 정렬 문제다. 아래는 예제 입력 1에 관한 내용을 그림으로 표현하였다. 2. 위상정렬은 간선(edge), 진입차수(Indegree)에 관한 배열과 큐(queue)를 이용하여 구현한다. 3. 하지만 이 문제는 ..

https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net - 그래프 이론(Graph Theory) - 다익스트라(Dijkstra) 1. 각 마을에서 파티장소까지 가고, 파티장소에서 다시 자신의 마을로 돌아오는 최단경로를 모든 vertex에 따라 구해야 한다. 그림은 다음과 같다. (4번 마을에 사는 사람에 대한 예시도 적었다.) 2. 결국 중요한 점은, 기존의 다익스트라 문제는 A->B까지 가는 거리의 최단거리를 구하는 것..

https://www.acmicpc.net/problem/13975 13975번: 파일 합치기 3 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net - 우선순위 큐(Priority Queue) - 그리디 알고리즘(Greedy Algorithm) 1. 처음에는 파스칼의 삼각형을 떠올려, 중간에 있는 값들을 최솟값으로 지정하고, 가장자리로 갈수록 오름차순의 나열을 떠올렸다. 하지만 이 과정을 한다고 해도, 덧셈 과정에서 for문을 필연적으로 두 번 사용해야 하기에 O(N^2)의 시간복잡도를 가져 시간초과가 날 것이라는 예상을 했다. 그 해결책..

https://school.programmers.co.kr/learn/courses/30/lessons/178870 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr - 투 포인터 (Two Pointer) - 부분합 (Partial Sum) - 누적합 (Prefix Sum) 1. 주어진 sequence의 이후 덧셈(for문 활용 - 시간복잡도 O(n) 증가)를 줄여주기 위해, 처음부터 누적합의 형식으로 sequence를 저장한다. 2. 배열의 길이가 1,000,000이기 때문에, 모든 부분합을 계산하게 되면(O(n^2)) 시간초과가 발생한다. 따라서 투 포인..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si > N; for (int i=0; i> x >> y; p[i].first..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net - 그래프 탐색(Graph Search) - DFS(Depth First Search) - BFS(Breadth First Search) - 이분 그래프 (Bipartite Graph) 1. 이분 그래프란? 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 주어진 그래프가 이분그래프인지 아닌지 검사하는 방법은, 인접한 정점끼리 서로 다른 색으로 칠해서 ..

https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net - 그래프 탐색(Graph Search) - DFS(Depth First Search) 1. 한마디로 말하자면, 섬이 몇 덩이(영역)있냐는 것이 문제다. 2. 바로 DFS를 떠올렸다. 아직 지나치지 않은 땅을 확인하면, 그 주변에 걸어갈 수 있는 땅을 다 찾을때까지 DFS한다. 위의 과정을 반복한다. 1. DFS는 재귀이므로, 현재 영역의 다음 영역(동서남북+대각선)에 대한 인덱스를 미리 받..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net - 그래프 탐색(Graph Search) - 너비 우선 탐색(Breadth-First Search) - 깊이 우선 탐색(Depth-First Search) 1. DFS와 BFS의 기본 개념을 잘 이해하고, 이를 코드에 적용할 수 있는지를 스스로 판단할 수 있는 대표적인 좋은 문제다. 2. 문제에서 시키는 대로, DFS와 BFS 코드 공식을 활용해서 풀어내면 된..

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net - 이분 탐색 (Binary Search) 1. 국가예산의 총액은 한정되어 있고, 여러 지방의 예산 요청액은 국가 예산 총액을 넘어설 수도 있다. 그렇기에 여러 지방의 예산 요청액을 최대한 충족하는 선에서, 국가예산 총액을 최대한 써야 한다(상한가 지정). 2. 상한가 지정은 Binary Search 로 진행을 한다. 1. Binary Search 진행 시에 low, mid, high 관계를..

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net - 자료구조(Data Structure) - 덱(Deque) 1. C++에서 배열을 지원하는 컨테이너로 대표적인 가 있지만, 문제를 보면 양쪽에서 pop과 push를 해야하는 상황이므로 배열을 더 유연하게 다룰 수 있는 를 쓰기로 했다. 1. 문제 이해가 우선이다. 1~N까지 적혀 있는 카드들을, 한꺼번에 왼쪽으로 밀거나 오른쪽으로 옮기면서 순서대로 원하는 카드들을 뽑는다는 것을 이해해야 한다..