1. 문제https://www.acmicpc.net/problem/1238 2. 문제 설명이 문제는 N개 숫자로 구분된 각각의 마을이 존재하며, 각 마을에는 한 명의 학생이 살고있다.각 마을을 이어주는 시간이 T만큼 걸리는 단방향 도로가 존재한다.학생들은 파티를 위해 X마을로 모여서 파티하고 끝나며 다시 자기가 살던 마을로 돌아간다.이 때 각 학생들은 최단 시간을 통해서만 이동한다.여기서 가장 시간이 오래걸린 학생의 걸린 시간을 출력하는 문제이다. 이 문제는 다익스트라 알고리즘을 통해서 해결할 수 있다.다익스트라를 풀어본 적이 없다면, 아래 문제를 먼저 풀어보는 것을 추천한다.https://soonmin.tistory.com/179 [백준] 1753. 최단경로 - JAVA1. 문제https://www...
Algorithm
1. 문제https://www.acmicpc.net/problem/1504 2. 풀이 과정무방향 그래프가 주어질 때 시작점(1)에서 도착점(N)으로 가는 최단 경로를 구하는 문제이다. 여기까지는 일반적인 최단 경로를 구해서 문제를 해결 할 수 있다. 하지만 이 문제는 조건이 있다. 시작점에서 출발해 반드시 v1, v2 지점을 통과한 뒤 도착점까지의 최단 경로를 구해야 한다. 문제 접근 방식v1, v2 지점을 통과하는 최단 경로를 구하기 위해 두가지 케이스를 고려해야 한다.1(시작점) -> v1 -> v2 -> N(도착점)1(시작점) -> v2 -> v1 -> N(도착점) 각각의 케이스에 따라 최단 경로를 구한 뒤, 둘 중에 더 작은 케이스의 결과를 출력해주면 된다. 만약, 두 케이스 모두 INF ..
1. 문제https://www.acmicpc.net/problem/1753 2. 풀이 과정이 문제는 방향 그래프와 시작점 K가 주어진다. 시작점에서 출발해 다른 모든 정점까지의 최단 경로를 구하는 문제이다.경로가 존재하지 않으면 INF를 출력한다. 이 문제는 다익스트라(Dijkstra) 알고리즘을 활용하는 가장 기본적인 문제이다. 다익스트라 알고리즘가중치가 있는 그래프에서 하나의 시작점으로부터 다른 모든 정점가지의 최단 거리를 구하는 알고리즘이다.항상 현재까지 발견된 최단 경로 중 가장 짧은 경로부터 확정해 나가는 방식이다. 동작과정시작 노드의 최단 거리를 0으로 설정, 다른 모든 노드는 INF로 초기화방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택그 노드를 거쳐서 다른 노드로 가는 비용을 계산..
1. 문제https://www.acmicpc.net/problem/13460 2. 풀이 과정N x M 크기의 게임판이 주어지며, 각 영역은 빨간구슬(R), 파란구슬(B), 빈칸(.), 벽(#), 구멍(O)으로 구분된다.빨간구슬 파란구슬 각각 1개 씩 주어지며, 가장 바깥 행과 열이 벽으로 막혀있다.이 때, 게임판을 상,하,좌,우로 기울이며, 구슬은 벽을 만날 때까지 이동한다.게임판을 몇 번을 기울여야 빨간구슬을 구명(O)에 넣을 수 있는 지 횟수를 구하는 문제이다.단, 파란 구슬이 구멍에 들어가면 실패이고, 빨간구슬과 파란구슬이 동시에 구멍에 들어가도 실패이다.또한, 10회 이상 시도해도 실패이다.실패는 -1을 반환한다. 문제 접근어려운 문제였고, 이 문제는 BFS를 통해 최단 거리를 구하는 문제이다...
1. 문제https://www.acmicpc.net/problem/14502 2. 풀이 과정이 문제는 N x M 크기의 맵이 주어지고, 각 영역은 빈 칸(0), 벽(1), 바이러스(2)로 구분된다.바이러스는 벽을 통과 못한다. 벽 3개를 추가로 설치할 수 있으며, 이 때 안전 영역의 최대 개수를 구하는 문제이다. N, M의 최대크기는 8인데 제한시간이 2초로 비교적 여유롭다. 문제 접근1. 3개의 벽을 치는 모든 케이스를 모두 구한다.DFS, 백트래킹을 통해 3개의 벽을 치는 모든 케이스를 구한다.각 케이스 마다 BFS를 통해 감염처리를 하고 안전영역의 개수를 구해서 최대값을 갱신한다.static void dfs(int depth) { if (depth == 3) { // 3개의 벽을 ..
1. 문제https://www.acmicpc.net/problem/3190 2. 풀이 과정N x N이 BOARD가 주어졌을 때, 사과가 있는 영역(1)과 빈 영역(0)이 존재한다.뱀은 (0,0)에서 오른쪽 방향을 보면서 시작한다. 그리고 뱀은 주어진 시간마다 왼쪽(L) 또는 오른쪽(D)로 방향을 튼다.뱀은 자기가 바라보고 있는 방향으로 1초에 1칸 이동한다.사과가 있는 영역으로 이동: 사과를 먹고, 몸의 길이는 1만큼 늘어난다.빈 영역으로 이동: 몸의 길이는 늘어나지 않고 뱀이 이동만 한다.만약 이동할 영역이 벽이거나, 자신 몸이라면 종료된다.게임이 몇 초에 끝내는 지 계산하는 문제이다. 처음에는 DFS로 접근했었다.. DFS로 푸니깐 도저히 뱀이 길이가 늘어나는 성질이 구현이 안되서 다른 풀이 방법으로..
1. 문제https://www.acmicpc.net/problem/2178 2. 풀이 과정(1, 1)에서 시작해서 (N, M)에 도달하기 위한 최단거리를 구하는 문제이다.각 영역은 0 또는 1인데, 0으로 이동할 수 없다. 처음에는 이 문제를 DFS로 접근했었다. 하지만 시간초과가 발생하는 것이었다. DFS 접근 방법의 문제DFS는 모든 경로를 끝까지 탐색하면서, MIN 값을 갱신해야 한다.최단경로를 보장하지 않으므로 모든 경우의 수를 전부 확인해야 한다.그래서 시간초과가 발생하는 것이었다. 문제 접근이 문제는 BFS로 접근해야 효율적으로 풀 수 있다.BFS는 같은 깊이의 노드부터 순차적으로 탐색한다. 이동거리를 누적하면 결국 N, M에 도달하는 시점이 최단거리가 된다. 1. 큐에 시작점 (0, 0)을 ..
1. 문제https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 2. 풀이과정이분 탐색 문제인 걸 알면서 풀었는데도, 아이디어가 잘 떠오르지 않은 문제였다.이분 탐색 문제를 많이 풀어봐야겠다..! 사람수 n명이 주어지고, 입국심사관이 한 명을 심사하는데 걸리는 시간이 times 배열로 주어진다.모든 사람들이 입국심사를 가장 빨리 끝내는 시간을 구하는 문제이다. 문제접근이 문제는 최악의 경우 n = 1,000,000,000 이고, 각 심사관이 한명을 검사하는 시간이 1,000,000,000 이다.또한, 심사..
문제 풀이 과정서로 다른 양의 정수로 이루어진 수열이 주어질 때 a(i) + a(j) = x를 만족하는 [a(i), a(j)] 쌍의 수를 구하는 문제이다. 이중 반복문으로 구현하면 시간 초과가 발생한다.제한시간은 1초인데 n이 최대 100,000이므로 100,000² => 시간 초과 문제 접근투포인터를 이용해서 반복 횟수를 줄여서 연산 횟수를 줄인다. 배열을 오름차순 정렬한다.투포인터: start를 배열의 첫번째 인덱스, end를 마지막 인덱스로 초기화 한다.정렬된 형태를 가지므로 단조성을 가진다.a[start] + a[end] = x 만족한다면,카운트 증가,같은 원소를 재사용할 필요가 없다. => start는 +1, end는 -1a[start] + a[end] > x를 만족한다면합이 x보다 크므로 합을..
문제 풀이 과정이 문제는 N 길이의 리스트가 주어질 때 처음과 끝이 연결된 구조이다.즉, 원형 연결 리스트로 구현 해결할 수 있다. 문제 접근원형 연결 리스트 구성Node 클래스 정의num: 풍선 번호x: 이동 값next: 다음 노드prev: 이전 노드move(int step): step 만큼 이동하여 도착한 노드 반환step > 0(양수) : 다음 노드를 따라 이동step remove(): 현재 노드를 원형 리스트에서 제거static class Node { int num; int x; Node next; Node prev; public Node move(int x) { Node cur = this; if (x > 0) { ..
