분류 전체보기 (75) 썸네일형 리스트형 완전탐색 #1759: 암호 만들기[JAVA] https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net [ 문제 접근 ] 웬일로 골드 문제가 깔끔하게 풀리나했는데 반례 때문에 틀렸다. (그럼 그렇지 ㅎㅎ) 알고리즘은 백트래킹 dfs으로 풀었다. 첫 번째 시도 - 문제의 코드 static void dfs(int depth) { if (depth == l && isVaildLen()) { // 최소 1개 모음, 2개 자음인지 for (char c : result) { sb.append(c); } sb.app.. 완전탐색 #10819: 차이를 최대[JAVA] https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 접근 1. 순열 재귀적 구현 2. 백트래킹 dfs(N과 M문제 복습) 코드 1. 순열 재귀적 구현 import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; import java.io.IOException; public class Main { static int[] arr; static i.. 순열 구현 순열 순열은 기본적으로 재귀 함수로 구현할 수 있다. 10!을 구한다고 하자. 10!=10*9!이므로 10!을 구하기 위해선 9!을 구해야하고 9!=9*8!...이므로 9!를 구하기 위해선 8!을 구해야하므로... 재귀적이라 할 수 있다. 코드는 다음과 같다. void perm(char[] list, int i, int n) { //list의 i번째부터 n번째 인덱스에 해당하는 요소 출력 if (i == n) { for (int j = 0; j 완전탐색 #1107: 리모컨 [JAVA] https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 www.acmicpc.net 문제 접근 쉬운듯 보였지만 어려웠드아 - broken 배열에 고장난 버튼에 해당하는 인덱스를 true로 표기 - 예외 경우인 N==100인 경우와 M==0인 경우 바로 출력하고 종료했는데 배열 초기화 안해서 99퍼에서 틀렸습니다 뜸 - 0부터 999999까지 모두 조사한다. 왜 999999냐면 N이 500000이고(N의 최댓값) 고장나지 않은 버튼의 수가 9밖에 없으면 99999.. #18870: 좌표 압축 [JAVA] 18870번: 좌표 압축 (acmicpc.net) 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다. X1, X2, ..., XN에 www.acmicpc.net 문제 접근 x좌표를 입력 받아 입력 순서를 유지할(출력 위해) 배열과 정렬과 개수 세기 위한 hashmap에 저장해두고 hashmap의 keyset을 가지고 정렬을 한 뒤 누적합 구함 이렇게 안해두 댐! 입력 받아서 입력 순서 유지할 배열과 정렬 저장할 배열에 동시 저장 정렬 배열에서 중복 걸러서 hashmap에 저장. 이때, value값은 x좌표보다 작은 좌표의.. 그래프 문제(bfs,dfs) #2146: 다리 만들기 [JAVA] https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 문제 접근 한 섬에서 다른 섬으로의 최소 거리를 구해야함. 1. 각 섬을 구분해주자 -> dfs 탐색. 같은 섬의 점이면 같은 인덱스를 부여 2. 각 섬의 모든 점에 대해 다른 섬으로의 최소 거리를 조사 ->bfs 탐색 간과한 점 1. 방문 안한 바다 조건에서 check[pr][pc]=true 안해서 메모리 초과 남. 2. 다른 섬 조건에서 바다가 아니라는 조건도 넣어야하는데 안해서 정답이 안나옴. 3.. #1764: 듣보잡 [JAVA] https://www.acmicpc.net/problem/1764 1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net 문제 접근 1. List 클래스의 교집합 메소드인 retainsAll() 썼으나 시간 초과 2. ArrayList의 contains() 메소드 쓰니까 시간 초과 3. HashSet 사용 성공 ! HashSet의 contains()는 O(1), ArrayList의 contains()는 O(n)이다. HashSet은 map을 기반으로 구현되고 ArrayList는 indexOf()를 사용해서 cont.. 이분탐색/삼분탐색 #2110: 공유기 설치 [JAVA] https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 문제 접근 이분 탐색 upper bound를 어떻게 적용해야할지 몰라 블로그 글을 찾아봤다. 글을 보니까 이해는 되지만.. 실전 코테에서 내가 그 아이디어를 떠올릴 수 있을까 의문이다. 꾸준히 하다보면 늘겠지.. 인접 공유기 간의 최소 거리가 있다고 하면 그 거리에 따라 설치할 수 있는 공유기의 개수가 정해진다. (약간 역발상..) 이때, 최소 .. 이전 1 2 3 4 ··· 10 다음
