DS & Algorithm

[백준] 1339번 단어 수학 - JavaScript(NodeJS)

문제 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 브루트 포스 문제지만, 억지로 브루트 포스를 적용해보려고 하다가 좀 헤맨 문제다. 모든 경우의 수를 조회할 수 있는 방법도 있지만, 각 단어를 구성하는 알파벳에 숫자를 대입한 합의 최대값을 출력하는 문제이기 때문에 다르게 접근해봤다. 단어에서 위치한 알파벳들의 자릿수 합을 계산하고, 자릿수의 합 순으로 정렬한다. 자릿수의 합이 큰 알파벳부터 순차적으로 가능한 가장 큰 숫자를 대입한다. "AAA", "BCD"일 때 111A + 100B + 10C ..

[백준] 2529번 부등호 - JavaScript(NodeJS)

문제 2529번: 부등호 두 종류의 부등호 기호 ‘’가 k개 나열된 순서열 A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제 www.acmicpc.net 풀이 Brute Force(무차별 대입, 무식하게 풀기?) 문제이다. 정수의 개수 k의 범위가 2 max ? result : max; min = result < min ? result : min; return; } if (inequality[L] === "

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

문제 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 1991번 문제와 거의 동일한 문제이다. 1991번 문제 이전 포스팅 { const N = +input[0]; if (N === 1) return 0; // N=1 이면 지름은 0이다. input = input.slice(1); const tree = Array.from({ length: N + 1 }, () => new Array()); input.map((str) => { const [from, to, dist] = str.sp..

[백준] 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. 왼쪽/오른쪽 ..