문제링크 https://www.acmicpc.net/problem/21923 21923번: 곡예 비행 동헌이는 모형 비행기 조종 대회에 참가하였다. 이 대회에서는 격자 모양의 공간에서 모형 비행기를 조종하여 얻는 비행 점수로 순위를 매긴다. 격자의 각 칸에는 점수가 부여되어 있고, 비행 www.acmicpc.net 문제풀이 처음 격자형 그래프에 대해 BFS로 풀이하려 함 그런데 상승에서 하강으로 바뀌는 시점에 처리가 모호했고, 제한된 시간 40분을 초과하여 풀이 방법을 확인함 - 동적 프로그래밍 풀이 - 상승과 하강일때 dp 테이블을 각각 구한 후 반복문 돌며 합했을 때 최대치를 구하면 됨 - 시간 복잡도 : N, M이 각 1000이라 해도 대략 O( 3 * 10^6 ) 보다 적게 연산 된다. 예시 예제..

문제링크 https://www.acmicpc.net/problem/21925 21925번: 짝수 팰린드롬 (1, 1), (5, 6, 7, 7, 6, 5), (5, 5) www.acmicpc.net 문제풀이 그리디 알고리즘 풀이 방법을 알게 되어 풀이시 메모리와 시간적 측면에서 앞서 직접 DP 풀이한 방식보다 나은 것을 확인가능했다. - 그리디 알고리즘 풀이 - 핵심 아이디어 : 큰 짝수 팰린드롬은 작은 짝수 팰린드롬으로 구성이 된다. 그러므로 1) i와 j 포인터를 사용해서 최소가 되는 짝수 팰린드롬 구하면 결과값 증가시키고 포인터 이동 (i < N까지) 2) i 시작점에서 팰린드롬을 찾지 못하는 경우 종료 후 -1 출력 (투 포인터 방식) 제출코드 import java.util.*; import jav..

문제링크 https://www.acmicpc.net/problem/21925 21925번: 짝수 팰린드롬 (1, 1), (5, 6, 7, 7, 6, 5), (5, 5) www.acmicpc.net 문제풀이 직접 풀이하여 통과는 하였지만, 방문 배열로 사용여부를 체크한다거나 맨앞에 펠린드롬이 아닌 경우 처리를 찾지 못해 아쉬움이 남는다. - 동적 프로그래밍 풀이 - palindrome 2차원 배열 전처리하여 구함 팰린드롬인 경우 1) 자기 자신이거나 (길이1) 2) 바로 옆에 수와 같거나 (길이2) 3) 양 끝이 같고, (시작점 + 1) ~ (끝점 - 1) 범위의 수도 팰린드롬인 경우 - 최대 수열의 길이 N = 5,000이기 때문에 int[][] palindrome 선언시 4byte * 5,000 * 5..

목차 최소 신장 트리 (MST, Minimum Spanning Tree) 그래프 내의 모든 정점을 포함하면서 사용된 간선들의 가중치 합이 최소가 되는 트리 MST 특징 1) 간선(Edge)의 가중치 합이 최소 2) N개의 정점을 가지는 그래프에서 반드시 (N - 1) 개의 간선만을 사용해야 함 (= 트리의 성질) 3) Cycle을 포함하면 안된다 프림(Prime) 알고리즘 - 인접 리스트와 우선 순위 큐, 그리고 방문 배열을 사용 - 시작점을 기준으로 인접한 정점 중에 아직 연결하지 않았고, 가중치가 최소인 정점을 선택 반복하여 노드를 연결함 - 우선 순위 큐를 집합으로 보고, 가장 가중치가 작은 노드를 우선 순위로 하여 연결(=방문) 여부 확인 후 연결 처리 한다. - 시간 복잡도 : O((V + E)..

최소 신장 트리 (MST, Minimum Spanning Tree) 그래프 내의 모든 정점을 포함하면서 사용된 간선들의 가중치 합이 최소가 되는 트리  MST 특징1) 간선(Edge)의 가중치 합이 최소2) N개의 정점을 가지는 그래프에서 반드시 (N - 1) 개의 간선만을 사용해야 함 (= 트리의 성질)3) Cycle을 포함하면 안된다  크루스칼(Kruskal) 알고리즘 - 최소 신장 트리(MST)를 구하는 알고리즘 중 하나- 매 순간 최소 가중치를 가지는 간선을 선택하여 연결하므로, 탐욕 알고리즘으로도 분류됨- 이때 Union-Find 알고리즘과 함께 사용하여 Cycle 형성되지 않을 경우 노드를 연결한다- 시간복잡도 : O(ElogE) - 실제 로직보다 간선 정보 정렬시 비용이 가장 큰 걸로 알려져..

문제 링크 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제 풀이 - 크루스칼 알고리즘으로 풀이시 메모리 초과 발생 - 행성의 개수 N이 최대 10^5 일 때 2중 for문 순회하면서 cost 연산 후 edge 추가시 최대 10^5 * 10^5 (러프하게 해석, 중복 제외시 연산은 더 적음)이고, Edge의 경우 class Edge {int from, int to, long cost} 로 정의시 (4byte ..

문제링크 https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제풀이 "빙산이 2 그룹이상 나눠지지 않고 모두 다 녹았을 때는 0을 출력한다" 조건을 이해하지 못해서 시간 소비 (반성) 절차 1) DFS 로 빙산 그룹을 카운팅한다. - 이때 빙상 그룹을 2그룹 이상 나누지 못하고 0이 된 경우 경우(모두 다 녹은 경우) 0을 출력하고 종료 - 빙상을 녹여 그룹 분할 하기 위해 while문 실행 2) BFS 사용하여 초기화시 빙산 위치를 넣어주..

문제링크 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제풀이 - 인접 리스트 사용해서 DFS 탐색 2번 수행 - 시간 복잡도 : O(V + E) 절차 1) 1번 루트 노드에서 가장 비용이 큰 리프(leaf)노드를 찾음 (= 지름에 해당하는 한점) 2) 찾은 리프 노드를 시작점으로 dfs 탐색을 한번 더 수행하여 구한 최대 cost가 트리의 지름이다 참고. 동일 문제 https://dev-ljw1126.tistory.co..

소수(prime)란? 1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수를 뜻함 (이때 1은 소수가 아니다) 예) 2, 3, 5, 7, 11, 13 ... 소수 판별 방법 방법1. 숫자 N이 주어질 때, 2 ~ (N - 1) 까지 수 중 나누어 떨어지는 수가 없으면 소수이다 - 1과 자기자신을 제외한 나누어 떨어지는 수가 없어야 소수이므로 반복문을 통해 구하는 가장 간단한 방법 - 시간복잡도 : O(N) - 단 범위가 너무 클 경우 시간 초과 발생 가능 private static boolean isPrime(int n) { // 2 ~ n - 1 사이 수 중 나누어 떨어지는 수가 있으면 소수 아님 for(int i = 2; i

문제 링크 https://www.acmicpc.net/problem/22254 22254번: 공정 컨설턴트 호석 거듭된 창업 성공을 이룬 류진국 사장은 이번에는 맞춤형 선물을 제작해주는 공장을 만들기로 했다. 현재 들어온 맞춤형 선물 주문은 총 $N$개이며, 각 맞춤형 선물마다 제작에 필요한 시간이 정 www.acmicpc.net 문제 풀이 - "모든 선물을 X 시간 내에 만들 기 위한, 공정 라인의 최소값" 으로 문제 해석하여 매개변수 탐색으로 풀이 - PriorityQueue 사용하여 공정 라인 수가 정해졌을 때 X 시간내 선물 생산 가능 여부 확인 (boolean) - 선물 개수 N =최대 10^5개, 제작 완료 X = 10^9 시간 제한 걸리고, 각 선물의 공정시간이 10^9일 때 공정라인은 10..

문제 링크 https://www.acmicpc.net/problem/22252 22252번: 정보 상인 호석 암흑가의 권력은 주먹과 정보에서 나온다. 주먹은 한 명에게 강하고, 정보는 세계를 가지고 놀 수 있기 때문에 호석이는 세상 모든 정보를 모으는 "정보 상인"이 되고 싶다. 정보 상인은 정보를 www.acmicpc.net 문제 풀이 - 해쉬맵, 우선순위 큐 사용하여 풀이 - 결과 최대치 long 최대치 생각해보기 - 쿼리 10만개가 주어지고, 고릴라가 10만 가치의 정보를 10만개씩 가지고 있고, 구매자가 10만개씩 구매한다면 .. 쿼리가 10만개 있을 때 5만개씩 상점에 정보 추가하고, 5만개씩 상점에서 구매자가 구매한다면 = 50,000 * 10^5 * 10^5 (int 범위 초과) - 고릴라 ..

문제 링크 https://www.acmicpc.net/problem/21278 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 문제 풀이 다익스트라 풀이 건물 중 두 개를 뽑는 조합을 구하고 다익스트라 알고리즘으로 최단 거리를 구한다. - N : 건물의 개수, 노드 수, 최대 100 - M : 도로의 개수, 간선 수, 최대 N * (N-1)/2 = 4950 - 100개의 건물 중 2개를 뽑는 조합 : 100C2 = 100 * 99 / 2! = 4950 - 다익스트라 알고리즘 시간 ..

문제 링크 https://www.acmicpc.net/problem/21276 21276번: 계보 복원가 호석 석호촌에는 N 명의 사람이 살고 있다. 굉장히 활발한 성격인 석호촌 사람들은 옆 집 상도 아버님, 뒷집 하은 할머님 , 강 건너 유리 어머님 등 모두가 한 가족처럼 살아가고 있다. 그러던 어느 날 www.acmicpc.net 문제 풀이 - 한달 지난 후 두번째 풀이 - 배열/정렬/해시맵/인접행렬과 같은 자료 구조를 활용하는 문제였다 예제 입력 7 -- 사람 수 daeil sangdo yuri hoseok minji doha haeun 7 -- 정보의 개수 hoseok sangdo -- X 의 조상은 Y이다 yuri minji hoseok daeil daeil sangdo haeun doha do..

문제 링크 https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 문제 풀이 - 스택 자료 구조 응용 문제 - 시간 복잡도 : O(N) 절차 1) 스택 선언하고 "(" 인 경우 스택에 추가한다. 2) ")"는 괄호일 때 2-1) 이전 괄호가 "(" 인 경우 레이저가 되므로, pop() 후 stack.size() 를 결과에 합산한다. 2-2) 레이저가 아닌 경우(=쇠막대 하나가 끝나는 위치) pop() 후 +1 을 결과에 합산한다. 예제입력 2 (((()(()()..

문제 링크 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 문제 풀이 - 다익스트라 알고리즘 - 시간복잡도 : O(ElogV) - s에서 출발하여 주어진 경로 g-h, h-g를 거쳐 최단 거리로 의심되는 노드에 도착하는지 파악하고, 경로를 거쳐 도착했을 경우 형식에 맞춰 출력하는 문제 처음 2차원 배열(int[][] dist = new int[노드][2]) 로 하여 풀이 하였는데 틀렸다 - 0번 인덱스에는 경로(g - h, h-g)를 거치..

문제 링크 https://www.acmicpc.net/problem/20010 20010번: 악덕 영주 혜유 FT온라인 게임에서 치열한 경쟁을 통해 영주가 된 혜유는 퀘스트를 받았다. 퀘스트의 내용은 자신이 관리하고 있는 마을 사이에 교역로를 건설하여 마을 간 교류를 활성화시키는 것이다. 이때, www.acmicpc.net 문제 풀이 최소 가중치를 가지는 MST는 구했는데, 두번째 값을 구하지 못해 3시간을 소비했다. 찾아본 결과 트리의 지름을 구하는 방법을 몰랐고, 문제 지문을 제대로 읽지 못해 MST 트리 정보를 활용하는 것을 파악하지 못했다..(반성) 문제 지문을 다시 보면 아래와 같다 마음이 괘씸한 혜유는 돈을 최대한 적게 쓰면서 퀘스트를 달성하려고 한다. 혜유를 도와서 (1)모든 마을과 마을을 ..

문제 링크 https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 문제 풀이 시간복잡도 - 상향식(Bottom-Up) 풀이시 O(N^2) = O(2000^2) - 하향식(Top-Down) 풀이시 O(N!) = O(2000!) 시간 초과 발생 가능 -> memorization 기법으로 시간내 풀이 가능 *팰린드롬 (PALINDROME) ? - 길이가 1일 때 자기 자신도 팰린드롬이다. (1, 2, 3, ...) - 길이가 2인 경우 두 숫자가 동일할때 팰린드롬이다. (11, 22) - 길이가..

문제 링크 https://www.acmicpc.net/problem/11049 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 문제 풀이 백준 11066 파일 합치기와 비슷한 문제였으나 행렬 곱셉을 어떻게 DP 배열로 처리할 지에 대해 파악하기 힘든 문제였다. - 상향식(Bottom-Up)으로 풀 경우 시간 복잡도 O(N^2) - 하향식(Top-Down)으로 풀경우 O(N!) , memorization 기법 활용하여 시간 내에 풀이 가능 - 최대치는 Integer 범위 - 행렬 A (m x k) ,..