IT 개발 돼지의 일상

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV140YnqAIECFAYD "Complete Binary Tree를 배열로 구현하고 탐색" 이 문제는 Complete Binary (완전 이진트리라고함.. full , complete, perfect 등에 번역이 헷갈려 영어로 기억함.) 의 중위 순회를 구현하는 문제이다. Complete binary tree 는 배열로 구현가능하며, 배열 안에서 인덱스로 특정 노드의 부모, 자식 위치를 구할 수 있다. 아래와 같다. 노드 i의 부모 : (i-1) /2 노드 i의 왼쪽 자식 : (2*i) +1노드 i의 오른쪽 자식 : (2*i) +2 참 쉽쥬? 그리고 중위 ..

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD"트리 구현" 트리를 구현하면된다. Complete Binary Tree 였다면 모두 배열에 넣고 좀더 쉽게 구할수 있었겠지만, 그냥 이진트리여서 그러지 못하고 트리를 구현했다. 대신 부모로 가는 경로를 쉽게 구하고자 해당 노드의 left, right 이외에 parent 변수도 함께 넣어줬다. 그렇게 한 후, A와 B의 공통 조상을 구하기 위해 A와 B의 조상을 번갈아가면서 찾으며 마킹을 했다. 이미 누군가가 지나간 노드의 경우 공통 조상이 되므로, 그 공통 조상을 구했고, 그 하위부터 다시 재귀적으로 공통 조상의 자식들을 l,r ..

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V1SYKAaUDFAWu "조합" 해당 문제는 어떤 row를 고를 것인지가 중요하다. 그리고 탐색한 결과를 모든 열이 k 개 연속된 숫자가 있는지 검사하는 것을 구현하는 것이 키포인트이다. 어떤 row를 고를 것인가는 조합과 같다. 바꾸는 row의 개수를 최소로 하는 값을 찾으면 되므로, 아래의 경우를 탐색한다. 그리고 만족하는 값을 찾았다면 결과 출력. 모두 바꾸지 않는 것 ~모든 행을 다 바꾸는 것 여기서 특정 row를 1 혹은 0 으로 바꾼 후에는 원래 상태로 복구 시켜주는 것이 필요하다. 마치 백트래킹 처럼.. 따라서 선택한 row를 0 혹은 1로..

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yC3pqCegDFAUx "와 어려웠다.인수분해" 처음엔 0~9 까지 숫자를 눌러 X를 구하려고 했다. 굉장히 구현이 잘 되지 않았다. 1 = 11*1 = 11*1*1 = 1 이런 경우 어떻게 처리할까.. 그래서. 약간의 기초적인 수학적인 지식이 필요했다. 어떤 수들을 곱해서 X가 만들어 졌고, X를 계속 인수분해 하다보면 계산기를 눌러 가능한 a * b *.. *... * 의 형태로 나올 것이다.. 따라서 해당 문제에서는 주어진 X값을 인수분해 하여 해당 a * b 의 형태로 바꾼 후에, a와 b를 계산기로 칠 수 있는지 확인하고, 그렇지 않다면 다시 ..

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIseXoKEUcDFAWN&categoryId=AWIseXoKEUcDFAWN&categoryType=CODE "그리디" 당연히 좀 더 큰 금액을 할인 받는것이 전체 금액이 최소가 된다. 따라서 주어진 가격을 내림차순 정렬하여 세 개 상품씩 그룹을 지어 가장 작은 가격을 더해 총 할인액을 구하는 것이 할인이 최대인것. 그리디. 내림차순 정렬하고 선택한다. 123456789101112131415161718192021222324252627282930313233343536373839404142import java.io.BufferedReader;import jav..

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWHPkqBqAEsDFAUn "구현... 다시보자! 꾸에에에엑" 다시보자... 왜 이런 생각을 못했을까. 처음에 그냥 브루트 포스로 전체 경우의 수를 재귀로 다 돌려보았다. 시간 초과. 풀이 참고해서 풀었따. 알고리즘은 아래와 같다. 1. 각 배점을 받을 때마다 최대값을 갱신한다.2. 갱신된 최대값 ~ 0 까지 탐색하며, 만약 이전에 이미 맞았던 점수가 있다면 이 점수에 내가 방금 입력받은 점수를 더해준 값도 체크한다.3. true 로 체크된 값들의 개수를 센다. 12345678910111213141516171819202122232425262728293031..

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15MeBKAOgCFAYD&categoryId=AV15MeBKAOgCFAYD&categoryType=CODE"이분 탐색 과 double.. 100~200 번만 돌리자." 이분 탐색을 통해 문제를 풀어야 한다. 근데 제한 없이 돌리다 보니 stackoverflow... 아래와 같은 게시물을 봄... 결론만 말하자면 double형을 가지고 이분 탐색을 할 경우 100~200 번 까지만 돌리도록 한다는 것이다. (https://www.acmicpc.net/blog/view/37) 1234567891011121314151617181920212223242526272..

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc "가장 많이 열리는 걸 열고, 그다음에 차근차근." 알고리즘 기본 로직은 맵에서 주위에 지뢰가 없는 칸을 탐색해 먼저 클릭하여 해당 칸을 오픈한다. 이렇게 오픈된 나머지 8칸에 대해서도 똑같은 검사를 한다. 이렇게 하여 주위에 지뢰가 없는 칸들이 모두 없어 지게 되고, 그 후에 남아있는 칸들의 수를 세서 최종 값을 더한다. 이때, 지뢰가 없는 칸의 탐색은 BFS를 통해 한다. 더해서 아래 큐에 들어가는 중에 중복이 생겨났었고, 시간초과가 났다. 탐색은 중복을 줄이는 것이 정말 중요하다. visited 배열을 두어 다시 들어가지 않..

출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7I5fgqEogDFAXB "무식한 DFS" 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.HashSet;import java.util.Set;import java.util.StringTokenizer;p..

출저 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV4yLUiKDUoDFAUx "DFS와 가지치기" DFS를 이용해 해당 위치의 명령을 수행한다. 이 때, '?' 명령의 경우 4방향 dx,dy 에 대해 모두 탐색해 준다. 가능한 경우가 나왔을 때는 boolean 변수 find를 true 설정해주어 더이상 탐색하지 않도록 한다. 범위가 벗어날 경우 문제에서 제시한 예외처리를 해주는 것도 중요하다. 일일이 x,y 좌표가 범위를 벗어난 경우를 체크하자. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474..