📍문제 링크https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)www.acmicpc.net 📍알고리즘 분류- 다이나믹 프로그래밍 - 배낭 문제 📍문제 풀이배낭 문제(Knapsack Problem) 로 알려진 유명한 문제 - 메모이제이션을 이용하지 않으면 시간이 매우 매우 오래걸린다 - DP를 이용하면 O(N * K) 로 해결 가능 데이터 수 N과, 최대 배낭의 무게 K가 주어진다. N개의 줄에 아이템의 무게 W, ..

📍문제https://school.programmers.co.kr/learn/courses/30/lessons/12900 📍풀이: DP로 경우의 수 메모이제이션타일을 배치하는 경우의 수를i. 세로 타일로 시작할 때 (| 모양 스타트)ii. 아닐 때 (= 모양 스타트) 크게 이렇게 구분할 수 있음 n = 1 이라면i. 1ii. 0-> 1 n = 2 i. 1ii. 1-> 2 n = 3i. n = 2의 경우의 수 (2) (| 모양 채웠으므로 나머지 2개 영역만 채우면 됨)ii. n = 1의 경우의 수 (1) (= 모양 채웠으므로 나머지 1개 영역만 채우면 됨) n = 4i. n = 3의 경우의 수ii. n = 2의 경우의 수 n = 5i. n = 4의 경우의 수ii. n = 3의 경우의 수 그렇다면 f(n)..

📍문제 링크 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 📍알고리즘 분류 - 구현 - 그래프 이론 - 그래프 탐색 - 너비 우선 탐색 - 시뮬레이션 📍문제 풀이 구현할 내용이 엄청 많고 복잡했다.. 프로그램 동작 기능 1. board를 탐색하여 인구 이동의 가능성이 있으면 인구가 이동될 좌표들 그룹을 구한다 - 인구 이동 가능성은 중첩 for 문을 활용하여 판정 - 인구가 이동될 좌표들 그룹을 구하기 위해 방문/미방문 좌표를 ..

📍문제 링크 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 📍알고리즘 분류 - 구현 - 그래프 이론 - 그래프 탐색 - 너비 우선 탐색 - 시뮬레이션 📍문제 풀이 - width, height 정보가 주어지고, 0과 1로 이루어진 2차원 배열의 정보가 주어진다 2차원 배열의 0은 공기, 1은 치즈를 의미한다 2차원 배열의 가장자리는 0이다 - 1시간이 지날 때마다 공기중에 노출된 치즈가 녹는다고 할 때, 치즈가 다 녹는데 걸리는 시간과, 마지막 치즈 면적을 구하라..

📍문제 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 📍알고리즘 분류 - 브루트포스 - 백트래킹 📍문제 풀이 4 이상의 양수 N과 2차원 배열이 주어질 때, 1 ~ N 까지 숫자들을 절반으로 나누는 가짓수를 구하고 각각 비교한다 비교 방법) 집합에서 nP2 (순열) 을 구해서 그 좌표를 2차원 배열의 좌표값으로 사용해 모두 더한 것의 최소값을 비교하여 가장 최소값을 출력 1 ~ N 까지 숫자들을 절반으로 나누기 : 백트래킹 이용하여 배열 구하기 백트래킹으로 ..

📍문제 링크https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으www.acmicpc.net 📍알고리즘 분류- 자료구조 - 스택 📍문제 풀이문제 요구사항은 쉽지만, N이 최대 8만에 달하기 때문에, O(N^2) 로는 해결할 수 없다 - 시간복잡도를 낮추기 위한 방법이 필요하다 배열을 순회하며 stack 길이만큼 반복문 수행 스택의 최신 값이 현재값보다 같거나 작으면, pop 실행, 아니면(가려져서 안보이므로) 종료 반복문 종료후 스택의 길이를 답에 더한다 그리고 스택에 현재..