알고리즘

[JAVA] 백준 1991번 - 트리순회

문제 1991번: 트리 순회 [ 해결순서 ] 한줄에 띄어서 입력받으므로 띄어쓰기를 붙여 문자열을 배열로 전환하여 노드에 저장하였다. 문제를 해결하기 위해 노드, 트리 클래스가 있어야 한다. 노드 클래스 : 루트, 왼쪽 자식, 오른쪽 자식이 있고, 노드의 값을 입력받아 지정 가능하다. 트리 클래스 : 여러개의 노드가 모여 트리를 구성하므로, 노드가 있어야 함 add() : 트리에 노드를 추가하는 메소드이며 처음을 제외하고는 search()를 사용하여 추가. search() : 어떤 노드밑에 서브트리가 생기는지 재귀호출하며 찾음. 전위순회 preorder : 루트 → 왼쪽 서브트리 → 오른쪽 서브트리 방문 중위순회 inorder : 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 방문 후위순회 postorder ..

[JAVA] 백준 2667번 - 단지번호붙이기

문제 2667번: 단지번호붙이기 [ 해결순서 ] 깊이우선탐색, 너비우선탐색 어떤 방식으로도 풀 수 있는 문제지만, 나는 문제를 보자마자 깊이우선탐색로 풀어야 겠다고 떠올라 이 방식으로 해결하였다. 총 단지수는 하나의 깊이우선탐색이 끝날때 변수 값을 하나씩 추가하면 되며, 모든 값들을 하나씩 살펴보며 방문하지 않은 것 중 집이 있는 곳을 깊이우선탐색 한다. dfs 메소드는 사실 다른 유사한 깊이우선탐색의 메소드와 비슷하다. 그래도 설명하자면, 입력한 x, y값을 기준으로 상하좌우의 값을 비교하여 조건에 맞는 (방문하지 않고, 집이있으면) 그 값을 기준으로 재귀처리 함. 총 단지수를 출력하고, 각 단지내의 수를 오름차순으로 정렬하여 출력 (까먹고 오름차순 정렬하지 않았다가 틀렸었다) ✏️ 한줄 평 이젠 어떤..

[JAVA] 백준 1697번 - 숨바꼭질

문제 1697번: 숨바꼭질 [ 해결순서 ] 문제의 조건을 파악한 후 이동을 할 때 3가지 경우에 따라 조건문을 작성하면 되겠다고 파악했다. 큐를 이용하여 시작 값을 먼저 큐에 넣고 큐가 비어있을 때까지 반복해서 큐의 값을 꺼내어 3가지 조건을 너비우선탐색을 이용한다. 값이 조건에 벗어나지 않고, 방문을 하지 않았으면 그 값을 큐에 넣어 재귀호출을 통해 그 값을 기준으로 또 너비우선탐색을 한다. 결과의 위치를 찾으면 그 위치가 몇 초후에 찾았는지 visited 배열의 값에 넣어 출력한다. ✏️ 한줄 평 이런 종류의 문제를 너비우선탐색을 이용하여 풀 수 있구나를 제대로 알게 된 문제였다. 코드

[JAVA] 백준 1149번 - RGB거리

문제 1149번: RGB거리 [ 해결순서 ] 처음엔 첫 줄의 최소 값을 구하고 다음 줄에는 그 줄의 색깔을 제외한 색깔 중 최소 값을 구하려 했다. 그러면 전체에서의 최소 값을 구하지 못함. 결국 전체 경우의 수를 구해야 함 해당 값을 구하려면 현재의 색깔을 제외한 색깔의 행과, 직전의 열을 값들을 비교해서 작은 값에 + 현재의 비용을 더함. (비용을 더하지 않는 실수를 함) 마지막 줄의 색깔 중 가장 작은 값이 정답 점화식 dp[i][red]=Math.min(dp[i-1][blue],dp[i-1][green])+cost[i][red] //빨간 색 이라면, 그 전줄의 빨간 색이 아닌 파랑, 초록 중 작은 값 + 해당 값의 가격 ✏️한줄평 DP 문제를 더 자주 풀어 익숙하게 해야겠다. 코드