분류 전체보기

[백준] 1167번 트리의 지름 - JavaScript(NodeJS)

문제 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 트리의 지름을 구하는 문제이다. 트리의 지름을 구하는 방법 참고 사이트 -> 바로가기 해당 포스팅을 참고하면 임의의 정점 X에서 가장 먼 정점인 Y를 찾고 찾은 정점 Y에서 가장 먼 정점 Z를 찾는다. 이 Y부터 Z까지의 경로가 트리의 지름이다. 트리의 정보를 기반으로 임의의 정점에서 DFS나 BFS를 실행한 결과를 가지고 한번 더 실행해서 트리의 지름을 구해보자. 필자는 DFS를 이용하겠다. 주의할 점? 입력의 각 행이 "노드 다음노..

[백준] 11725번 트리의 부모 찾기 - JavaScript(NodeJS)

문제 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 트리의 루트는 1로 정해져 있다. 2번 노드부터 순서대로 각 노드의 부모 노드의 번호를 출력하면 된다. 각 입력(1 6, 6 3, 3,5 ... )에 대해서 무방향 트리임을 고려해서 입력을 받는다. BFS 너비우선탐색을 이용해보자. 1부터 BFS로 조회하면서 방문을 위한 체크 배열에는, 인덱스(자식 노드)에 값(부모 노드)를 입력한다. 부모 노드는 최소 1의 값을 가지므로, 방문 여부 판별에 이용할 수 있다. BFS가 끝나면 체크 배열에서 2번 인덱스부터 출력한다. 코드를 작성해보자. 코드 const sol = (i..

[백준] 2250 트리의 높이와 너비 - JavaScript(NodeJS)

문제 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 풀이 620 - 트리 1 시리즈에서 가장 어려웠던 문제이다. 우선 문제부터 상당히 길다. 조건을 요약해보면 1. 같은 레벨의 노드는 같은 행(row)에 위치한다. 2. 한 열(column)에는 노드 하나만 존재한다. 3. 특정 노드의 왼쪽 자식은 항상 특정 노드보다 왼쪽에 위치하고, 오른쪽 자식은 항상 특정 노드보다 오른쪽에 위치한다. 4. 열(column)에는 노드가 연속적으로 존재해야 한다.(빈 열이 없어야 한다.) 5. 왼쪽/오른쪽 ..

[백준] 1991 트리 순회 - JavaScript(NodeJS)

문제 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 풀이 전위 순회, 중위 순회, 후위 순회를 순차적으로 실행하고 결과를 출력한다. 문제의 중요한 조건은 항상 A가 루트 노드이며 자식 노드가 없다면 .으로 표현된다. 입력에서 루트가 번호가 아닌 알파벳이 주어지므로, 객체를 이용하자. node의 left, right 순으로 순회하도록 함수를 작성할 것이므로 어느 시점에서 노드를 출력하는가에 따라 전위, 중위, 후위 순회인지가 결정될 것이다. 코드로 바로 구현해본다. 코드 const sol = (input..

[백준] 1261번 알고스팟 - JavaScript(NodeJS)

문제 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 풀이 N x M 크기 미로에서 (1,1)에서 시작하여 (N,M)에 도달하면 끝난다. 미로에서는 벽이 없다면 바로 이동하며, 벽이 있다면 부수고 이동할 수 있다. (N,M)에 도달하기까지 벽을 최소 몇 개 부수고 이동할 수 있는지를 구하면 된다. 이동은 상하좌우로 총 4방향이 가능하다. 풀이 방향 13549 숨바꼭질3 문제와 유사한데, 작업의 우선순위를 설정해야 한다. 즉, 목적지에 도착하기까지 벽을 최대한 부수지 말아야 하므로, 벽을 ..

[백준] 14226 이모티콘 - JavaScript(NodeJS)

문제 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 풀이 처음 시작은 이모티콘 1개로 시작한다. 다음 3가지 연산으로 이모티콘을 S개로 만들면 된다. 모든 연산은 1초가 걸린다. 1. 화면의 이모티콘을 모두 복사해서 클립보드에 저장 2. 클립보드에 있는 이모티콘을 모두 화면에 붙여넣기 3. 화면의 이모티콘 중 한 개 삭제 클립보드에 대한 조건은 다음과 같다. 클립보드에 이모티콘을 복사하면, 이전 클립보드가 덮어씌워진다. 클립보드가 비었다면, 2번 명령 붙여넣기 불가능. 풀이 방향 처음에는 이모티콘 1개로 시작해..