전체 글

https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 풀이 총 2가지 풀이 방법으로 접근할 수 있다. 1. SCC 로 강한 결합요소를 전부 찾아서 (요소가2이상 혹은 셀프 사이클인 부분) 전체N에서 빼는방법 2. dfs 사이클 탐지 방법 1. SCC 풀이 방법 SCC는 scc집합들을 담은 ArrayList라고 할때 , SCC를 반복문으로 돌려서 scc의 크기가 2이상이거나 , 1이지만 셀프참조를 할 경우에 전체 N에서 그 만큼 갯수를빼주면 팀에 속하..

https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 문제 풀이 탐색 문제이다. 우선 섬의 갯수를 세고 각 섬마다 다른 숫자로 라벨링을 해준다. (초기1-> 2,3,4, .... ) 섬 아무곳에서 출발하여 바다면 움직인거리+1 다른 섬을만나면 섬섬 거리 최소거리 갱신 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 3..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 풀이 만약 스티커를 하나 떼어 냈다고 가정하면 다음에 뗄 수 있는 스티커는 한칸대각선 or 두칸 대각선이다. 즉 , 이 둘중에 큰 값을 선택하면 끝 반대로 말하면 이전의 스티커 점수의 합은 그림과 같이 둘 중 큰 곳에서 가져오면 된다. 파란색의 스티커를 떼어냈다고 가정을 하면 이전의 점수합은 빨간색 둘 중 큰 값을 가져오면 된다는것. 따라서 점화식은 1 2 3 4 5 6 7 8 9..

문제 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 증가하는 수열 -> 감소하는 수열 형태로 나오기때문에 lis 알고리즘을 일단 떠올려야 한다. 왼쪽에서 출발하여 증가하는 수열을 DP로 접근하여 뽑은 결과를 DP1 오른쪽에서 출발하여 증가하는 수열을 DP로 접근하여 뽑은 결과를 DP2 for 문으로 0~수열의길이 까지 순회하여 DP1[i]+DP2[i]-1 이 가장 큰 값이 정답 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..

풀이 스케쥴링 방법 중 하나인 SJF 방식이다. 1. 처리해야 할 작업 중 현재 기준으로 처리할 수 있는 작업을 선택 2. 선택한 작업을 가장 시간이 덜 걸리는 순으로 처리 1. 입력받은 jobs를 가장 먼저 도착하는 순서로 정렬을 수행한다. 2. 정렬된 jobs배열 중 처리 가능 한 Task를 우선순위 큐에 전부 삽입 3. 만약 큐가 비어있다면 => 현재까지 경과된 시간을 jobs배열의 다음 대상의 도착시간까지 당겨오고 , 2번으로 4. 큐에서 하나씩 빼면서 처리하면서 시간들 계산 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 import j..

https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 문제 풀이 SCC (강한 결합 요소)를 구하기위해 코사라주 알고리즘을 사용했다. 1. 그래프를 dfs 로 탐색하면서 Stack에 탐색한 정점들을 push 2. Stack 에서 원소 하나씩 Pop 하면서 , 역방향 그래프 탐색 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22..

문제 https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 풀이 다음과 같은 예시인 경우 , 6:3 으로 나누면 차이가 최소가 된다. 즉 , 차이가 최소이기 위해선 한쪽편에 해당되는 노드의 자식수를 a 라고하고 전체 노드의 수n-a 를 다른 한쪽편의 노드들이라고 했을때 구해야 하는 최소값을 min 이라고 하자. min(n-2a , min) 이 답이다. 1. 1번 노드를 root 로 기준을 잡고 시작하여 2. 해당 노드의 자식수를 ..

https://www.acmicpc.net/problem/19581 19581번: 두 번째 트리의 지름 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리 www.acmicpc.net 문제 풀이 트리의 지름을 구하기위해 다음과 같은 방법을 이용해서 구할 수 있었다. 1. 아무노드(1)에서 탐색을하여 제일 먼 것(a)을 선택. 2. 선택한 제일 먼 노드(a)에서 제일 먼 노드를 선택(b) ab 의 거리가 트리의 지름이다. 그러나 , 이 문제에서는 조건이 하나 더 추가된다. 두번째 큰 지름을 구하는것. 위의 1,2번 까지는 똑같이 하면된다. 3. a에서 출발하여 b를 ..