for IF

📌 문제백준 | RGB거리 | SILVER 1 | DPhttps://www.acmicpc.net/problem/1149  📌 문제 탐색하기RGB 거리에는 집이 N개 존재거리는 ‘선분’1~N번 집 존재빨, 초, 파 중 하나의 색⇒ 각 비용이 존재할 때, 모든 집을 칠하는 비용의 MIN 값 구하기 규칙 :1번 집 색상 ≠ 2번 집 색상N번 집 색상 ≠ N-1번 집 색상i 번 집 색상 ≠ i-1 (2≤i≤n-1)i 번 집 색상 ≠ i+1 (2≤i≤n-1)입력 :N (집의 수)집을 빨, 초, 파로 칠하는 비용 (1~N번 순서로)출력 :모든 집을 칠하는 비용의 MIN 값   📌 알고리즘이전의 계산 결과가 이 후의 계산에 영향을 주므로, DP를 활용해서 문제를 풀어야한다.DP를 풀땐, 규칙이 가장 중요한데…이..

📌 문제백준 | 자원캐기 | SILVER 2 | DPhttps://www.acmicpc.net/problem/14430  📌 문제 탐색하기제한된 범위 내에서 자원을 탐색(1,1) 부터 (N,M)까지 자원을 탐색오른쪽, 아래쪽으로 한칸 이동 가능(x,y)에 자원이 있는 경우에만 해당 자원을 채취 가능 입력 :n (세로길이 = 행), m(가로길이 = 열)n행 m열에 걸쳐 탐사영역자원 = 1, 땅 = 0출력 : 탐색할 수 있는 자원의 최대 숫자를 구하기   📌 알고리즘N과 M이 최대 300이므로, 땅의 크기는 최대 90000까지 가능만약, 완전탐색으로 접근할 경우, N,M까지 가는 경우 O(300^2) + 최대 가지의 수임DP를 통해서, 최대 광석의 개수를 계속해서 업데이트한다면?example) DP[i..

📌 문제백준 | 1, 2, 3 더하기 | SILVER 3 | DPhttps://www.acmicpc.net/problem/9095   📌 문제 탐색하기n이 있을 때, 1,2,3의 합으로 나타내는 방법의 수를 찾기합은 1개 이상 사용해야한다.   📌 알고리즘방법이 존재하는 경우들을 모두 세야하므로, DP를 활용해야한다.DP는 그 이전의 결과값을 바탕으로 쓸 수 있으므로, 해당 값을 이용해야한다.DP[0] = 0DP[1] = 1DP[2] = 2DP[3] = 4DP[4] = 7 (=1+2+4)DP[5] = 13 (=2+4+7)DP[6] = 24 (=4+7+13)DP[7] = 44 (=7+13+24)DP[10] = 274 즉, DP[i] = DP[i-1] + DP[i-2] +DP[i-3] (i ≽ 4) ?..

📌 문제백준 | 적록색약 | GOLD 5 | 완전탐색https://www.acmicpc.net/problem/10026   📌 문제 탐색하기N*N크기의 그리드R, G, B 가 그리드에 존재구역이 나뉘어 있고, 같은 색으로 있음같은 색상이 상하좌우로 인접 ⇒ 두 글자는 같은 구역에 속함적록색약 = 빨간색과 초록색의 차이를 거의 느끼지 못함 (빨강과 초록을 하나로 보는 것)example)RRRBBGGBBBBBBRRBBRRRRRRRR적록색약 x = 4구역적록색약 o = 3구역 출력 : 적록색약 아닌 사람이 본 구역의 수, 적록색약인 사람이 본 구역의 수   📌 알고리즘적록색약 및 적록색약 x 사람이 보는 색의 구역을 모두 확인해야하므로, ‘BFS’ 완전탐색을 사용한다.N이 100이하이므로, 2차배열을 사..

📌 문제백준 | 버섯농장 | SILVER 1 | 완전탐색https://www.acmicpc.net/problem/27737  📌 문제 탐색하기N * N 칸으로 이루어진 나무판버섯이 자랄 수 있는 칸버섯이 자랄 수 없는 칸M개의 버섯포자 (자랄 수 있는 칸에 배치)포자가 심어진 칸을 포함해 최대 K개의 연결된 칸에 버섯이 자람상하좌우로 적어도 한 변을 공유하는 칸들한 칸에 여러개 겹쳐서 심을 수 있음ex) x개의 버섯 포자 겹쳐서 = x * K개의 연결된 칸에 버섯 입력 : N(크기), M(버섯 포자 개수), K(연결)0 : 버섯 자랄 수 O1 : 버섯 자랄수 X출력 : 농사가 가능할 경우, 남은 버섯 포자의 개수농사 가능 = 버섯이 자랄 수 있는 모든 칸에 버섯이 전부 자랐을 때 농사가 가능   📌..

📌 문제백준 | 폴짝폴짝 | SILVER 2 | 완전탐https://www.acmicpc.net/problem/1326  📌 문제 탐색하기징검다리에 숫자 존재징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로 감a번째 징검다리에서 b번째 징검다리로 이동출력 : 최소 몇 번 점프를 하여 b번까지 가는지   📌 알고리즘‘최소’ 의 점프를 구해야하므로, 완전탐색(DFS/BFS)를 사용할 예정DP와 같은 경우에는 ‘누적’된 정보들을 바탕으로 풀어야하는데, 이전 상태값에 의존하는 것은 아니므로 DP로 하지 않아도 될 것이라 생각했다.징검다리의 개수 N이 10,000까지 존재하므로 O(N^2) = 100,000,000  📌 코드 설계하기N, A, B 입력받기BFS를 통해앞으로 가는 경우뒤로 가는 경우→ ..

📌 문제백준 | 후보 추천하기 | SILVER 1 | 시뮬레이션https://www.acmicpc.net/problem/1713  📌 문제 탐색하기학생회장 후보 = 일정기간동안 전체 학생의 추천 수홈페이지 사진틀의 수 = 후보의 수모든 사진틀 empty어떤 학생 → 특정 학생 추천 : 추천받은 학생이 사진틀에 게시모두 full → 추천받은 횟수가 가장 적은 학생의 사진을 삭제 & 새롭게 추천받은 학생 게시 (OS 페이징 기법 중, LFU)만약, 2명 이상 = 게시된 지 가장 오래된 사진을 삭제(OS 페이징 기법중, LRU)게시된 학생이 다른 학생의 추천을 ‘또’ 받으면, 추천 횟수 +1if 삭제되는 경우 = 추천횟수는 0으로 변경출력 : 최종 후보 (제일 추천이 많은 후보)example)2 1 4 3..

📌 문제백준 | 줄세우기 | GOLD 4 | DP, 이진탐https://www.acmicpc.net/problem/2631 📌 문제 탐색하기일반적인 정렬 알고리즘은 최대 O(NlogN) ~ O(N^2) 까지 될 수 있어서… 비추하는 방법일 것 같은데문제에서 N이 고작 200이하의 정수라고 주어졌고시간제한이 1초라면, 최대 40000 즉, 1초도 안넘을 것임 ⇒ 그러므로 일반 정렬 사용해도 괜찮다.근데 문제는,,, ‘정렬’을 하는 것이 아니라, ‘최소 몇 번으로 이동 가능’이므로 ‘DP’로 풀어야할 것.3 7 5 2 6 1 4 - 3 5 63 7 4 5 2 6 1 (4번 이동) - 34563 4 5 2 6 1 7 (7번 이동) - 345671 3 4 5 2 6 7 (1번 이동) - 1 3 4 5 6 7..

📌 문제백준 | 파도반 수열 | SILVER 3 | DPhttps://www.acmicpc.net/problem/9461 📌 문제 탐색하기정삼각형이 나선(오른쪽 시계방향)으로 계속 돌면서 모양을 만듬  📌 알고리즘P(N)이 구현되는 모습이, 그 전의 값들로부터 영향을 받아 구현되기 때문에 이 문제는 ‘DP’ 알고리즘으로 풀 수 있다.이를 구현하기 위해, Memoization 을 활용한다.example) P(N) = 1, 1, 1, 2, 2, 3, 4, 5, 7, 9N012345678P(N)011122345       P[1] + P[5]P[2] + P[6]P[3] + P[7]즉, P(N) = P(N-5) + P(N-1) (단, N>=5)  📌 코드 설계하기TEST 입력MEMOIZATION 기법을 ..

📌 문제백준 | 가장 큰 증가하는 부분 수열 | SILVER 2 | DPhttps://www.acmicpc.net/problem/11055 📌 문제 탐색하기증가하는 부분 수열 중, 합이 가장 큰 것 구하기ex) A = {1, 100, 2, 50, 60, 3, 5, 6, 7, 8}⇒ 1,2,50,60 = 113⇒ 3, 5, 6, 7, 8 = 29그러므로 가장 큰 증가하는 부분 수열은 113  📌 알고리즘부분수열을 구해야하는데, A의 크기가 1,000까지 가능만약 for문을 통해 돌 경우, 1000 * (1000 - i) (i = 자신의 위치)시간이 1초제한이므로, 1000000 - 1000i라 가능할 것 같긴한데.. => 너무 비효율적인 것 같아서 PASS어쨌든, 최대 합인 부분수열을 골라야하므로, ..