짱아의 개발 기록장

전형적인 Tree문제이다. InorderTraversal(중위순회)을 통해서 col값을 ++해주고 dfs를 통해서 인자값으로 넘긴 level을 기준으로 height[level]값에 해당 col값을 차례대로 넣어주었다. 이후에는 1~maxHeight값을 탐색하며 level별로 너비를 구해주며, 최대 너비를 구했다. 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 // 트리의 높이와 너비 #include #include #include using n..

유니온파인드를 사용하는 대표적 문제이다. 문제는....cin, cout이 진짜 느리다는 것을 실감한 문제^^ cin, cout을 쓰니까 맞왜틀이어서 질문 검색란을 찾아보니 똑같은 문제에 시달리시는 분들이 계셔서 ㅋㅋㅋ ios::sync_with_stdio(0); cin.tie(0); 써서 해결했다. 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 // 집합의 표현(1717번) #include #include using namespace std; int n, m, a, b, c; int connect[1000002] = {0, }; in..

문자열에 순열을 가미한 문제였다. 가장 놓치지 쉬운 부분이 MAX의 초기값 설정에 관한 부분이었는데... 최대값도 음수가 될 수 있다는 점!!!! 그래서 최대값도 0이 아니라 -INT_MAX값으로 초기화 해주어야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455#include #include #include using namespace std; int n, op;char oper[4] = {'+', '-', '*', '/'};int num[101] = {0, };vector v;int MIN = 987654321, MAX = -987654321; int cal(){ ..

이 문제는 실제 N* 게임회사에서 나왔던 코딩테스트 문제와 거의 99%일치하는 문제였는데.... 아쉽게도 시험에서는 풀지 못해서 백준에서 유사한 문제를 기여코 찾아내서 풀었다...ㅎㅎ 처음에 봤을 때는, 중학교때 풀었던 경우의 수? 같은 문제여서 대충 DP로 푸는 문제구나 싶었긴 했는데.... 결국은 아래 블로그의 풀이를 참고해서 풀었다..;; (DP는 왜 이렇게 어려울까?ㅎㅎ) blog.naver.com/occidere/220784778900 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 #include #include using namespace std; int n, k; int dp[10001] = {0, }; vec..

여러가지 방법으로 구현해볼 수 있는 문제였다. 보니까 다들 dp, 그리디, 재귀 등 다양한 방법으로 풀었다. [메인 로직] 1 | 2 | 3 | 4 ... | n-1 | n 까지 for문으로 탐색하면서 다음으로 (지금 날짜+걸리는 날)만큼 더한 날짜로 넘어가서 최대값을 찾는다. 아무래도 코드를 보면 더 이해가 잘 될 듯하다. 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 // 퇴사 #include #include using namespace std; int n, days, cost; vector v; int ans = 0; void dfs(int d..

재귀와 dp를 함께 사용하는 아주 전형적인 문제 중 하나이다! 어느정도 난이도도 있으면서 감을 잡기 좋은? 문제인 것 같다. [메인 로직] dp배열을 -1의 값으로 초기화해놓고 판다가 출발하는 좌표보다 더 많은 대나무를 가지고 있는 영역의 dp값을 가져와서 +1씩 더하는 논리로 구현했다. 가지치기를 할 수 있는 부분이 바로 dp값이 -1이 아닌 경우는 이미 이전에 방문을 해서 그 영역에서 최대 몇 일을 버틸 수 있는지 메모이제이션을 해놓은 것이기 때문에 연산을 하지 않고 return dp[x][y]을 하고 바로 넘어갈 수 있다. (-> 매우 시간 절약!) 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 ..

모기업 코드페스티벌에 참여했는데,,,, 유일하게 풀지 못했던 문제;;;; ㅂㄷㅂㄷ 팰린드롬인지 아닌지를 판별하는 문제는 쉽게 풀었었는데 만드는 문제는 처음 접해서 당황했다.... 끝나고 백준을 찾아보니 역시나 똑같은 문제가 있었다 ㅋㅋㅋ 그래서 다른 분의 코드를 참조해서 다시 풀어보았다! [메인 로직] 해결방법은 인덱스가 0인 지점부터 차례대로 조사하며 팰린드롬이 되는 최소한의 시작 위치를 찾는 것이다. 어차피 중간에 팰린드롬이 생기는 것은 아무 의미가 없기 때문에특정 인덱스부터 문자열의 맨 마지막까지 팰린드롬이 되는 부분 문자열을 찾으면, (특정인덱스+원래 문자열의 크기)가 최소 팰린드롬의 길이가 되는 것이다. aabcaa인 경우에는 맨 뒤의 aa만 팰린드롬이 가능하다 따라서 aa는 그대로 두고 나머지..

n의 크기가 크지 않아서 n^2으로 푸신 분들도 계시겠지만 글쓴이는 nlogn LIS 알고리즘을 사용하여 풀었습니다. 특히, 이 문제는 요소들을 구해야 하기 때문에 LIS 요소 역추적하는 부분도 구현했습니다. 블로그에 LIS 요소 역추적하는 방법에 대해서도 포스팅 했으니 참고바랍니다. jungahshin.tistory.com/7 [Algorithm] LIS 요소 역추적하기(backtracing) 실제 LIS 알고리즘을 통해 생성된 백터는 실제 LIS를 나타내지 않습니다. 그렇기 때문에 LIS를 이루는 원소들을 알아내기 위해서는 추가 과정이 필요합니다. 아래 문제가 LIS 요소 역추적을 연습하� jungahshin.tistory.com 코드 첨부 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..