전위 순회, 중위 순회, 후위 순회란 무엇인가? 전위 순회 루트 노드가 가장 먼저 나오는 순회 방식 Root -> Left -> Right 자기 자신 -> 왼쪽 자식을 방문 -> 오른쪽 자식을 방문 중위 순회 각 루트 노드가 자식 노드의 사이에 위치 Left -> Root -> Right 왼쪽 자식을 방문 -> 자기 자신 -> 오른쪽 자식을 방문 후위 순회 루트 노드가 가장 마지막에 출력 Left -> Right -> Root 왼쪽 자식을 방문 -> 오른쪽 자식을 방문 -> 자기 자신 접근 방법 DFS를 이용한 구현 왼쪽, 오른쪽을 구분할 수 있는 2차원 배열 생성 배열 안에 값을 알파벳 말고 숫자로 담은 후 출력만 알파벳으로! 구현 전위 순회: DFS를 시작했을 때, 그 값을 먼저 출력하고 계속 파고드..
첫째 줄에는 체스판의 한 변의 길이 둘째 줄에는 나이트가 현재 있는 칸 셋재 줄에는 나이트가 이동하려는 칸이 주어진다. 0, 0에서 시작해서 -> 7, 0 도착 최소 몇 번만에 이동할 수 있는지 확인하는 문제다. => BFS를 이용해서 최솟값을 구하자 처음 나이트가 이동할 수 있는 경우의 수, 가운데 시작에서 나이트는 저렇게 이동할 수 있음을 알고 시작하자. col, row / col2, row2를 따로 나누었다. 2차원 배열을 생성해서 예를 들어보자. 이런식으로 이동할 수 있음을 나타낸다. 두 번째, col2와 row2를 이용했을 때 이동할 수 있는 예를 들어보자. 이렇게 이동함을 알 수 있다. 그럼 이제 같이 이동했을 때를 나타내보자 겹칠 일이 없이, 내가 이동할 수 있는 좌표를 Queue에 담고 한..
= 접근 방법 = NxN 배열 A A[i][j] = i * j 이 수를 일차원 배열 B에 넣으면 B의 크기는 NxN이 된다. B[k]를 구해보자 N = 3, B = 7일 때 b[7] = 6이 문제에서 주어졌다. 문제를 그래도 만들어보자, int[][] A = new int[3][3] 그동안 우리가 해왔던 이분 탐색 문제들은 단순하게 주어진 값을 이용해서 반으로 나누는 식으로 어떻게든 2중 for문 시간 복잡도 O(N^2)이 아닌, O(logN)형식으로 만들면 되는 거였다. 이 문제가 어려운 이유는? => 지금까지 풀어왔던 틀에서 완전히 벗어나 새로운 규칙을 발견하고 응용해야 된다. 입력) 배열의 크기 N이 주어진다. N은 105보다 작거나 같은 자연수 이 문장을 봤을 때, 순수하게 배열을 그대로 만든다면..
= 문제 접근 방법 ( 틀림 ) = 내가 접근한 방법은 공유기를 하나 하나 다 설치해보고 그거에 최댓값을 찾는 식으로 했었다. 애초에 끝까지 구현도 못한 방식이라 어떻게 말해야 될지 모르겠다.. 이분 탐색 파트에서 1번 2번 문제는 이해했고 어떻게 접근하면 되는 건지 깨달았는데 이런식으로 조금만 문제가 다르게 나오고, 응용이 필요하면 항상 틀린다. 더 깊게 생각하고 여러 문제를 풀면서 사고력을 키워야겠다. = 해결 = 우리가 그동안 해왔던 방식이랑 매우 비슷하다. 인덱스에서 절반을 나누고, 최댓값을 찾는 식으로 구현했었다. 이 문제도 똑같다. 단지, 응용하고 사고력이 필요했던 문제다. 주어진 식으로 최댓값을 찾냐 아니면 주어진 식을 이용해서 결과를 최대로 만드냐 ? 이런 느낌이라고 보면 된다. 숫자 찾기..
= 처음 접근 방법 (틀림) = 이 문제는 시간 초과로 틀렸다. https://byungil.tistory.com/210 백준 - 이분 탐색 1654번 랜선 자르기 / 풀이,오답 = 처음 접근 방법 (틀림) = 접근을 못했다. 숫자 카드2를 응용해서 풀 수 있는 문제였는데, index로만 생각해봤지 이렇게 길이를 쪼개서 이분 탐색을 한다는 것을 새로 배웠다. 구글링을 통해 다른 byungil.tistory.com 이 문제랑 접근 방법, 풀이까지 거의 일치한다고 보면 된다. 똑같은 문제인데 왜 틀렸을까... 좀 더 고민하고 응용 능력을 키워야겠다. upperBound를 이용해서 해결하지 않았기 때문에 틀렸다. 상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이 문장..
= 처음 접근 방법 (틀림) = 접근을 못했다. 숫자 카드2를 응용해서 풀 수 있는 문제였는데, index로만 생각해봤지 이렇게 길이를 쪼개서 이분 탐색을 한다는 것을 새로 배웠다. 구글링을 통해 다른 사람의 풀이를 보고도 이해하는데 조금 오래걸렸다. 되게 단순한 문제였는데 더 열심히해야겠다. = 풀이 = 어떻게 접근해서 해결했는지 알아보자 https://byungil.tistory.com/205 백준 - 이분 탐색 10816 숫자 카드2 문제 / 복습 자세한 풀이 https://byungil.tistory.com/186 백준 - 집합과 맵 10816번 숫자 카드2 / 이분 탐색을 활용 ( 중복값 ) = 내가 접근한 방법 = 숫자 카드1 문제랑 똑같이 접근했다. Map을 이용해서 Map의 메서드 getO..
