ProgramSoliving (197) 썸네일형 리스트형 백준 : 14725 (트라이) https://www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 � www.acmicpc.net 트라이 문제로 분류된다. 각각의 노드들에 TreeMap 을 이용하여 순서가있는 String key값 들을 자식으로가지고 TrieNode를 class로 반환함으로써 연결리스틀 만들수 있다. 문자열을 출력할 때는 DFS(깊이 우선 탐색)을 이용하여 출력할 수 있다. import java.io.BufferedReader; import java.io.IOException; import .. 백준 : 10266 https://www.acmicpc.net/problem/10266 10266번: 시계 사진들 문제 상근이는 보통의 시계와는 다른 독특한 시계 사진 두장이 있습니다. 시계는 n개의 동일한 길이와 목적을 가진 시계 바늘들을 가지고 있습니다. 애석하게도 시계의 숫자들은 희미해져 각 시 www.acmicpc.net 문제의 input으로는 어느 바늘을 기준으로 시계바늘이 있는 위치를 간격 0 ~ 360000 으로 보여준다. 이것은 0과 1을 가지는 문자열로 나타낸다면 문자열 길이 360,000인 00011001011110 비트형태의 문자열을 만들수가있다. 이상태에서 기존 비교해야할 문자열을 길이를 두배로하고 KMP알고리즘을 이용해서 origin 에 pattern이 존재여부를 확인하면 같은 시간을 가리키는가? 를.. 백준 : 6543 https://www.acmicpc.net/problem/6543 6543번: 그래프의 싱크 각 테스트 케이스마다 한 줄에 걸쳐 bottom(G)의 모든 노드를 출력한다. 노드는 공백으로 구분해야 하며, 오름차순이어야 한다. 만약, bottom(G)가 공집합이면 빈 줄을 출력한다. www.acmicpc.net SCC를 찾는 문제인데 간선이 존재하지 않는 노드는 그자체가 강한 연결요소이다. 위의 그림처럼 5번을 제외한 나머지 노드들은 강한 연결요소가 아니다 1->2->3 은 강한 연결요소인것 같지만 3->4 edge도 존재하기 때문에 강한 연결 요소가 아니다 이러한 경우의 SCC는 제외하면 된다. SCC를 만들어가는 과정에서 현재 사이클에서 SCC가 만들어진 집단에대해서 연결된 edge가 false가 존재.. 백준 : 6497 https://www.acmicpc.net/problem/6497 6497번: 전력난 문제 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈�� www.acmicpc.net 모든 간선 - MST = Answer import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.StringTokeniz.. 백준 : 11585 속터지는 저녁 메뉴 https://www.acmicpc.net/problem/11585 11585번: 속타는 저녁 메뉴 수원이와 친구들은 저녁 메뉴를 잘 선택하지 못한다. 배가 고픈 수원이가 보다 못해 메뉴를 정하곤 하는데 이마저도 반대에 부딪히는 경우에는 수원이가 원형 룰렛을 돌려 결정하곤 한다. 이 원 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class B11585 { static int[] getPi(String Pattern) { int[] pi =.. 백준 : 1305 (광고) java https://www.acmicpc.net/problem/1305 1305번: 광고 첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다. L은 백만보다 작거나 같은 자연수이다. www.acmicpc.net 문제의 정답은 L - Pi[L-1] 이다 이것이 나타내는 것은 L이라는 문자열 안에 똑같은 패턴이 있다면 가장 짧은 패턴을 찾아내는 것이다. 물론 패턴의 길이 최대는 L 이다. KMP 의 getPi 함수를 사용하면 접두사 접미사로 이루어져있고 문자열의 길이 마다 반복되는 문자열의 위치를 알 수 있다. aaaaa -> 01234 이것을 이용해서 최대 패턴의 길이를 구할 수 있다. import java.io.BufferedReader; import java.io.IO.. 백준 : 4920 https://www.acmicpc.net/problem/4920 4920번: 테트리스 게임 문제 테트리스는 아래와 같은 5가지 조각으로 이루어져 있다. 정수로 이루어진 N×N 표가 주어진다. 테트리스 블록 중 하나를 표에 놓아 블록 아래에 있는 숫자의 합의 최댓값을 구하는 프로그램� www.acmicpc.net rotate와 배열돌리기를 적절히 활용해서 문제를 풀었다. 주의 할점은 100만 이하의 절대값인 수가 입력으로 들어온다. 따라서 long값과 sovle의 범위초과할때 Long.MINVALUE를 해주면 쉽게 구현할 수 있다. package ps; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream.. 백준 : 18809 https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net DFS(조합) + BFS 자주 나오는 유형의 문제이다. 다만 문제에서 조합을 두번해야한다는 것이다. 1. 배양액을 심을 위치 R+G 개수를 선정한다. (조합) 2. 그조합중에서 R C 배양액을 놔둘 위치를 선정한다. (조합) 3. 1과 2 의 조합을 가지고 BFS 탐색을 진행한다. 이때 color[][] 2차원 배열을 이용해서 0 : 방문.. 이전 1 ··· 8 9 10 11 12 13 14 ··· 25 다음
