짱아의 개발 기록장

DP가 아닌, BFS로도 풀 수 있는 문제이다. 행과 열의 값이 최대 1000이기 때문에 무리 없이 풀 수 있지만, DP로 풀기에 최적화된 문제라고 생각한다. 토끼가 →, ↘, ↗ 방향으로만 이동할 수 있기 때문에 현재 위치에서 그 전의 지점에서 올 수 있는 경로를 파악하여 dp값을 계속적으로 3지점의 최대값으로 갱신해주는 식으로 구현했다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465// 토끼가 정보섬에 올라온 이유#include #include using namespace std; int n, m, startX, startY;str..

인접리스트를 활용한 BFS문제이다. 인접리스트로 친구관계를 모두 형성해놓고 bfs를 통해 level이 얼마나 형성되는지 점수를 매기면 된다. 1~N까지 사람마다 bfs를 돌아서 점수를 매겼고 가장 적은 점수를 가진 사람을 찾았다. 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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 // 회장뽑기 #include #include #include #include using namespace std; int..

프로그래머스에도 동일한 문제가 있다. 하지만, 차이점이라고 한다면 백준 문제는 입력값의 범위가 훨씬 크기 때문에 잘 고려해서 코드를 구현해야한다. [메인 로직] 먼저, 모든 경우의 수 중에서 가장 최악의 시간이 나올 경우를 찾는다. ex) [7, 10], m = 6이면 최악의 시간은 10분이 걸리는 심사관에게 6명 모두가 입국심사를 받는 경우가 될 것이다. 그러면 최악의 시간은 총 60분이다. Start = 0, End = 60(최악시간)으로 하고 이분탐색을 시작하면 된다. mid = (Start+End)/2로 잡고 mid의 시간일 때 총 검사할 수 있는 인원의 수를 구한다. 30/7+30/10 = 7은 m=6의 값보다 크기 때문에 End = mid-1로 이분탐색을 쭉 진행하면 된다. [중요한 포인트] ..

DFS와 DP를 활용한 대표적인 문제이다. it회사들에서 이러한 유형을 좋아하는 것 같다. 물론 it회사 뿐 아니라, 모든 회사에서? 그래서 연습을 많이 해두면 좋을 것 같다. 사이클이 형성되면 무한대로 이동이 가능하다는 것을 의미하기 때문에 사이클 형성여부를 visited배열로 표시해주었다. 즉, 이미 방문한 점을 또 방문한다면 => 사이클을 형성한 것이기 때문에 바로 -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 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59..

2020네이버 하반기 토요일 공채 코딩테스트 3번으로 나왔던 문제와 매~~~우 유사한 문제이다. 이 문제의 핵심은 당연하게도 점화식을 세우는 것인데 최소값을 구하는 것이 핵심이다. 최대값은 사실 규칙만 잘 파악했다면 바로 구할 수 있다. 구체적인 해설은 아래 블로그를 참고하면 더 좋을 것 같다. escapefromcoding.tistory.com/147 3687 : 성냥개비 ( 백준 / java ) www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 escapefromcoding.tistory.com 아래 코드에서 중요한 부분은 2가지..

문자열 처리의 대표적인 문제 유형이다. 문자열 처리하고 정렬을 해주면 바로 풀린다. 중간에 예외처리만 잘 해준다면 어렵지 않다. 딱히 설명은 필요없이 코드를 참고하면 충분히 이해가능할 것이다. 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 #include #include #include #include #include using namespace std; vector solution(vector files) { vector answer; vector tmp; map m; for(int i=0; i

치즈 내부에 있는 공간을 표시해주어서 외부 공기와 구분해주는 작업이 가장 중요한 것 같다. 어차피 테두리에는 치즈가 없다는 조건이 있기 때문에 (0, 0)에서 BFS를 시작해서 인접한 모든 외부 공기들의 isInside값을 false로 해주었다. 따라서, isInside가 true인 공기(내부 공기)와 인접한 것은 외부공기와 접하지 않았다고 간주했다. 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 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70..

DP...역시 쉽지 않다. 예전에 풀었던 동전 문제와 유사해서 점화식을 비교적 쉽게 세울 수 있었다. DP[선택한 수의 개수][총 합]이라고 가정했을 때 DP[k][n]을 만들기 위해서 맨 마지막에 뽑은 수가 L이라고 한다면, DP[K][N] = Σ(DP[K-1][N-L]) L => 0 n>>k; // 1개 선택했을 때 for(int i=0; i