본문 바로가기

백준744

백준 10867 자바 - 중복 빼고 정렬하기 (BOJ 10867 JAVA) 문제 : boj10867 중복 제거만 하고 정렬만해도 풀 수 있는 간단한 문제이다. 해시로 중복체크하면서 list에 넣고 정렬 후 출력만 해줘도 된다. 또 다른 방법은 그냥 TreeSet에 넣으면 중복이 알아서 제거되므로 순서대로 꺼내면 된다. 내 경우엔 어차피 값이 -1000~1000 까지의 정수이므로 2000개짜리 배열에 어떤 수가 존재하는지 기입한다. 그럼 중복은 알아서 제거되고, 배열 순서대로 출력만 해주면 된다. 배열을 2001개 잡아두고 0~1000은 음수가, 그 이상은 양수가 사용하게 해도 되고, 그냥 음수 따로 양수 따로 1000개씩 배열을 만들어줘도 된다. 내 경우엔 후자로 진행했다. 예를들어 '-5 4 4 -1 -5 3 0'이 있고, 값이 -5~5 까지 가능했다고 한다면(그리기 쉽게) .. 2022. 1. 2.
백준 10465 자바 - Rolling Encryption (BOJ 10465 JAVA) 문제 : boj10465 1. 우선 문자열에서 k개를 그대로 출력한다. 이후 각 character마다 그 이전 k개의 문자열 중 가장 많이 나온 문자를 찾는다. 그리고 가장 많이 나온 문자(동일한 수가 나온게 있다면 알파벳에서 먼저 나오는걸로)만큼 쉬프트 시킨다(a면 1번, b면 2번, ..., z면 26번) 2. 문제만 보면 간단히 구할 수 있을 것 같은데, 문제는 k가 최대 10000이고 문자열의 길이가 최대 100000이므로 단순하게 각 character마다 이전 k개를 보게된다면 O(10000 * 100000)이 필요하므로 시간초과가 나게 된다. 이 경우 소문자는 총 26개이므로 별도 배열로 각 문자에 대해 세보면 더 효율적으로 가장 많이 나온 문자를 찾을 수 있다. "abbaabbac"에 대해 .. 2022. 1. 2.
백준 6588 자바 - 골드바흐의 추측 (BOJ 6588 JAVA) 문제 : boj6588 1. 홀수인 소수란 말은 그냥 2를 제외한 소수라는 의미이다. 2 말곤 전부 홀수인 소수이다. 아무튼 그러니 100만 이하의 소수를 모두 구해준다. 에라토스테네스의 체를 사용해 입력받기전에 미리 구해두면 각 케이스에 대해 해당 소수들을 써먹을 수 있으니 효율적이다. 그리고 여러 방법이 있겠으나, 시간복잡도를 좀 손해보더라도 편하게 코드를 짜기 위해 TreeSet에 찾은 소수를 넣어두었다. 시간 복잡도에 중점을 두려면 소수를 hashSet에 넣고, 추가로 소수 순서대로 배열에 넣어두면 된다. 어차피 시간이 널널한 문제라 뭘 쓰던 상관없다. TreeSet은 set이므로 a+b = n을 찾을 때 a가 정해지면 b가 존재하는지 contains(n-a)로 확인할 수 있다. 또한 hashSe.. 2022. 1. 1.
백준 10819 자바 - 차이를 최대로 (BOJ 10819 JAVA) 문제 : boj10819 N이 최대 8밖에 안된다. 8개의 수로 만들 수 있는 모든 경우를 확인해봐도 O(N!) 이므로 그냥 모든 경우를 확인해보면 된다. 재귀나 스택을 사용한 dfs로 짜면 완전탐색(=brute force)을 쉽게 짤 수 있다. 단순 반복문으로 짜려고 하면 최대 8중첩 반복문이 필요하다 ㅋㅋ 재귀에 익숙치 않다면 방문체크가 어려울 수 있다. 다음 수를 선택하기 전에(내부에서 dfs를 다시 부르면서 cnt+1 해주는 부분이 다음 수를 선택하기 위한 부분이다.) 방문체크를 하고, 반환된 후에 다시 방문체크를 해제해줘야 모든 경우를 볼 수 있다. 코드 : github import java.io.BufferedReader; import java.io.InputStreamReader; impor.. 2022. 1. 1.
백준 2491 자바 - 수열 (BOJ 2491 JAVA) 문제 : boj2491 1. 연속해서 커지는 경우(같은 것 포함)만 일단 생각해보자. 주어지는 N개의 숫자에 대해서, 숫자가 작아진 경우 카운팅을 1로 되돌려보자. 그럼 다음과 같이 증가(같은 것 포함)하는 경우에 대해 각 구간에서 얼마나 긴 길이를 가지는지 알 수 있다. 2. 그럼 감소하는 경우도 마찬가지다. 값이 이전보다 커지는 경우 카운팅을 1로 되돌리면서 계속 세어나가면 된다. 이 문제의 경우엔 커지거나, 작아지는 수열 중 답을 구해야한다. 하지만 다를건 없다 그냥 하나씩 입력받으면서 증가하는 경우의 카운팅과, 감소하는 경우의 카운팅을 따로따로 해주면 된다. 한번에 세지 못하고 따로따로 세줘야 하는 이유는, 모든 수가 동일한 구간이 포함된 경우 (e.g. '1 1 1 1 1 1')를 제대로 판단하.. 2021. 12. 31.
백준 2225 자바 - 합분해 (BOJ 2225 JAVA) 문제 : boj2225 1. 0부터 N까지에서 '0부터' 부분 때문에 좀 헷갈렸다. '덧셈의 순서가 바뀐 경우는 다른 경우로 센다' 라는 부분 때문에, 예를들어서 N이 1이라 해도 K가 5라면 1+0+0+0+0 / 0+1+0+0+0 / ... / 0+0+0+0+1 이 가능해진다 ㅋㅋㅋ 0의 더하는 순서라니 인지적으로는 좀 이상하긴 하지만, 사실 문제 푸는데는 상관없다! '2'를 보면 알겠지만, 그냥 1부터 N까지라고 해도 점화식이 달라질 뿐이다. 2. K-1개의 수를 합해 만든 어떠한 값이 있다. 이 값에 0부터 N까지의 정수를 더한다면 K-1개의 수로 만든 합에 1개의 정수를 더 더한 것이므로, K개의 수를 사용해 만든 어떠한 합이 될 것이다. 그렇다면 0부터 N까지의 정수를 사용해서, X개의 수를 합.. 2021. 12. 30.
백준 2133 자바 - 타일 채우기 (BOJ 2133 JAVA) 문제 : boj2133 1. 우선, 2x1과 1x2짜리 타일을 사용해야 하므로 무슨짓을 하던 n이 홀수라면 전체 칸 수(3 x n)가 홀수이므로 2칸짜리 타일로 타일링이 불가능하다. 즉, n이 짝수일 때만 타일링이 가능하다. 이 부분은 예외로 처리해준다. 2. 가장 기본적인 규칙성을 찾아보자. n=2일 때 3가지 모양이 나온다. 3. 그럼 n=4일 때는 n=2일 때 나왔던 모양에서 각각의 경우 3가지 모양이 더 추가되므로 'n=2일때의 모양 x 3'이 됨을 쉽게 알 수 있다. 예를 들어 위 n=2일때 중 첫번째 그림에 대해서만 그려보면 다음과 같다. 일단 여기까지, f(n)을 3 x n 타일링에서 n개의 가로칸으로 가능한 타일링의 경우의 수라 하자. 그럼 f(4) = f(2) * 3 임을 알 수 있다. .. 2021. 12. 30.
백준 2193 자바 - 이친수 (BOJ 2193 JAVA) 문제 : boj2193 1. N=1 일 때를 생각해보자. 0으로 시작하면 안되므로, 0으로 끝나는 수는 0개이고 1로 끝나는 수는 1개이다. (0과 1) 2. N=2 일 때를 생각해보자. 0으로 끝나려면 어떻게 해야 할까? 이 문제의 경우 1이 두번 연속으로 나오지 않기만 하면 된다. 따라서 이전 값이 0으로 끝나거나, 1으로 끝나거나 상관 없이 0을 붙일 수 있다. 반면에 끝이 1로 끝나려면 이전에 0으로 끝난 경우에 대해서만 1을 추가로 붙일 수 있다. 3. 이제 위의 규칙을 계산하기 위해 dp를 사용해보자. dp[n][x(=2)]를 n자리수에서 x로 끝나는 경우의 수라 정의하자. 이 때 n=5인 경우에 대해 그려보면 다음과 같다. 점화식으로 나타내면 dp[n][0] = dp[n-1][0] + dp[.. 2021. 12. 30.
백준 2294 자바 - 동전 2 (BOJ 2294 JAVA) 문제 : boj2294 1. 우선 문제에서 필요없는 정보를 제한해보자. 1.1 '사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.' -> 이 조건은 해당 가치를 표현하는 경우의 수를 구할때나 의미가 있다. '사용한 동전의 최소 개수'를 구하는 문제이므로 무시해도 된다. 1.2 '가치가 같은 동전이 여러 번 주어질 수도 있다.' -> 가치가 동일한 동전의 경우 연산을 느리게 할 뿐이므로, 동일한 동전이 주어진 경우는 HashSet 등을 사용해 제거하면 될 것임을 생각할 수 있다. 1.3 'k 2021. 12. 30.
백준 2293 자바 - 동전 1 (BOJ 2293 JAVA) 문제 : boj2293 1. 우선 문제를 좀 더 간단히 변경해서 봐보자. 1,2,5의 가치를 가지는 동전이 있고, 그 가치의 합이 10이 되게 하려 한다. 그리고 문제와 다르게 동전의 구성이 같아도 순서가 다르면 다른 경우로 치고 생각해보자. 그럼 1차원 배열을 활용한 dp로 아래와 같이 풀 수 있다. (냅색 문제처럼 풀면 된다.) 1.1 우선 초기값이다. dp[idx]는 1,2,5의 동전들을 가지고 idx의 가치를 가지는 경우의 수를 나타낸다. dp[0]은 실제론 불가하지만, 초기값으로 넣어준다. 그래야 동전 하나를 가지고 표현할 수 있는 경우에 대해서도 별도로 처리하지 않고 점화식 하나로 계산하기 편하다. (예를들어 2의 가치를 표현하려면 동전2짜리 하나만 쓸 수 있다. 식으로는 dp[2-2]이다. .. 2021. 12. 29.

티스토리툴바