SY DevLog

1185번: 유럽여행 첫 줄에는 방문할 나라의 수 N(5 ≤ N ≤ 10,000)과 이 나라들 사이를 연결하는 길의 수 P(N-1 ≤ P ≤ 100,000)가 주어진다. 두 번째 줄에는 N+1번째 줄까지 i+1번째 줄에는 i번째 나라를 방문할 때 드는 비 www.acmicpc.net 전체 나라 개수가 N개이고, 이어져 있는 길이 N-1개 일 때, 최소 비용으로 어느 시작 나라 하나를 정해서 모든 나라를 다 방문한 후 다시 시작 나라로 돌아오기 위해서는 나라는 2*N-1개를 방문하고, 길은 2*(N-1)번을 지나야 한다. 따라서, 각 길의 비용은 이어져 있는 두 나라의 비용 + 길의 비용*2 로 정하면 된다. 예를 들어, 1번과 2번 나라 사이의 길의 비용은 1번 나라의 비용(10) + 2번 나라의 비용(..

14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net 백준 2206번 : 벽 부수고 이동하기 문제와 비슷하다. 기존의 벽 부수고 이동하기 문제에서는 벽을 한 번만 부수는 게 가능했는데, 이번 문제에서는 K가 주어지면, K개만큼 벽을 부수면서 이동이 가능하다. 벽 부수고 이동하기에 대한 풀이는 아래 포스팅을 참고 https://lotuslee.tistory.com/142 [백준 2206번] 벽 부수고 이동하기 (java) 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이..

2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 처음에는 일반적인 너비우선탐색(BFS) 방법처럼 visited 배열을 2차원 배열로 만들어서 문제를 풀었으나, 11%에서 틀렸다고 나왔다. 특정 위치(nr, nc)에 도착했을 때, 그 위치까지 도달하는 과정에서 벽을 한 번 부수고 도달했는지, 한 번도 부수지 않고 도달했는지 이 두가지 경우를 모두 고려해서 방문처리를 해야 한다. 따라서 visited 배열을 2차원 배열이 아닌 3차원 배열로 만들어서 1. 벽을 부수지 않고 방문한 경우 :..

백준 전깃줄 문제와 유사하다. 이진탐색을 사용한 증가하는최장부분수열(LIS)을 구하는 문제이다. 다만, 수열의 길이만 구하는 것이 아니라 수열 자체도 구해야 하므로 역추적하는 배열이 별도로 필요하다. 역추적을 통한 증가하는최장부분수열의 수열 구하는 방법은 아래 포스팅에 나와있다. LIS(Lowest Increasing Subsequence) - 수열 구하기 저번 글에서는 최장 증가 수열의 길이를 구하는 경우에 대해 다루었다. LIS(Lowest Increasing Subsequence) - 길이 구하기 LIS(Lowest Increasing Subsequence) : 최장 증가 수열 : 어떤 수열이 주어졌을 때, 그.. lotuslee.tistory.com 이 문제는 전선이 만나지 않도록 하면서 전구가 ..

싱글톤 패턴 : 인스턴스를 하나만 생성하고 싶을 때 사용하는 디자인 패턴 싱글톤 인스턴스, 생성자, 인스턴스를 반환하는 메서드 이렇게 세가지가 필요하다. 싱글톤 인스턴스 private static Singleton instance; 인스턴스가 하나만 생성되어야 하므로 외부에서 함부로 접근할 수 없도록 private static으로 선언한다. 클래스가 로드될 때 한번만 생성된다. 싱글톤 생성자 private Singleton(){} 외부에서 생성자를 통해 인스턴스를 생성하지 못하도록 private으로 지정한다. 싱글톤 getter public static Singleton getInstance(){ return instance;} 외부에서 인스턴스를 얻기 위한 유일한 통로 외부에서 접근할 수 있어야 하므로..

20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 토네이도의 방향 순서가 서쪽 -> 남쪽 -> 동쪽 -> 북쪽 순서대로 반복된다. direct 3차원 배열을 만들어서, - 첫 번째 인덱스는 방향(0: 서쪽, 1:남쪽, 2:동쪽, 3:북쪽)을 의미하고, - 두 번째 인덱스는 0일 경우 r 좌표(행 좌표), 1일 경우 c 좌표(열 좌표)를 나타내었다. - 세 번째 인덱스는 현재 위치를 기준으로 1%비율에 해당하는 위치, 2%에 해당하는 위치, 5%에 해당하는 위치, 7%에 해당하는 위..

9202번: Boggle 각각의 Boggle에 대해, 얻을 수 있는 최대 점수, 가장 긴 단어, 찾은 단어의 개수를 출력한다. 한 Boggle에서 같은 단어를 여러 번 찾은 경우에는 한 번만 찾은 것으로 센다. 가장 긴 단어가 여러 개 www.acmicpc.net DFS와 트라이 알고리즘을 통해 문제를 해결하였다. 게임 사전에 등재된 단어들을 트라이에 넣는다. 각 보드마다 DFS방식으로 접근하면서 여태까지 지나온 알파벳들로 이루어진 단어가 트라이에 포함되어 있는지를 확인한다. 문제에서 같은 단어를 여러 번 찾은 경우는 하나로 간주한다고 했으므로 중복을 피하기 위해 찾은 단어를 HashSet에 넣어주었다. 기존의 트라이의 contains() 메서드는 true 혹은 false를 반환하였다.특정 단어에 트라이..

5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net parent라는 ArrayList 리스트 배열을 만들어서 현재 노드의 직전 노드를 저장하는 공간을 만들어주었다. 현재 노드에 최소 경로로 도달할 수 있는 직전 노드가 여러 개 있으면, ArrayList에 여러 개를 넣는다. 예를 들어, 위의 문제 예제 그림에서 D = 6에 최소 경로로 도달할 수 있는 경우의 수는 2가지이다. 이 때 각각의 경우에서 6번 노드의 직전 노드는 3번과 5번 노드이다. 따라서 parent[6]에는 {3, ..

20055번: 컨베이어 벨트 위의 로봇 길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부 www.acmicpc.net int[] A = new int[2*N+1] : 칸 별로 내구도를 의미 int[][] num = new int[2][N+1] : 각 위치에 무슨 번호의 칸이 있는지를 의미 컨테이너 벨트의 가장 왼쪽 위가 [0][1], 가장 오른쪽 위가 [0][N], 가장 왼쪽 아래가 [1][1], 가장 오른쪽 아래가 [1][N] 위치를 의미한다. 처음에는 num[0][1] = 1번 칸, num[0][2] = 2번 칸, ... num[0][N]= N번 칸 ....

3653번: 영화 수집 각 테스트 케이스에 대해서 한 줄에 m개의 정수를 출력해야 한다. i번째 출력하는 수는 i번째로 영화를 볼 때 그 영화의 위에 있었던 DVD의 개수이다. 상근이는 매번 영화를 볼 때마다 본 영화 DVD www.acmicpc.net 다른 풀이를 참조하여 문제를 풀었다. 세그먼트 트리로 푸는 방법이다. 우선, n+m 크기로 배열을 만들어야 한다. 0부터 (m-1) 인덱스까지는 0으로 초기화를 하고, m부터 (n+m-1) 인덱스까지는 1로 초기화를 한다. 0이 들어간 공간은 빈공간을 의미한다. DVD를 꺼내서 맨 위에 쌓을 때마다 이 빈공간의 맨아래(m-1)에서부터 1로 채워진다. 원래 DVD가 있던 위치의 1은 0으로 변경된다. n번 DVD가 위의 배열 중에 어디에 있는지 그 위치(인..