초보개발자의 작은 끄적임

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 풀이 방법 다익스트라 알고리즘 관련된 문제를 이번에 처음 접해보았다. 푸는데 해당 알고리즘을 코드로 구현하는데는 어렵지 않았다. 하지만, 1. 메모리 초과로 인해 인접리스트와 1차원 배열로 변경 2. 시간 초과로 인해 우선순위 큐로 변경 3. INF의 범위 이렇게 고려해야할 요소들이 많아 풀었던 문제를 수정하는데에 정말 많은 시간이 소요되었다. 중간에 정말 때려치우고 싶었다. 아예 모르는 문제보다 아는데 계속 빙빙 돌아서 가는 느낌의 ..

2448번: 별 찍기 - 11 첫째 줄에 N이 주어진다. N은 항상 3×2k 수이다. (3, 6, 12, 24, 48, ...) (0 ≤ k ≤ 10, k는 정수) www.acmicpc.net 풀이 방법 처음에 구현했을 때 로직은 맞았지만 시간초과가 떴다. 그 이유는 2중 for문으로 System.out.print()로 배열을 여러번에 걸쳐서 출력을 했기 때문이다. 그래서 한번에 출력하도록 하기 위해서 StringBuilder를 이용했다. 하지만 그 다음에는 틀렸습니다가 떴다. 그 이유는 백준에서는 null을 읽으면 발생한다고 한다. 그래서 char 2차원 배열을 ' ' 빈 공백으로 초기화 해주었다. 구현 코드 import java.io.BufferedReader; import java.io.IOExce..

1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 방법 지수를 나누어 재귀로 푸는 것이 이 문제의 핵심이다. 다른 코드들을 살펴보면 함수 전달 시 A인자에 A%C를 전달해 주는 경우가 있다. 이 부분이 이해가 안가서 찾아보던 중 함수 안에서 if (B == 1) return A % C; 이와 같은 제약조건을 준다면 그냥 A를 전달해주어도 된다. 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokeni..

1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또 www.acmicpc.net 풀이 방법 분할정복(Divide and Conquer)으로 푸는 문제이다. 해당 영역이 모두 0인지 혹은 모두 1인지 확인해 같으면 출력하고, 그렇지 않으면 상, 하, 좌, 우 4영역으로 나누어(divide) 정복(conquer)하는 STEP으로 이루어져있다. 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public c..

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 방법 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Q_1520 { static int N, M; static int[][] array, dp; static..

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 방법 처음에는 모든 경우의 수를 1개일 때, 2개일 때, ..., 10개일 때로 나누어서 생각해보았는데 시간복잡도가 O(n^3)이 나와서 의미 없다고 생각했다. 그래서 이 문제는 dp로 밖에 못 푸는구나 하고 깨달았다. 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public ..

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 방법 점화식을 세우는 건 익숙하지 않아서 정말 어렵다. 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q_2293 { public static void main(String[] args) throws IOException { BufferedRead..

2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 풀이 방법 여기서 같은 값을 가지는 2차원 배열이 2개 존재하도록 문제를 풀었기 때문에 shallow copy와 deep copy의 차이를 알아야한다. 먼저 shallow copy는 원본 참조변수의 참조값만 복사하는 것이고, deep copy는 원본 참조변수의 참조값이 가르키는 객체를 메모리 공간에 복사 생성 후 복사본 참조변수가 가르키는 것을 의미한다. 좀 더 쉽게 말하면 shallow copy는 복사 후 원본이나 복사본을 수정하면 둘 다 동일한 객체를 ..

1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 방법 왼쪽 위의 대각선과 오른쪽 위의 대각선에 존재하는 값을 비교해 큰 값을 더해주는 방식으로 위에서 아래로 가는 방법을 선택했다. 마지막 배열에 존재하는 값들 중에서 가장 큰 값이 최대가 되는 경로에 있는 수의 합이된다. 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q_1932 { static int n; publ..

2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 풀이방법 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q_2468 { static int N; static int[][] array, visited; static int[] x = { -1, 1, 0, 0 }; static int[] y = { 0, 0, ..