본문 바로가기

전체 글110

[Java] BOJ 11725 트리의 부모 찾기 문제 문제 링크 https://www.acmicpc.net/problem/11725루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.아이디어인접 리스트로 트리를 구현해서 양방향으로 트리의 간선 정보를 입력받는다.그리고 DFS로 노드마다 부모 노드를 찾아서 배열에 저장한다.우선 루트를 1로 정했으므로, 1부터 DFS를 돌리며 노드 1을 방문처리하고, 1에 연결된 노드 중 방문 되지 않은 노드라면 해당 노드의 부모 .. 2024. 12. 21.

[Java] BOJ 1991 트리 순회 문제 문제 링크 https://www.acmicpc.net/problem/1991이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.예를 들어 위와 같은 이진 트리가 입력되면,전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)가 된다.첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, .. 2024. 12. 20.

[Java] BOJ 1474 밑 줄 문제 문제 링크 https://www.acmicpc.net/problem/1474세준이는 N개의 영어 단어를 이용해 길이가 M인 새로운 단어를 만들려고 한다. 새로운 단어는 N개의 단어를 순서대로 이어 붙이고, 각 단어의 사이에 _을 넣어서 만든다. 이렇게 만든 새로운 단어의 길이가 M이 아닌 경우 _를 추가해서 길이가 M이 되게 만들어야 한다._는 단어와 단어 사이에만 추가할 수 있다. 따라서, 새로운 단어는 _으로 시작하거나, _로 끝날 수 없다.단어와 단어 사이에 있는 _의 개수는 모두 같아야 한다.모두 같게 만드는 것이 불가능한 경우 단어와 단어 사이에 있는 _의 개수의 최댓값과 최솟값의 차이는 1이 되어야 한다.새로운 단어 중 사전 순으로 가장 앞서는 단어를 구해보자.첫째 줄에 N과 M이 주어진.. 2024. 12. 18.

[Java] BOJ 2294 동전 2 문제 문제 링크 https://www.acmicpc.net/problem/2294n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다. 첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다. 아이디어동전의 갯수만큼 배열을 선언하고 동전의 가치를 저장한다.그리고 0원부터 k가격까지 만들때 사용한 동전의.. 2024. 12. 17.

[Java] BOJ 12933 오리 문제 문제 링크 https://www.acmicpc.net/problem/12933오리의 울음 소리는 "quack"이다. 올바른 오리의 울음 소리는 울음 소리를 한 번 또는 그 이상 연속해서 내는 것이다. 예를 들어, "quack", "quackquackquackquack", "quackquack"는 올바른 오리의 울음 소리이다.갑자기 영선이의 방에 있는 오리가 울기 시작했고, 이 울음소리는 섞이기 시작했다. 영선이는 일단 울음소리를 녹음했고, 나중에 들어보면서 총 몇 마리의 오리가 있는지 구해보려고 한다.녹음한 소리는 문자열로 나타낼 수 있는데, 한 문자는 한 오리가 낸 소리이다. 오리의 울음 소리는 연속될 필요는 없지만, 순서는 "quack"이어야 한다. "quqacukqauackck"과 같은 경우는.. 2024. 12. 17.

[Java] BOJ 2504 괄호의 값 문제 문제 링크 https://www.acmicpc.net/problem/25044개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다.한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다.만일 X가 올바른 괄호열이면 ‘(X)’이나 ‘[X]’도 모두 올바른 괄호열이 된다.X와 Y 모두 올바른 괄호열이라면 이들을 결합한 XY도 올바른 괄호열이 된다.예를 들어 ‘(()[[]])’나 ‘(())[][]’ 는 올바른 괄호열이지만 ‘([)]’ 나 ‘(()()[]’ 은 모두 올바른 괄호열이 아니다. 우리는 어떤 올바른 괄호열 X에 대하여 그 괄호열의 값(괄호값)을 아래와 같이 정의하고 값(X)로 표시한다.‘()’ 인 괄호열의 값은 2이다... 2024. 12. 16.

이전 1 2 3 4 5 ··· 19 다음

티스토리툴바