문제 풀이
-
[Baekjoon Online Judge] 1260번: DFS와 BFS문제 풀이/Baekjoon Online Judge 2021. 1. 12. 22:32
1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net [그래프 탐색] DFS와 BFS 1. 그래프란? 그래프는 vertex(정점)와 vertex(정점)를 이어주는 edge(간선)로 이루어져 있다. 정점은 대상이나 개체를 나타내고, 간선은 이들 간의 관계를 나타낸다. 상호 관계가 대칭적이지 않은 hyeonic.tistory.com 간선을 연결하는 두 정점의 번호를 입력 받아 그래프를 그리고 DFS와 BFS로 탐색한다. DFS와 BFS에 대한 설명은 https://hyeonic.t..
-
[그래프 탐색] DFS와 BFS문제 풀이/Baekjoon Online Judge 2021. 1. 12. 20:31
1. 그래프란? 그래프는 vertex(정점)와 vertex(정점)를 이어주는 edge(간선)로 이루어져 있다. 정점은 대상이나 개체를 나타내고, 간선은 이들 간의 관계를 나타낸다. 상호 관계가 대칭적이지 않은 경우 방향을 가진 간선으로 나타낼 수 있다. 이때 이러한 그래프를 방향을 가진 그래프 혹은 Direct Graph 유향 그래프라고 한다. 반면 간선의 방향이 없는 그래프를 무방향 그래프 혹은 Undirected Graph 무향 그래프라고 한다. 2. 그래프의 표현 그래프의 표현 방법에는 행렬을 이용하는 방식과 리스트를 이용하는 방식이 있다. 2.1 인접 행렬 그래프 G = (V, E)에서 정점의 총 수를 n이라고 가정하자. 행렬의 크기는 n x n 행렬이 된다. 정점 i와 정점 j 사이에 간선이 존..
-
[2020 KAKAO BLIND RECRUITMENT] 가사 검색문제 풀이/KAKAO BLIND RECRUITMENT 2021. 1. 10. 23:33
코딩테스트 연습 - 가사 검색 programmers.co.kr 정확성과 효율성 테스트 각각 점수가 있는 문제이다. 가사 단어의 제한사항 - words의 길이(가사 단어의 개수)는 2 이상 100,000 이하이다. - 각 가사 단어의 길이는 1 이상 10,000 이하로 빈 문자열인 경우는 없다. - 전체 가사 단아 길이의 합은 2 이상 1,000,000 이하이다. - 가사에 동일 단어가 여러 번 나올 경우 중복을 제거하고 words에는 하나로만 제공된다. - 각 가사 단어는 오직 알파벳 소문자로만 구성되어 있으며, 특수문자나 숫자는 포함하지 않는 것으로 가정한다. 검색 키워드 제한사항 - queries의 길이(검색 키워드 개수)는 2 이상 100,000 이하이다. - 각 검색 키워드의 길이는 1 이상 10..
-
[Baekjoon Online Judge] 1541번: 잃어버린 괄호문제 풀이/Baekjoon Online Judge 2021. 1. 8. 20:26
1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 괄호가 지워진 수식이 주어진다. 연산자가 + - + - +.. 혹은 - + - + -.. 로 번갈아가면서 나오게 된다. 여기서 규칙성을 찾아보았다. 만약 55-50+40-20+25-10 인 경우 (55) - (50 + 40) - (20 + 25) - (10)이 가장 최소값이 된다. 만약 55+50-40+20-25+10 인 경우 (55+50)-(40+20)-(25+10)이 가장 최소값이 된다. 항상 -를 기준으로 ()를 사용하면 가장 최소값을 구할 수 있다...
-
[Baekjoon Online Judge] 1100번: 하얀 칸문제 풀이/Baekjoon Online Judge 2021. 1. 8. 20:21
1100번: 하얀 칸 체스판은 8*8크기이고, 검정 칸과 하얀 칸이 번갈아가면서 색칠되어 있다. 가장 왼쪽 위칸 (0,0)은 하얀색이다. 체스판의 상태가 주어졌을 때, 하얀 칸 위에 말이 몇 개 있는지 출력하는 프로그램 www.acmicpc.net 체스판의 하얀 칸 위에 말이 몇 개 있는지 출력하는 문제이다.. import java.io.*; public class Baekjoon1100 { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter =..
-
[Baekjoon Online Judge] 9251번: LCS문제 풀이/Baekjoon Online Judge 2021. 1. 8. 20:18
9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS (Longest Common Subsequence) 공통 부분 수열 중 가장 길이가 긴 것이 바로 최장 공통 부분 수열이다. 문제의 예시를 들어보았다. 문자열 A - ACAYKP 문자열 B - CAPCAK 두개의 문자열이 있다고 가정하자. 두 문자열의 공통 부분 수열은 C, CA, ACA, ACAK, AA 등이 있다. 그중 가장 긴 부분 수열을 구하는 문제이다. 문자열 A - ACAYKP 문자열 B - CAPC..
-
[Baekjoon Online Judge] 10808번: 알파벳 개수문제 풀이/Baekjoon Online Judge 2021. 1. 8. 19:53
10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net import java.io.*; import java.util.HashMap; import java.util.Map; public class Baekjoon10808 { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(..
-
[Baekjoon Online Judge] 2743번: 단어 길이 재기문제 풀이/Baekjoon Online Judge 2021. 1. 8. 19:50
2743번: 단어 길이 재기 알파벳으로만 이루어진 단어를 입력받아, 그 길이를 출력하는 프로그램을 작성하시오. www.acmicpc.net import java.io.*; public class Baekjoon2743 { public static void main(String[] args) throws IOException { BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out)); String s = bufferedReader.readLine(); bu..