어흥

문제 링크: https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 문제 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 www.acmicpc.net 1. 주의할 점 - 1 ->2, 2,3,4팀인 경우 생각해줘야 한다 (2->3, 3->4, 4->2를 통해 이미 2,3,4는 팀이 생성되었다고 가정) - Deque를 이용한다 2. 구현 - A학생이 어떤 학생과 팀이 되고 싶어하는지를 Arr[A] 배열에 저장한다 - Check[] 배열을 전부 False로 초기화하여 팀 검사가 이루어지지 않았다고 설정한다 - 1~Num 까지의 학생들을 전부 ..

문제 링크: https://www.acmicpc.net/problem/14921 14921번: 용액 합성하기 홍익대 화학연구소는 다양한 용액을 보유하고 있다. 각 용액은 -100,000,000부터 100,000,000사이의 특성 값을 갖는데, 같은 양의 두 용액을 혼합하면, 그 특성값은 두 용액의 특성값의 합이 된다. 당� www.acmicpc.net 1. 주의할 점 - 용액을 합성할 때 항상 사용될 용액 A를 미리 지정해 놓는다 - 이분탐색을 사용한다 2. 구현 - 용액 Num개를 입력 받는다 - For문을 통해 용액 A를 Arr[0]~Arr[Num-1]사이에 모든 용액을 사용한다(사실 Num-2까지만 해도 된다) - 용액 A를 Arr[i]로 골랐다면, Low = i+1, High = num-1을 가리..

문제 링크: https://www.acmicpc.net/problem/14588 14588번: Line Friends (Small) Q개의 줄에 걸쳐 두 선분이 가까운 정도를 출력한다. 만약, 두 선분 사이의 친구 관계가 단절되었다면 -1을 출력한다. www.acmicpc.net 1. 주의할 점 - 2개의 선분이 겹치는 조건을 잘 생각한다 - 플로이드 와샬 알고리즘에 대하여 알고 있어야한다 - 양방향 그래프이므로 플로이드 와샬을 사용할 경우, 배열의 원소를 잘 초기화 해야한다(내 코드의 경우 한번에 2개의 원소를 초기화 해야 한다) 2. 구현 - Arr[][]배열을 전부 987654321로 초기화하며, i==j인 경우에만 0으로 초기화한다 - 각 선분에 대한 정보를 입력받은 후, 2개의 선분(I,J)을 ..

문제 링크: https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으�� www.acmicpc.net 1. 주의할 점 - N^2으로 풀지 않도록 한다 -> TLE 발생 - Stack을 사용하여 풀도록 한다 2. 구현 - 모든 수들을 배열 Arr[]에 입력받으며, 가장 높은 빌딩의 높이+1을 Maxi 변수에 넣는다(가장 오른쪽에 위치한 건물의 오른쪽에 가상의 Maxi 높이만큼의 건물이 있다고 가정하고 풀기 위해 사용한다) - 건물 배열은 1~N에 담았기 때문에 N+1번째 빌딩..

문제 링크: https://www.acmicpc.net/problem/11780 11780번: 플로이드 2 첫째 줄에 도시의 개수 n(1≤n≤100)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 www.acmicpc.net 1. 주의할 점 - 플로이드 와샬 알고리즘을 진행하면서 경로를 저장해야 빠르게 문제를 풀 수 있다 - 플로이드 와샬 알고리즘을 진행하면서 새로운 최단 경로가 생성되는 경우, I~K까지의 경로 + K~J까지의 경로를 I~J까지의 경로에 갱신해서 저장한다. 단, K가 2번 입력되지 않도록 설정한다 - 간선의 정보를 입력받을 때, I~J까지의 경로가 1가지가 아닐 수..

문제 링크: https://www.acmicpc.net/problem/18223 18223번: 민준이와 마산 그리고 건우 입력의 첫 번째 줄에 정점의 개수 V와 간선의 개수 E, 그리고 건우가 위치한 정점 P가 주어진다. (2 ≤ V ≤ 5,000, 1 ≤ E ≤ 10,000, 1 ≤ P ≤ V) 두 번째 줄부터 E개의 줄에 걸쳐 각 간선의 정보 www.acmicpc.net 1. 주의할 점 - 다익스트라 알고리즘에 대해 알고 있어야 한다 - 다익스트라 알고리즘을 수행할때, 초기화를 잘해줘야 한다 2. 구현 - 민준이가 건우를 도와서 마산에 도착하는 경우, 민준-> 건우 + 건우->마산까지의 거리가 민준->마산까지의 거리와 같을 때다(각 간선의 가중치는 1보다 큰 정수이기 때문이다) - 모든 간선에 대한 ..

문제 링크: https://www.acmicpc.net/problem/10836 10836번: 여왕벌 입력의 첫 줄에는 격자칸의 가로와 세로 크기 M(2 ≤ M ≤ 700)과 날짜 수 N(1 ≤ N ≤ 1,000,000)이 자연수로 주어진다. 첫날 아침의 애벌레 크기는 모두 1이므로 입력에 주어지지 않는다. 다음 N개의 �� www.acmicpc.net 1. 주의할 점 - 매일마다 애벌레의 크기를 바꾸면 시간초과가 발생한다 - 0,1,2의 순서로 증가하는 크기를 나타내므로, 좌, 좌상, 상과 비교할때 제일 많이 자란 애벌레는 무조건 상이다 2. 구현 - 매일 자라는 애벌레의 크기를 Order[] 배열에 담는다. 단, 1씩 자라기 시작하는 곳, 2씩 자라기 시작하는 포인트에서만 ++한다 - 왼쪽과 상단의 ..

문제 링크: https://www.acmicpc.net/problem/17182 17182번: 우주 탐사선 우주 탐사선 ana호는 어떤 행성계를 탐사하기 위해 발사된다. 모든 행성을 탐사하는데 걸리는 최소 시간을 계산하려 한다. 입력으로는 ana호가 탐색할 행성의 개수와 ana호가 발사되는 행성의 위�� www.acmicpc.net 1. 주의할 점 - 플로이드와샬 알고리즘을 통해 미리 각 Node간 최단거리를 구해놓는다 2. 구현 - 각 Node간의 거리를 입력 받은 후, 플로이드 와샬 알고리즘을 사용하여 각 Node간 최단거리를 구한다 - 시작하는 행성의 Visit[]값을 True로 바꾼후, DFS()를 수행한다 - DFS(int idx, int dist, int planet) 함수는 각각 현재 행성,..