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

소수(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/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) ,..

문제 링크 https://www.acmicpc.net/problem/1949 1949번: 우수 마을 N개의 마을로 이루어진 나라가 있다. 편의상 마을에는 1부터 N까지 번호가 붙어 있다고 하자. 이 나라는 트리(Tree) 구조로 이루어져 있다. 즉 마을과 마을 사이를 직접 잇는 N-1개의 길이 있으며, www.acmicpc.net 문제 풀이 - 인접 리스트 사용하여 시간 복잡도 O(V + E) = O(10,000 + 9,999) - 트리이기 때문에 간선의 수 = 노드의 수 - 1 - DFS 방식으로 리프 노드 구하는 문제에서 응용하는 문제로 2차원 배열로 방문 여부에 따라 조건 처리를 하게 된다 - 시작 노드는 1로 해서 최종적으로 DP[1][0], DP[1][1] 중 최대값이 최대 인구에 해당한다 DP..

문제 링크 https://www.acmicpc.net/problem/1509 1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제 풀이 스스로 풀지 못하여서 기술 블로그를 참고 하였고, 이번 문제를 통해 DP 기법과 Two Poiner 기법 응용하는 방식에 대해 처음으로 알게 되었다. 풀이 후 몇일 있다가 손으로 그려보고 Top-Down, Bottom-Up 풀이하는데 역시나 쉽지 않은 문제인 것 같다. 가짜문제 정의, 초기화 항목 .. 단순히..

요구사항 로컬 개발 환경에 설치한 HTTP 웹 서버를 물리적으로 떨어져 있는 원격 서버에 배포해 정상적으로 동작하는지 테스트한다. 이때 HTTP 웹 서버 배포 작업은 root 계정이 아닌 배포를 담당할 새로운 계정을 만들어 진행한다. ① 계정 추가 및 sudo 권한 할당② 각 계정별 UTF-8 인코딩 설정해 한글 이슈 해결③ JDK, 메이븐 설치④ Git설치, clone 및 빌드⑤ 방화벽 설정(ufw)⑥ 소스 코드 재배포 참고. AWS 사용할 경우 아래 링크 참고 (p83)https://opentutorials.org/module/1946 참고. 영상 자료https://www.youtube.com/watch?v=dWGzApCuF9Mhttps://www.youtube.com/watch?v=N8iLAuAo-..

문제 링크 https://www.acmicpc.net/problem/15681 15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 문제 풀이 - 시간 복잡도 O(V + E) // 인접 리스트 사용 - 백준 링크에 들어가보면 하단에 친절하게 로직을 설명하고 있어 참고하면 됨 # 입력 트리를 그릴 경우 5번 Root 기준 5 4 6 3 7 8 9 1 2 # subtree 결과 subtree [0, 1, 1, 3, 4, 9, 4, 1, 1, 1] 제출 코드 ..

문제 링크 https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 - 시간 복잡도 : O(N) - 1,2,3 더하기 문제에서 조금 변형된 문제, 상향식, 하향식 연습하기 좋은 문제 - 단, 같은 숫자를 연속적으로 붙일 수 없기 때문에 이전 숫자에서 무엇이 사용되었는지 상태값을 기록할 필요가 있다 (2차원 배열 사용) - 간단하게 2차원 배열로 해서 1 ~ 3 숫자 사용 여부를 표기하고 동일하게 점화식으로 구하면 됨 - 최대치 long DP[N + 1][4] 2차원 배열 생성 ( DP[N][1..

문제 링크 https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1

문제 링크 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 풀이 - 입력의 경우 int 배열로 100개까지 받으므로 400byte - 연산에 필요한 DP의 경우 행20 * 100 * 8byte = 16KB 정도 메모리 잡음 - 최대치의 경우 출력에 2^63 -1 명시되어 있기 때문에 long으로 처리 시간 복잡도 상향식 (Bottom-Up) 하향식(Top-Down, 재귀 함수) O(N * 20) O(2^n) = O(2^100) - ..

문제 링크 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 문제 풀이 - 시간복잡도 : O(N) - 점화식 DP[N] = DP[N - 2] + DP[N - 1] 형태로 최대 N이 90까지 가능하다 - 피보나치의 경우 46번째만 넘어가도 29억이 넘기 때문에 long (8byte, 64bit)으로 문제 풀이 해야 함 풀이 순서 가짜 문제 정의 - 가짜 문제로 정답을 구할 수 있는가? - 초기항 - 점화식 - 풀이 & 테스트 0 1 2 ..

문제 링크 https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 문제 풀이 - 시간 복잡도 O(N) - 메모리 제한 4MB 직접 문제를 풀었을 때 최대 값을 구하는 것은 Bottom-Up방식으로 설명에 따라 그대로 하였기에 구할 수 있었다. 그러나 최소 값의 경우 구할 수 없었고, 기술 블로그를 찾아 본 결과 '메모리 제한', '슬라이딩 윈도우 기법'와 같은 파악하지 못 한 부분에 대해서도 확인할 수 있었다. (최소값의 경우 반대로 선택 가능 범위 내에 최소 값을..

문제 링크 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 풀이 해당 문제의 경우 직접 풀이하지 못하고, 기술 블로그를 참고하여 풀 수 있도록 하였습니다. 2차원 배열 DP로 풀이시 문제가 되었던게 '0 ~ 9의 숫자를 사용한 여부는 어떻게 알 수 있을까' 였습니다. 3차원으로 변경하여 0 ~ 9 까지 체크했는지 반복문으로 사용해서 할 경우 그거대로 더 복잡해 질거 같은 생각이 들었습니다. 기술 블로그를 찾아본 결과 해당 문제는 '비트 마스킹' 기법을 사용하여 문제 풀이 가능한 것을 알게 되었고 2~3일간 이해가 되지 않아 시간을 보냈고, 지금은 이해한 내용을 ..

문제 링크 https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net 문제 풀이 - 시간복잡도 O(N) - 최대치의 경우 9907에 대한 나머지를 구하라 하므로 Integer로 예상 가능 (문제 설명에 나머지 처리 없는 경우 최대치 잘 파악) 2 * 1 일때 0 의 경우 아무것도 없는 경우 1의 경우 왼쪽에 사자가 있는 경우 🦁 2의 경우 오른쪽에 사자가 있는 경우 🦁 2 * 2의 경우 1) 앞에 블록에 빈 우리 더할 경우 : 3가지 🦁 🦁 2) 왼쪽에 사자🦁가 있는 우리를 추가하는 경우 : 2 가지 빈 우리 아래에 추가하거나 🦁 오른쪽에 사자가 있는 우리 밑에 추가 할 수 있다 🦁 🦁 ..

문제 링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 문제 풀이 - 시간 복잡도 O(N), 최대치 Integer 범위 내 - 스티커 하나를 뜯을 경우 상하좌우로 찢어져서 사용할 수 없게 됨 - 2 x N열 스티커, 2차원 배열 형태의 DP 문제 초기화 1 DP[0][i] 50 DP[1][i] 30 0번행의 2열 스티커를 뽑을 경우 아래 선택가능한 영역에서 최대치를 뽑아 더해주면 됨 0 1 2 O 스티커 선택 O O 1번행의 2열..

문제 링크 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 문제 풀이 - 시간 제한 0.5초 이므로 완전 탐색으로 풀 경우 시간 초과 발생 - 첫번째 집의 RGB 값으로 초기값을 설정하고, 동적 프로그래밍으로 풀이한다 - 최종적으로 DP[N][1 ~ 3] 값 중 최소값 출력 - 시간복잡도 : O(N) 점화식 DP[i][j] = Math.min(DP[i - 1][x], DP[i - 1][y]) + RGB[i][j] (이때 i..

문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net문제 풀이 - 시간복잡도 O(N)- 초기항 구하고, N번째 포도주에 대해 아래 3가지 경우를 비교하여 최대 값 구함  이때 3번 연달아 포도주를 마실 수 없다는 규칙에 따라 DP 테이블을 갱신한다 i번째 포도주를 마시지 않는 경우① DP[i - 1]할당 i번째 포도주를 마시는 경우② i - 1 번째 포도주 먹고 마시는 경우 최대치 (DATA[i - 1] + DP[i - 3])③ i - 2 번째..