본문 바로가기

알고리즘/완전탐색

 (34)
백준 - 일곱 난쟁이(Java) 다시 풀기 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/2309 [문제 설명] 완전탐색 문제입니다. 완전탐색을 처음 접했을 때 많이 헤멨던 문제라 다시 풀어보기로 했습니다. [접근 방법] 9명 중 2명은 난쟁이가 아니다. 따라서, 두명의 키를 뺐을 때, 키의 총합이 100이면 그 두사람이 난쟁이가 아니다. 조합이므로 복잡도는 9C2 -> 36회 연산됩니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;..
9575번: 백준 - 행운의 수(Java) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/9575 [문제 설명] 3개의 배열이 주어지고 각 배열에서 숫자를 하나씩 뽑아 더했을 때 합을 구한다. 그 합이 5와 8로만 이루어졌으면 이 숫자는 행운의 숫자다. 행운의 숫자의 총 개수를 구하시오. [접근 방법] 제약 조건 수열 크기는 50을 넘지 않고, 원소는 30,000보다 작거나 같은 양의 정수 1125,000 문제에선 중복된 숫자는 같은 걸로 처리함. 2. 중복을 처리할 수 있는 방법들 2.1 해시셋 2.2 배열을 이용하여 방문처리 만족하는 원소 개수(행운..
백준 - 계란으로 계란치기 (Java) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/16987 [문제 설명] 문제가 너무 거창하고 길어서 헤메기 좋은 문제입니다. 특히 2번 조건과 3번 조건이 엄청 헷갈렸습니다. 3번 같은 경우 아직도 헷갈립니다. 잡론은 각설하고 문제의 유형은 완전탐색으로 모든 경우의 수를 만드는 것입니다. 시간복잡도는 계란의 개수^계란의 개수라 언뜻 보면 시간 초과가 날것처럼 보이지만 계란의 개수가 최대 8개이므로 8^8 => 2^24으로 16,777,216 => 1600만밖에 되지 않습니다. import java.io.*; i..
백준 - 0의 개수(java) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/11170 [문제 설명] N부터 M까지 숫자를 쭈욱 썼을 때 0의 총 개수 100,115이면 101,102,103,...,110,111,112,113,114,115 [접근 방법] 규칙이 있어보이지만, 시작 번호가 주어졌다는 점에서 코드가 복잡해질 느낌이 들었다. 그래서 완전 탐색 돌렸다. 숫자는 최대 7자리수이므로 한 숫자에 최대 7번 반복. 테스트 케이스 개수*숫자의 자리수*첫번째숫자부터 끝번 숫자까지 횟수 T*7*(M-N+1) => O(TM) 대략 최대 횟수 연..
백준 - 한 줄로 서기(Java) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/1138 [문제 설명] [접근 방법] 완전탐색 태그로 본 문제다 보니, 바로 완전탐색밖에 떠오르지 않았다. 저번에 이렇게 아무 생각도 안하고 풀었다가 시간초과로 호되게 당한 적이 있기 때문에 완전탐색의 시간복잡도를 먼저 구했다. N명의 사람들을 줄 세우는 방법은 O(N!), N은 최대 값이 9이므로 9!이 된다. 따라서 362,880이다. 여기서 끝나는 게 아니라 입력 받은 배열들이 세워진 줄과 조건이 일치하는지 확인해야한다. 첫번째 입력 예시로 들면 2,1,1,0..
백준 - 1(JAVA) 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/4375 [문제 설명] 1,11,111,1111,11111 주어진 숫자를 배수해서 만들 수 있는 1로 이루어진 숫자는 몇번째 숫자인지 구하시오. 예: 입력이 3일 때 3에 37을 곱한 111이 1로 이루어진 숫자다. 즉, 1로 이루어진 세번째 숫자. 입력이 7일 때 111111은 7의 배수다. 즉, 7로 이루어진 6번째 숫자. [접근 방법] 문제를 딱 봤을 때, 엄청 쉽네 생각하고 풀었다가 오버플로우나 시간 초과나서 망하기 좋은 문제. 백퍼센트 각각의 값에 관계가 ..
백준 - 마인크래프트 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/18111 [문제 설명] N*M 크기의 맵이 있을 때, 높이를 나라시한다고 했을 때, 최소시간을 구하시오. 최소시간이 여러 개면 가장 높은 높이를 리턴하시오. [접근 방법] 현재 땅의 높이 중 최소 높이부터 최대 높이까지 모든 경우를 만들어보고, 그 중에 시간이 가장 작고, 높이가 가장 높은 것을 리턴한다. 3 4 99 0 0 0 0 0 0 0 0 0 0 0 1 위의 테스트 케이스라면 최소 높이가 0 최대 높이가 1이므로, 0부터 1까지 모든 경우의 수를 구한다. ..
백준 - 꽃길 본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다. 저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다. 문의는 댓글 바람. 문제 출처 : https://www.acmicpc.net/problem/14620 [문제 설명] 땅에 꽃을 3개 부화시킬려고한다. 가장 돈이 적게 들게 땅을 사는 방법은? [접근 방법] 완전탐색 문제다. 꽃은 왼쪽 오른쪽 위 아래 크기이기 때문에, 1~땅의 크기-1까지 놓을 수 있다. 땅의 크기가 6이상 10이하이므로 면적은 최소 36에서 100이 된다. 시간복잡도는 꽃을 심을 때마다 면적을 전부 검색하며, 꽃의 개수는 3개이므로 O(면적^3) 땅의 크기를 N으로 줬을 때, 면적은 N^2이니 O(면적^3)은 O(N^6)이 된다. 언뜻 ..

티스토리툴바