https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 이번에 풀은 문제는 트리구조 관련 문제라고 생각하고 풀었는데, 알고보면 그냥 BFS문제이다. 간단하게 생각하면 된다. 시작 노드를 1로 하고 인접 노드들의 위치에 부모 노드인 1을 집어 넣고, 그 다음 인접 노드에는 1의 자식 노드들을 집어 넣고 하면 된다. 말로하면 이게 무슨 말인가 싶을 수도 있다. 그래서 예제를 따왔다. 예제에서 주어진 입력을 BFS에서 사용하는 간선 추가를 위한 입력으로 생각하고, 시작 노드를 1로 해서 BFS로 탐색을 진행하면, 1과 ..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 오늘 푼 문제는 누적합과 투 포인터를 이용하는 문제였다. 나는 이 문제의 접근방식은 맞았지만 구현하는 과정에서 조건문을 처리하는 것에서 문제가 있어서 애를 먹었다.. 또 감자 짓도 해서 문제를 잘못 읽어 S인 값을 찾는다고 생각해버렸다.. 하지만 문제에는 S이상인 값이었다... 어쨌든 그래서 이 문제의 풀이 방법을 설명해보면 슬라이딩 윈도우 알고리즘이라고 생각하면 된다. 물론 슬라이..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 오늘 풀은 문제는 투 포인터 문제이다. 골드 5라는 등급을 받고 있는 문제이지만 조건만 잘 정한다면 금방 풀 수 있는 문제인 것 같다. 나는 이 문제를 처음에는 이분탐색트리를 사용해서 풀려고 했었다. 하지만 메모리 초과로 풀 수 없었다... 이번 문제를 풀면서 메모리 초과와 시간초과에 대해서 공부해야 겠다고 생각하는 계기였다.. 그래서 먼저 이 문제의 접근 방식은..

https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 이번 문제는 벨만 포드 알고리즘을 이용해서 푸는 문제였다. 다익스트라와 음의 가중치가 존재한다는 차이점 말고는 없는 알고리즘 로직이지만 이해하기 힘들었다.. 아직 정확하게 이해 한 것인지도 잘 모르겠다. 정리하자면, 배열을 모두 무한 값으로 초기화하고, 시작점의 값을 0으로 지정한다. 그다음에 다익스트라와 같은 원리로 초기화 작업을 시작..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 이번 문제는 저번에 BFS로 풀은 숨바꼭질 문제와 같은 문제이다. 차이점이라면 시간의 계산 정도이다. 하지만 이 차이점이 문제 풀이에 큰 영향을 준다. 이 문제를 풀면서 몇몇 사람들은 대입되는 인접리스트의 순서에 따라서 정답이 맞고, 틀리는 경우가 발생했다고 한다. 그것에 대한 증명을 하는 것은 어려운 일이다. 그렇지만 문제를 풀때 BFS로 적용 해야 할지 다익스..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 오늘도 한 감자 했다...어제와 비슷한 문제였는데...문제를 좀만 더 잘 읽을걸 그랬다. 문제의 내용은 간단하다 주어지는 특정한 정점 두개를 반드시 지나는 최단경로를 구하라는 것이다. 여기서 내가 실수 한 것은 문제에서 양방향의 간선이 주어졌다는 것이다....저번 1753번 문제를 생각하면서 풀다보니...양방향은 생각도 못했다....그래서 몇 시간 동안..

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 이 문제는 상당히 오래 걸린 것 같다. 다익스트라를 알지 못해서 무작정 BFS로 풀려고 하다보니 많은 시간을 허비하고 시간초과와 메모리 초과의 늪에서 못나오다가 결국 다익스트라 알고리즘을 공부했다. 다익스트라 알고리즘의 원리는 간단하다. 1. 출발지점을 설정한다. 2. 출발 지점을 기준으로 각 인접 노드에 접근하는 최소 비용을 저장한다. 3. 방문하지 않은 노..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 나는 처음에 이 문제에서 주어진 이분 그래프가 뭔지 잘 이해하지 못했다. 그래서 구글링을 통해 위키백과에 정의 된 그림도 봐보고 다른 사람들의 설명도 봐보았다. 문제에 주어진 아래와 같은 설명은 나같은 감자에게는 이해하기 어렵다. 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Gr..