짱아의 개발 기록장

트리를 DFS와 DP를 활용해서 푸는 문제이다. 트리를 DFS로 구현하되, 시간 절약을 위해서 DP를 사용한 형태이다. 가장 핵심 아이디어는, 내가 얼리어답터이면 -> 자식이 얼리어답터이던 아니던 상관없다. 내가 얼리어답터가 아니면 -> 자식은 반드시! 얼리어답터이어야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364// SNS#include #include #include using namespace std; const int MAX = 1000001;int n, u, v;vector connect[MAX]; // 친구 관계vecto..

가장 최소의 수를 구하는 그리디 문제였다. dp를 사용해서 푸는 방법도 있지만, 직관적으로 판단한다면 더 쉽게 풀 수 있다. 5로 나누어떨어지지 않는다면, 2를 계속 빼는 식으로 계산했다. 최종적으로, 5로 나누어 떨어지지 않아서 while문을 빠져 나왔다면 1) 2로 나누어떨어지는 경우이거나, 2) 아예 2와 5로 떨어지지 않는 수이다. ex) 3, 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 // 거스름돈 #include #include using namespace std; int n; vector v; int dp[100001] = {0, }; int main() { cin>>n; int c..

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