티스토리

팡트루야

검색하기

블로그 홈

팡트루야

pangtrue.tistory.com/m

배운 것을 정리하는 목적의 블로그입니다. ^__^

구독자: 6

방명록 방문하기

주요 글 목록

[백준 12865 : JAVA] 평범한 배낭 1. 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 2. 입력 첫 줄에 물품의 수 N($1 \le N \le 100$)과 준서가 버틸 수 있는 무게 K($1 \le.. 공감수 1 댓글수 0 2021. 9. 8.
[백준 15486 : JAVA] 퇴사 2 1. 문제 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다. 각각의 상담은 상담을 완료하는데 걸리는 기간 $T_{i}$와 상담을 했을 때 받을 수 있는 금액 $P_{i}$로 이루어져 있다. N=7인 경우에 다음과 같은 상담 일정표를 보자. 1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다. 상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다... 공감수 0 댓글수 0 2021. 9. 6.
[백준 17626 : JAVA] Four Squares 1. 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 $5^{2}$과 $1^{2}$의 합이다. 또한 $4^{2}+3^{2}+1^{2}$으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = $125^{2}+6^{2}+1^{2}+1^{2}$라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다. 자연수 $n$이 주어질 때, $n$을 최소 개수의 제곱수 합으로 표현하는 프로그램을 작성하시오. 2. 입력 입력은.. 공감수 2 댓글수 0 2021. 9. 6.
[백준 12100 : JAVA] 2048 (Easy) 문제 2048 게임은 4x4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다.) 게임의 룰은 다음과 같다. 보드판은 상, 하, 좌, 우로 이동할 수 있다. 앞의 블록과 값이 같다면 두 값을 더한 하나의 블록으로 합쳐진다. 한 방향으로의 이동에서 각각의 블록은 한 번씩만 합쳐질 수 있다. 이 문제에서 다루는 2048 게임은 보드의 크기가 NxN이다... 공감수 1 댓글수 0 2021. 8. 16.
[백준 10972 : JAVA] 다음 순열 문제 1부터 N까지의 수로 이루어진 순열이 있다. 이때, 사전순으로 다음에 오는 순열을 구하는 프로그램을 작성하시오. 사전 순으로 앞서는 순열은 오름차순으로 이루어진 순열이고, 가장 마지막에 오는 순열은 내림차순으로 이루어진 순열이다. N=3인 경우에 사전순으로 순열을 나열하면 다음과 같다. 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 입력 첫째 줄에 N($1 \le N \le 10,000)$이 주어진다. 둘째 줄에 순열이 주어진다. 출력 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. 풀이 해당 문제는 이름 그대로 다음에 오는 순열을 찾을 수 있는지를 묻는 문제입니다. 다음과 같은.. 공감수 3 댓글수 0 2021. 8. 9.
[백준 1931 : JAVA] 회의실 배정 / 그리디 문제 한 개의 회의실이 있는데, 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 [시작시간, 종료시간] 이 주어지고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 갯수를 구하라. 단, 회의는 한 번 시작하면 중단할 수 없고, 회의가 끝남과 동시에 다음 회의를 시작할 수 있다. 입력 첫째 줄에 회의의 수 N($1 공감수 1 댓글수 0 2021. 8. 3.
[백준 1700 : JAVA] 멀티탭 스케줄링 / 그리디 문제 풀이 이런 유형의 문제는 경우를 디테일하게 나누는게 중요하다. 필자는 가장 먼저 아래와 같이 최초 멀티탭에 사용할 전기용품의 콘센트를 다 꼽은 상태의 인덱스부터 시작하였다. 초기 세팅 - 멀티탭 구멍의 갯수만큼 사용할 전기용품의 콘센트를 순서에 맞춰 꼽는다. 1. 다음에 사용할 전기용품의 콘센트가 멀티탭에 꽃혀있는 경우 ----> 다음 인덱스로 패스~ 2. 다음에 사용할 전기용품의 콘센트가 멀티탭에 꽃혀있지 않은 경우 2.1. ~마지막에 사용할 전기용품까지 탐색하여 지금 꽃혀있는 것 중 앞으로 사용될 일이 없는 콘센트가 있는 경우 2.2. ~마지막에 사용할 전기용품까지 탐색하여 지금 꽃혀있는 것들 모두가 다음에 또 사용되는 경우 2.2.1. 지금 꽃혀있는 콘센트들 중 가장 늦게 다시 사용되는 콘센트.. 공감수 2 댓글수 0 2021. 8. 3.
[백준 2437 : JAVA] 저울 / 그리디 문제 풀이 이 문제는 수학적인 규칙을 찾아야 풀 수 있는 문제다. {1, 2, 3, 공감수 1 댓글수 0 2021. 8. 2.
[백준 2240 : JAVA] 자두나무 / DP 문제 풀이 만약 자두를 먹는 위치가 두 군데가 아니라, 한 군데였다면 훨씬 쉽게 느껴졌을지도 모른다. 한 군데라면 1차원이지만, 두 군데 이상부터는 2차원이 되기 때문이다. 예제 입력을 표로 나타내보면 다음과 같다. 현재 2초이고, 1의 위치에 있다고 하자. 얘가 이전에 있을 수 있는 위치는 두 군데다. 1. 1초에 1의 위치에 있을 경우 2. 1초에 2의 위치에 있을 경우 (이 경우 이동을 해야하기 때문에 현재 위치의 이동횟수-1 을 가진다) DP[현재 위치][시간][이동횟수] DP[1][2][W] = Math.max(DP[1][1][W], DP[2][1][W - 1]) + (해당 초에 해당 위치에 자두가 떨어지면 +1, 아니면 +0) 그리고 위의 점화식을 반복문으로 구성하기 위해, 초기 이동횟수를 0.. 공감수 2 댓글수 1 2021. 4. 22.
[백준 15990 : JAVA] 1, 2, 3 더하기 5 / DP 문제 풀이 기존의 1, 2, 3 만들기 문제에서 같은 수가 연속해서 오지 못 한다는 조건이 추가되었다. 따라서, 단순히 그 수를 만들기 위한 경우의 수만 저장해가지곤 점화식을 끄집어낼 수 없다. 두 가지 정보가 필요하다. N을 만들기 위한 경우의 수인데, 그 수식의 마지막이 어떤 수로 끝나는 것들. 7을 1, 2, 3의 합으로 나타내는 경우의 수를 살펴보자. 1) 7을 만드는 수식 중 마지막이 1로 끝나는 것의 수 6을 만드는 수식 중 마지막이 2로 끝나는 것 + 1 6을 만드는 수식 중 마지막이 3로 끝나는 것 + 1 DP[7][1] = DP[6][2] + DP[6][3] 2) 7을 만드는 수식 중 마지막이 2로 끝나는 것의 수 5를 만드는 수식 중 마지막이 1로 끝나는 것 + 2 5를 만드는 수식 중.. 공감수 1 댓글수 0 2021. 4. 21.
[백준 9084 : JAVA] 동전 / DP 문제 풀이 점화식을 어떻게 세워야할까 노트에 표를 그려보면서 고민을 해봤지만... 결국 풀이를 참고하였다. 문제를 단순화하여, 동전의 종류가 한 가지일 때를 생각해보자. 예를 들어, 동전의 종류 A = {2} 이고, 만들어야하는 수 K = 10 이라고 해보자. 2원짜리 동전으로 10원을 만들려면 어떻게 해야할까? (2*5=10 이니까 1가지겠네 뭐.. 라고 생각하셨다면 우리 DP 공부 열심히 합시ㅏ..) 이때, 구하고자하는 타겟인 10을 바로 생각하지 말고, 타겟을 기준으로 1부터 생각해보는 것이다. 2원짜리 동전으로 1원을 만드는 경우의 수는? 2원짜리 동전으로 2원을 만드는 경우의 수는? 2원짜리 동전으로 3원을 만드는 경우의 수는? 2원짜리 동전으로 4원을 만드는 경우의 수는? ... (중략) 2원.. 공감수 2 댓글수 0 2021. 4. 20.
[백준 2302 : JAVA] 극장 좌석 / DP 문제 풀이 점화식을 찾을 수 있는지 묻는 문제이다. 가장 먼저 노가다로 좌석이 4개일 때까지의 경우의 수를 구해보자. (DP에서 점화식을 찾을 때 3~4 정도까지는 노가다로 그려보자) 좌석이 1개일 때) 1 좌석이 2개일 때) 1 2 2 1 좌석이 3개일 때) 1 2 3 1 3 2 2 1 3 좌석이 4개일 때) 1 2 3 4 1 2 4 3 2 1 3 4 2 1 4 3 1 3 2 4 노가다로도 쉽게 구할 수 있는 4개까지 구해보니, [1, 2, 3, 5] 라는 수열을 얻을 수 있었다. DP[i] = DP[i - 1] + DP[i - 2] 인가... (가장 흔한 피보나치 수열 점화식) 대충 어림짐작해보고 좌석이 5일 경우로 넘어가보자. 좌석이 5개쯤부터는 노가다로 힘들어진다. 이 구간에서는 DP의 철학대로 .. 공감수 1 댓글수 2 2021. 4. 18.
[백준 10164 : JAVA] 격자상의 경로 / DFS + DP 문제 풀이 DFS + DP를 이용하는 기본유형의 문제다. DFS 탐색으로 경로의 수를 찾을 때, 중복되는 탐색 내용이 무엇인지에 대한 이해만 있으면 충분히 풀 수 있는 문제. 위 그림의 빨간색 노드(탐색을 진행 중인 노드)는 파란색 노드로 가는 탐색을 굳이 진행할 필요가 없다. 파란색 노드부터 목적지까지의 경로의 수를 이미 알기 때문이다. 위 개념만 제대로 이해하면, 나머지는 DFS로 탐색만 하면 쉽게 풀 수 있다. 코드 import java.io.*; import java.util.*; public class Main { private static int N, M, K; private static int[] dx = {0, 1}; private static int[] dy = {1, 0}; privat.. 공감수 1 댓글수 0 2021. 4. 17.
[백준 1890 : JAVA] 점프 / DP + DFS 문제 풀이 BFS로 문제를 풀어보려고 고민을 여러 차례해봤는데, BFS로는 탐색했던 곳을 재탐색하지 않으면서, 경로의 수를 누적시키는게 불가능하다고 판단했다. 반면, DFS를 이용하면 하나의 경로에 대해 온전히 보장받으면서 재탐색없이 경로의 수를 누적시키는게 가능하다. 아래의 그림을 참고하자. 즉, 도착점까지 탐색을 진행한 후에, 역으로 거슬러 올라오면서 경로의 값을 누적시키는게 포인트다. 코드 import java.io.*; import java.util.*; public class Main { private static int N; private static int[][] map; private static long[][] cache; private static int[] dx = {1, 0}; pr.. 공감수 2 댓글수 0 2021. 4. 10.
[백준 2225 : JAVA] 합분해 / DP 문제 풀이 DP의 핵심 중 하나는 초깃값 설정이다. 해당 문제는 0~N까지의 수열에서 K개의 정수를 선택해 N을 만드는 경우의 수니까 K=1일 경우부터 가정하여 생각해보자. 1개의 수를 선택해 N을 만드는 경우의 수는 무조건 1개이다. (N이라는 수 하나를 선택해야 N을 만들 수 있다.) K=2일 경우를 생각해보자. (N=6 이라 가정) N=6 이라고 가정하면, [0, 1, 2, 3, 4, 5, 6] 이라는 수열에서 2개의 정수를 선택해 6을 만들기 위한 방법은 아래와 같은 규칙을 가진다. [0, 1, 2, 3, 4, 5, 6] [0, 1, 2, 3, 4, 5, 6] [0, 1, 2, 3, 4, 5, 6] [0, 1, 2, 3, 4, 5, 6] 문제에서 (0, 6)을 선택하는 경우와 (6, 0)을 선택하.. 공감수 2 댓글수 0 2021. 4. 8.
[백준 2133 : JAVA] 타일 채우기 / DP 문제 풀이 먼저 N이 홀수일 경우는 타일로 완전히 채울 수 없다. 타일은 2의 배수인데, N이 홀수가 되어버리면 벽의 넓이가 홀수가 되기 때문이다. 즉, 타일로 벽을 가득 채우기 위해선 벽의 넓이가 2의 배수가 되어야하는데, N이 홀수면 벽의 넓이가 홀수가 되어버리기 때문이다. 따라서 첫 시작은 N이 2인 경우부터이다. 다음 짝수인 N=4인 경우를 생각해보자. 3*4 = 3*2 + 3*2 // N=2인 경우를 두 번 합한 것으로 생각해볼 수 있다. 그럼 N=2일때 3가지 경우의 수를 가졌으니, N=4는 3*3=9가지 경우의 수를 가질까? 3*2로는 만들 수 없었지만, 3*4로는 만들 수 있는 추가적인 경우의 수가 2개 존재한다. 따라서, N=4는 11가지가 된다. 참고로, 예외 케이스에 대해선 노가다로 .. 공감수 3 댓글수 0 2021. 4. 6.
[백준 7469 : JAVA] K번째 수 / MergeSort Tree 문제 풀이 어떤 식으로 K번째 수를 찾을 수 있을까 고민을 많이 했던 문제다... i~j 구간에서 k번째 수가 X라고 하자. 우리는 이 X가 뭔지 모르기 때문에 찾아나가야 한다. MergeSort Tree 특성상 각 노드가 담당하는 구간은 정렬된 상태의 배열이기 때문에 k번째 수인 X보다 작은 수의 갯수는 k-1개가 된다. 문제의 조건상 X가 될 수 있는 값의 범위는 $-10^{9}$~$10^{9}$ 이니까, 이를 토대로 이분탐색을 진행해나간다. 즉, MergeSort Tree의 쿼리 함수가 담당하는 기능은 해당 구간에서 파라미터로 들어온 값보다 작은 수의 갯수이다. [1, 2, 3, 8] 수열이 있고, 2~4 구간에서 3번째 값을 찾는다고 했을 때, X가 될 수 있는 후보는 4~8이다. 즉, X보다 .. 공감수 2 댓글수 0 2021. 4. 2.
[백준 3653 : JAVA] 영화 수집 / 세그먼트 트리 문제 풀이 세그먼트 트리 응용문제로, 창의성을 요구하는 문제다. 한 번 보고난 영화 DVD는 위로 옮겨져야 하기 때문에 옮겨질(m)만큼의 크기도 추가해 배열을 할당한다. 3번 영화를 보고난 후에는 3번 영화의 인덱스를 변경해줘야 하기 때문에, 각 [영화 번호, 인덱스] 쌍을 알고 있어야 한다. 영화번호-인덱스 쌍을 저장하기 위해 Map(=Dictionary) 자료구조를 이용하는 대신, 좀 더 원시적인 방법인 배열을 이용했다. for (int i = 1; i 0) { StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); in.. 공감수 1 댓글수 0 2021. 3. 30.
[백준 10090 : JAVA] Counting Inversions / 세그먼트 트리 문제 풀이 Inversion 이란 $A[i]>A[j]$ (단 $i 1; return segmentTree[node] = update(start, mid, node * 2, pos) + update(mid + 1, end, node * 2 + 1, pos); } // [left, right] : 구하고자하는 구간 private static int query(int start, int end, int node, int left, int right) { if (right < start || end < left) return 0; if (left 1; return query(start, mid, node * 2, left, right) + query(mid + 1, end, node * 2 + 1, left, .. 공감수 1 댓글수 0 2021. 3. 25.
[백준 2954 : JAVA] 창영이의 일기장 / 정규 표현식 문제 풀이 다른 분들은 어떤 식으로 풀었나 검색해보니 정규 표현식으로 푼 풀이는 없길래 도움이 되었으면 하는 마음으로 올려본다..! 찾아야할 패턴은 모음 + 'p' + 모음 이다. 만약 세 문자를 하나로 처리한다면, 대체해야할 모음을 적어줄 수가 없기 때문에 각자 처리한다. 예를 들면, apa -> a 로 바꿔줘야하는데, apa를 하나로 보면 바꿔줘야할 문자를 적어줄 수가 없다. 그래서 한 단어씩 처리한다. 정규 표현식에서 제공하는 기능 중 사용한 기능은 다음과 같다. 논-캡쳐링을 의미하는 (?:) 공감수 1 댓글수 0 2021. 3. 22.
[백준 9202 : JAVA] Boggle / 트라이 + DFS 문제 풀이 푸는데 반나절걸렸다.. (한 5시간즘..?) 그래도 혼자 힘으로 풀어서 뿌듯하다 .. 일단 단어 사전에 들어가는 단어들은 트라이 구조에 담았다. 일반적인 트라이 방법대로 구현하였고, 한 가지 추가한 부분이 있다면 기존의 find() 메서드에서 bool 타입으로 완전한 문자열을 검색할건지에 대한 파라미터를 받았다. boolean find(String key, boolean isCompleteString) { // ... } 원래의 find() 메서드의 역할은 해당 문자열이 있는지를 검색하는 것인데, 이 기능을 확장해 접두사 문자열에 대해서도 확인할 수 있게 했다. {"Hello", "He"} 두 개의 문자열이 있을 때, 완전한 문자열 검색이라면 "Hel" 이라는 문자열은 존재하지 않는 문자열이라.. 공감수 1 댓글수 0 2021. 3. 14.
[백준 11066 : JAVA] 파일 합치기 / DP + 최적화 문제 풀이 DP[i][j]를 i에서 j까지의 최소비용이라고 하면, 해당 문제의 점화식은 다음과 같다. DP[i][j] = min(DP[i][j], DP[i][k] + DP[k + 1][j]) (단, i < k < j) 위의 점화식은 총 3개의 변수가 각각의 for문을 구성해 O($N^{3}$)의 시간 복잡도가 걸린다. for (int i = 2; i 0; j--) { dp[j][i] = Integer.MAX_VALUE; for (int k = j; k 공감수 1 댓글수 1 2021. 3. 9.
[백준 14476 : JAVA] 최대공약수 하나 빼기 / 세그먼트 트리 + 유클리드 문제 풀이 N의 최대값이 $10^{6}$ 이기 때문에 단순한 완전 탐색(이중 루프)을 하게 되면 시간초과가 걸린다. 따라서, 세그먼트 트리를 이용한다. (세그먼트 트리가 뭔지 모른다면 ---> pangtrue.tistory.com/299) 만약 N=8이라면 세그먼트 트리의 모양은 다음과 같다. 배열을 이용해서 저장할 것이고, 루트 노드부터 순서대로 1번 인덱스에 값이 저장될 것이기 때문에, 가장 처음 리프 노드의 인덱스를 구한다. // 원소의 갯수에 따른 첫 번째 리프 노드의 인덱스를 구한다. // 예를 들어, n이 [2^2+1, 2^3]이면 첫 번째 리프노드 인덱스는 8 // n이 [2^3+1, 2^4]이면 첫 번째 리프노드 인덱스는 16 int getFirstLeafNodeIdx(int n) { in.. 공감수 1 댓글수 0 2021. 3. 6.
[백준 2168 : JAVA] 타일 위의 대각선 / 수학 문제 풀이 먼저, 분자와 분모의 최대공약수가 1인, 쉽게 말해 $\frac{3}{2}$, $\frac{4}{3}$ 와 같은 기약분수 형태에 대해 그림을 그려보자. 위의 그림을 통해 직사각형에 대각선을 그으면 $(x-1)$개의 세로줄, $(y-1)$개의 가로줄을 지난다는 것을 알 수 있다. 즉, 대각선이 그어진 타올의 수는 처음 선을 긋기 시작한 타올의 수를 더한 $(x-1)+(y-1)+1$ 이라는 것을 알 수 있다. 최대공약수가 2 이상인 것 부터는 중간에 최대공약수가 1인 지점을 기준으로 가로줄, 세로줄이 아닌 꼭지점을 지나게 되므로 의미가 없다. 즉, 최종 식을 도출해보면 $gcd(x, y) * ((x / gcd(x, y)-1)+(y / gcd(x, y)-1)+1)$ 이 된다. 위에서 도출된 식을 풀.. 공감수 1 댓글수 0 2021. 3. 4.
[백준 2436 : JAVA] 공약수 / 유클리드 호제법 문제 풀이 해당 문제를 풀기 위해선 다음의 수학적 정리를 알고 있어야 한다. 임의의 두 수 $x$, $y$에 대해서 최대공약수($gcd(x, y)$) * 최소공배수($lcm(x, y)$) = $x * y$ 이다. (단, $x$, $y$는 최대공약수의 배수) 즉, 우리가 해야할 건 $x * y$의 약수이면서, 최대공약수의 배수인 수를 찾아야 한다. 알고리즘은 다음과 같다. (편의상, 최대공약수는 A, 최소공배수는 B 라고 표현) 최대공약수와 최소공배수가 주어지면 두 수를 곱해 $x*y$를 구한다. 최대공약수의 배수 중 $xy$의 약수인 수를 $i$라고 한다면, $i$와 $xy/i$ 쌍을 얻을 수 있다. $i$와 $xy/i$ 쌍의 최대공약수가 A라면 이 둘은 우리가 찾고자하는 쌍이다. 이전에 찾아놓은 $i$.. 공감수 1 댓글수 0 2021. 3. 4.
[백준 11051 : JAVA] 이항 계수2 / 조합 + DP 문제 풀이 이항 계수: n개의 서로 다른 물건 중에서 순서없이 k개를 뽑는 가짓수 이항 계수를 식으로 표현 ---> $n \choose k$ = $\frac{n!}{k!(n-k)!}$ = ${}_n \mathrm{ C }_k$ 위의 이항 계수의 공식대로 팩토리얼로 풀게될 경우 N의 최대값이 1000이기 때문에 $1000!$를 계산해야되서 적절하지 못하다. 대신, 파스칼의 삼각형 원리를 이용해 DP로 풀 수 있다. 즉, ${}_n \mathrm{ C }_k$ = ${}_{n-1} \mathrm{ C }_{k-1}$ + ${}_{n-1} \mathrm{ C }_k$ 라는 식을 이용한다. 코드 import java.io.*; import java.util.*; public class Main { public .. 공감수 1 댓글수 0 2021. 3. 3.
[백준 17825 : JAVA] 주사위 윷놀이 / 백트래킹 + 시뮬레이션 문제 풀이 개인적으로 많이 어려웠던 문제. 해당 문제에서 요구하는 요구사항은 크게 2가지다. 주어진 맵(윷놀이판)을 어떻게 표현할 것인가? 10개의 턴에 대한 4개의 말 순서 배치는 어떻게할 것인가? (순열 --- 백트래킹 알고리즘 이용) 먼저 첫 번째 요구사항을 보자. 주어진 윷놀이판을 1차원으로 보기 쉽게끔 나타내면 다음과 같다. 위의 1차원 구조에서 포인트는 10, 20, 30은 두 가지 방향을 가진다는 것이다. 그럼 노드가 가져야할 정보는 다음과 같다. 해당 칸의 점수, 해당 칸이 비었는지(다른 말이 있는지), 지름길(파란 방향)이 있는지, 도착점인지 배열에 담아도 되지만, 그보다는 연결 리스트로 담는게 좀 더 직관적이라 생각한다. ( 개인적으로 아래와 같이 연결 리스트를 만들어 사용해보는건 처음.. 공감수 1 댓글수 0 2020. 11. 22.
[백준 1339 : JAVA] 단어 수학 / 백트래킹 문제 풀이 문제를 단순화해보자. 예를 들어, 주어진 문자열이 다음과 같이 2개 주어졌다면 ABC BCDE 위의 문자열에서 사용된 문자는 A B C D E ---> 5개다. 즉, 0~9까지의 수열에서 5개의 부분수열을 구하는 문제로 바라볼 수 있다. 입력 문자열과는 별도로 어떤 문자들이 사용되었는지 파악이 필요한데, 아래와 같이 List 자료구조에 하나씩 순차적으로 담는다. for (int i = 0; i < N; i++) { words[i] = br.readLine(); // 입력 문자열 for (int j = 0; j < words[i].length(); j++) { if (!alpabetList.contains(words[i].charAt(j))) { alpabetList.add(words[i].ch.. 공감수 1 댓글수 0 2020. 11. 9.
[백준 2529 : JAVA] 부등호 / 백트래킹 문제 풀이 N개의 수열에서 M개의 수열을 찾는 N과 M 문제와 비슷하다. 0~9의 고정된 수열이 있고, 주어진 부등호 조건을 만족하는 수열을 찾으면 된다. DFS 탐색의 깊이(인덱스)가 주어진 부등호의 갯수+1을 만족한다면 해당 수열은 부등호 조건을 만족하는 수열이다. 조건에 만족하는 모든 수열을 list에 모두 저장한 후, 정렬한 다음 처음과 마지막 값을 출력한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { private static BufferedReader br = new BufferedReader(n.. 공감수 2 댓글수 0 2020. 11. 8.
[백준 15684 : JAVA] 사다리 조작 / 백트래킹 문제 풀이 개인적으로 되게 어려웠던 문제였다. 풀이를 보면서도 많은 시간 고민했다. 첫 번째로 고민했던건 주어지는 가로선의 정보를 어떤 식으로 저장할까였다. 그동안 풀었던 문제는 대게 칸으로 주어졌기 때문에 별 생각없이 map[y][x] 에 저장하면 됬지만, y축과 x축이 칸이 아닌 선으로 주어져서 고민했는데, 그냥 아래처럼 칸이라 생각하고 똑같이 저장하면 되겠다라고 생각이 들었다. 위의 그림에서 최상단 좌측을 (1, 1)이라 두고, 값이 저장되는 세 가지 경우를 나눴다. 0 : 해당 칸에는 가로선이 없다. 1 : 해당 칸을 기준으로 우측으로 연결되는 가로선이 있다. 2 : 해당 칸을 기준으로 좌측으로 연결되는 가로선이 있다. 1번 높이의 1번과 2번 세로선을 연결하는 가로선이 있다면, map[1][1].. 공감수 1 댓글수 0 2020. 11. 8.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.