본문 바로가기

Dot Algo∙ DS/PS

[BOJ] 백준 22856번 트리 순회 (Java)
Dot Algo∙ DS/PS 2022. 3. 18. [BOJ] 백준 22856번 트리 순회 (Java) #22856 트리 순회 난이도 : 골드 4 유형 : 트리 순회 / DFS 22856번: 트리 순회 노드가 $N$개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. www.acmicpc.net ▸ 문제 노드가 N개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자. 순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. 이때 루트 노드는 항상 1번 노드이다. 유사 중위 순회는 루트 노드에서 시작하며, 다음과 같이 진행된다. 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로..
[BOJ] 백준 15927번 회문은 회문이 아니야!! (Java)
Dot Algo∙ DS/PS 2022. 3. 17. [BOJ] 백준 15927번 회문은 회문이 아니야!! (Java) #15927 회문은 회문이 아니야!! 난이도 : 골드5 유형 : 문자열 15927번: 회문은 회문아니야!! 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 www.acmicpc.net ▸ 문제 팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다. 같은 의미를 가지는 여러 단어들을 보자. 회문 (한국어) palindrome (영어, 프랑스어, 노르웨이어, 그리스어, 라틴어) 回文 (일본어, 중국어) palindro..
[BOJ] 백준 6443번 애너그램 (Java)
Dot Algo∙ DS/PS 2022. 3. 16. [BOJ] 백준 6443번 애너그램 (Java) #6443 애너그램 난이도 : 골드 5 유형 : 문자열 / 순열 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net ▸ 문제 씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다. 애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다. 입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우..
[BOJ] 백준 1593번 문자 해독 (Java)
Dot Algo∙ DS/PS 2022. 3. 15. [BOJ] 백준 1593번 문자 해독 (Java) #1593 문자 해독 난이도 : 골드 4 유형 : 문자열 / 슬라이딩 윈도우 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net ▸ 문제 마야 문자를 해독하는 일은 예상 외로 어려운 일이다. 현재에도 뜻이 완전히 밝혀진 마야 문자는 거의 없는 실정이며, 그나마 해독에 진척이 시작된 지는 30여 년도 되지 않았다. 마야 문자는 소리를 나타내는 여러 종류의 그림글자로 구성되는데, 이 글자들이 여러 위치에서 결합함으로써 단어를 형성한다. 마야 문자 해독을 어렵게 하는 요인 중 하나는 바로..
[BOJ] 백준 1595번 북쪽나라의 도로 (Java)
Dot Algo∙ DS/PS 2022. 3. 14. [BOJ] 백준 1595번 북쪽나라의 도로 (Java) #1595 북쪽나라의 도로 난이도 : 골드 3 유형 : 트리의 지름 / dfs 1595번: 북쪽나라의 도로 입력은 여러줄에 걸쳐 주어진다. 입력의 각 줄은 세 개의 양의 정수로 구성되어있는데, 각각은 차례대로 서로 다른 두 도시의 번호와 두 도시를 연결하는 도로의 길이를 의미한다. 모든 도로는 www.acmicpc.net ▸ 문제 두 도시 사이에 도로를 만드는 일은 매우 비싸다. 때문에 북쪽나라는 특정 도시를 두 번 이상 지나가지 않고서 임의의 두 도시간을 이동하는 경로가 유일하도록 도로가 설계되어 있다. 또한 북쪽나라의 모든 도시는 다른 모든 도시로 이동할 수 있다고 한다. 이때, 거리가 가장 먼 두 도시 사이의 거리를 출력하는 것이 당신의 임무이다. 북쪽나라에는 최대 10,000개의 도시가 있을 수 ..
[BOJ] 백준 1414번 불우이웃돕기 (Java)
Dot Algo∙ DS/PS 2022. 3. 13. [BOJ] 백준 1414번 불우이웃돕기 (Java) #1414 불우이웃돕기 난이도 : 골드 2 유형 : 문자열 / MST / 크루스칼 1414번: 불우이웃돕기 첫째 줄에 컴퓨터의 개수 N이 주어진다. 둘째 줄부터 랜선의 길이가 주어진다. i번째 줄의 j번째 문자가 0인 경우는 컴퓨터 i와 컴퓨터 j를 연결하는 랜선이 없음을 의미한다. 그 외의 경우는 랜선 www.acmicpc.net ▸ 문제 다솜이는 불우이웃 돕기 활동을 하기 위해 무엇을 할지 생각했다. 마침 집에 엄청나게 많은 랜선이 있다는 것을 깨달았다. 마침 랜선이 이렇게 많이 필요 없다고 느낀 다솜이는 랜선을 지역사회에 봉사하기로 했다. 다솜이의 집에는 N개의 방이 있다. 각각의 방에는 모두 한 개의 컴퓨터가 있다. 각각의 컴퓨터는 랜선으로 연결되어 있다. 어떤 컴퓨터 A와 컴퓨터 B가 있을 때,..
[BOJ] 백준 16172번 나는 친구가 적다 (Large) (Java)
Dot Algo∙ DS/PS 2022. 3. 12. [BOJ] 백준 16172번 나는 친구가 적다 (Large) (Java) #16172 나는 친구가 적다 (Large) 난이도 : 골드 2 유형 : 문자열 / kmp 16172번: 나는 친구가 적다 (Large) 첫 번째 줄에는 알파벳 소문자, 대문자, 숫자로 이루어진 문자열 S가 주어진다. (1 ≤ |S| ≤ 200,000) 두 번째 줄에는 성민이가 찾고자 하는 알파벳 소문자, 대문자로만 이루어진 키워드 문자열 K가 www.acmicpc.net ▸ 문제 친구가 적은 성민이는 수업에 결석해도 시험이나 과제에 대한 정보를 제대로 얻을 수 없었다. F 학점을 받을 위기까지 아슬아슬하게 결석일 수를 유지하던 성민이는, 어느 날 갑자기 영문도 모른 채 쪽지시험을 보게 되었다! 갑작스러운 쪽지 시험으로 마음이 급해진 성민이는 매직아이를 사용해 벼락치기를 하기로 한다. 성민이가 듣는 과목..
[BOJ] 백준 9177번 단어 섞기 (Java)
Dot Algo∙ DS/PS 2022. 3. 11. [BOJ] 백준 9177번 단어 섞기 (Java) #9177 단어 섞기 난이도 : 골드 4 유형 : 문자열 / bfs 9177번: 단어 섞기 세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 www.acmicpc.net ▸ 문제 세 개의 단어가 주어졌을때, 꿍은 첫 번째 단어와 두 번째 단어를 섞어서 세 번째 단어를 만들 수 있는지 궁금해졌다. 첫 번째와 두 번째 단어는 마음대로 섞어도 되지만 원래의 순서는 섞여서는 안 된다. 다음과 같은 경우를 생각해보자. 첫 번째 단어 : cat 두 번째 단어 : tree 세 번째 단어 : tcraete 보면 알 수 있듯이, 첫 번째 단어와 두 번째 단어를 서로 섞어서 세 번째..

티스토리툴바

티스토리툴바