밤이 블로그

카카오 모의 테스트 문제(Java) 문제 풀어본거 코드 올려봅니다. 궁금하신 점이나 코드에서 고쳐야할 부분이 있다면 댓글 달아주세요. * 문제 1, 2, 3 : 쉬움* 문제 4, 5, 6, 7 : dp 문제 * 문제 5- 재귀 형태로 풀이 시 (Java) 효율성 테스트 실패, 바텀업 방식으로 풀이 시 효율성 테스트 성공. 두 경우 걸리는 시간은 비슷함.(두가지 방식의 코드 모두 올려놨습니다) - 제가 올린 바텀업 코드에서 메모리를 더 많이 절약할 수 있습니다. dp배열을 [100001][4]로 선언하지 않아도 됩니다. * 문제 7- 문제 7번의 경우에도 재귀 형태로 풀이 시 (Java) 효율성 테스트 실패. 문제 #1/** * 자연수 N이 주어지면, N의 각 자릿수의 합을 구해서 return 하는 sol..

BOJ#1219 오민식의 고민 * 문제https://www.acmicpc.net/problem/1219 * 풀이벨만-포드 최단거리 문제입니다. 간선 cost는 음수이고, 각 노드마다 추가로 돈을 벌 수 있습니다.원하는 것은 S(시작점)에서 D(도착점)까지 갈 때 최대로 벌 수 있는 돈의 액수를 구하는 것입니다. 일반적으로 문제에서 간선의 cost가 양수로 주어지는 반면,이 문제에서는 간선 cost가 음수이므로음수 사이클은 문제가 되지 않고 반대로 양수 사이클인 경우가 문제 됩니다. 벨만-포드 알고리즘에 따라 (엣지수(M)만큼 Relaxation)을 N-1번 반복하고N번째에도 Relaxation이 되면 사이클이 존재함을 알 수 있습니다. 그러나 우리는 사이클 유무를 판단하는 것이 목적이 아니라시작점에서 도..

BOJ#6603 로또 * 문제https://www.acmicpc.net/problem/6603 * 풀이주어진 숫자에서 6개의 숫자를 고르는 문제입니다. 간단히 조합을 돌려서 해결했습니다. 각각의 숫자에 대하여 뽑는 경우, 뽑지 않는 경우로 나누고잘뽑은 경우에만 출력을 했습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%236603/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static voi..

BOJ#4191 Dominos 2 * 문제https://www.acmicpc.net/problem/4191 * 풀이어렵지 않은 문제였습니다.풀이는 아래 코드로 대체합니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/master/BOJ%234191/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class Main { static ArrayList edge; static boolean[] visited;..

BOJ#2412 암벽 등반 * 문제https://www.acmicpc.net/problem/2412 * 풀이BFS를 통해 암벽 정상까지 최소 이동 횟수를 구하면 됩니다.- 일단 Start 노드를 시작으로 인접한 노드들을 탐색하고 조건에 맞는 노드들만 다시 Queue에 넣어줍니다.- 조건 : |a-x| o2.col) return 1; if (o1.col == o2.col) { if (o1.row o2.row) return 1; } return 0; }; Queue queue = new LinkedList(); queue.add(new Node(0, 0)); int step = -1; while (!queue.isEmpty()) { step++; ..

a^3 + b^3 = c^3 + d^3 을 만족하는 100 이하의 자연수를 모두 찾아보자 a, b, c, d는 자연수이므로 a^3 + b^3의 결과도 어떤 자연수 x로 표현할 수 있다. 즉, 아래와 같이 표현할 수 있다. a^3 + b^3 = c^3 + d^3 = x 다시 바꾸어 말하면, 어떤 자연수 x는 위 조건을 만족하는 두 자연수의 쌍의 집합으로 표현할 수 있다. a^3 + b^3 = c^3 + d^3 = x1 [(a11^2 + b11^2), (a12^2 + b12^2), ...] = x2 [(a21^2 + b21^2), (a22^2 + b22^2), ...] = x3 [(a31^2 + b31^2), (a32^2 + b32^2), ...] = ... 이제 우리는 위 형태의 자료구조를 만들고 집합의 ..

BOJ#1963 소수 경로 * 문제https://www.acmicpc.net/problem/1963 * 풀이- 구하는 것 :두 소수 변환에 필요한 최소 변환 횟수 (최단 경로, 가중치 1이고 경우의 수가 많지 않으므로 BFS 탐색 가능) - 조건 : 4자리수, 소수로만 이동 가능, 중복 방문 x - 예를 들어 Test Case가 '1033 8179'인 경우 step = 0;1) 1033에서 한자리수를 변경해서 만들 수 있는 모든 소수들을 구한 후 Queue에 넣는다. (step = 1)2) step == 1인 Queue에 들어있는 모든 수에 대해 반복 (step = 2)3) step == 2인 Queue에 들어있는 모든 수에 대해 반복 (step = 3)....결국 step == n에서 8179를 찾게 ..

BOJ#4485 녹색 옷 입은 애가 젤다지? * 문제https://www.acmicpc.net/problem/4485 * 풀이다익스트라 (Priority Queue 이용)개념만 알면 풀 수 있는 기본 문제이므로 설명은 생략합니다. * 나의 코드 https://github.com/stack07142/BOJ/blob/7abd485c7bdc3853570ff8d262afbd03b7234709/BOJ%234485/src/Main.java import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.PriorityQueue; import java.util.StringTokenize..

BOJ#6549 히스토그램에서 가장 큰 직사각형 * 문제https://www.acmicpc.net/problem/6549 * 풀이세그먼트 트리 + 분할정복으로 풀었습니다.어려워서 많이 고생한 문제입니다. - 구하는 것 : 히스토그램에서 가장 큰 직사각형 - 히스토그램은 막대의 집합이고, 모든 막대 x에 대하여 막대 x의 높이로 하면서 만들 수 있는 가장 큰 직사각형들을 구해봅시다.- 어떤 막대 x에 대하여 양쪽으로 직사각형을 확장해나가면, 막대 x 높이로 만들 수 있는 가장 큰 직사각형을 구할 수 있습니다. - 우리는 그것들 중 가장 큰 직사각형을 구하면 됩니다. - 그렇다면 [2 1 4 5 1 3 3]의 히스토그램이 주어졌을 때, 어떤 순서로 막대를 검사하면 될까요- 가장 작은 막대부터 (높이가 작은 ..

BOJ#1992 쿼드트리 * 문제https://www.acmicpc.net/problem/1992 * 풀이- 분할정복을 사용하는 알고리즘들은 대개 3가지의 구성 요소를 갖고 있습니다. 1. 문제를 더 작은 문제로 분할하는 과정(divide) 2. 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(merge) 3. 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(base case)(출처 : 알고리즘 문제 해결 전략) 위 해결 전략을 염두하고 문제를 풀어보았습니다.쉬운 문제이므로 풀이는 생략하겠습니다. * 나의 코드https://github.com/stack07142/BOJ/blob/master/BOJ%231992/src/Main.java import java.io.Buffer..