오랜만에 다익스트라 푸니까 원리 다 까먹어버림 1. 출처 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 1~N까지 가는 최단 경로의 거리를 구하는 문제 최단 경로를 구하는 과정에서 필수 2가지 노드를 꼭 거쳐야함 2. 설계 2-1) 다익스트라의 원리 다익스트라 알고리즘은 출발지에서 연결된 모든 도착지에 대해 최단 거리를 계산한다. (연결되지 않으면 계산하지 않음) 때문에 출발지 지정이 중요하다. [다익스트라 기본 코드] public static int Dijkst..
미로를 따라 움직이는 것이 아닌 움직인 발자취를 보고 미로를 그려내는 문제 처음에는 어떻게 풀지?... 많은 고민을 했다가 아이디어를 생각해내고 '아!' 하게 했던 문제! 뿌듯해서 기록해본다. 야심한 새벽에 이 무슨 코딩 체조람 1. 출처 1347번: 미로 만들기 홍준이는 미로 안의 한 칸에 남쪽을 보며 서있다. 미로는 직사각형 격자모양이고, 각 칸은 이동할 수 있거나, 벽을 포함하고 있다. 모든 행과 열에는 적어도 하나의 이동할 수 있는 칸이 있다. 홍 www.acmicpc.net 특정 크기의 지도에서 유저가 움직인 발자취가 주어진다. (직진, 왼쪽 회전, 오른쪽 회전) 발자취를 보고 지도를 다시 그려내는 문제 #은 벽, . 은 이동 가능 위치 내가 어느 위치에서 시작하는지도 주어지지 않는다는 것이 포..
오늘은 23.11.23에 풀었던 알고리즘 스터디의 첫 번째 문제! 지연이가 요청했던 그 문제!!! 감시피하기 문제를 다시 보고 리뷰하는 시간을 갖도록 하겠다. 다시 보니까 꽤 난이도 있는 문제여~ 1. 출처 https://www.acmicpc.net/problem/18428 18428번: 감시 피하기 NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복 www.acmicpc.net N*N 복도에 학생과 선생님의 위치가 주어짐 3개의 장애물을 설치해서 학생들을 선생님 감시 하에서 피하게 해야함 선생님은 자신의 4방을 거리 제한없이 감시할 수 있음 단, 선생님은 장..
수학적인 공식이 아닌 논리 공식을 이끄는 dp는 어렵다 ㅎㅎ 오늘의 오답노트는 바로 기타리스트~ 1. 출처 https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 공연의 새로운 파트가 시작되기 전 볼륨을 바꿀 수 있음 파트의 수, 가장 먼저 실행되는 볼륨, 올릴 수 있는 최대 볼륨 3가지가 주어짐 볼륨은 0에서 최대 볼륨 사이로 실행시킬 수 있음 이 때, 가장 마지막 파트에서 틀 수 있는 가장 큰 볼륨을 구하는 문..
내 수준은 딱 골드 5인 것 같아서 요즘은 알고리즘 스터디 문제 중 실버 ~ 골드5 문제를 열심히 풀고 있다. 오늘은 맞춘 문제이지만, 내가 취약해하는 요소 DP + Math 2개가 모두 섞여있어서 복습을 해보고자 한다. 1. 출처 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 모든 자연수는 최대 4개의 제곱수의 합로 나타낼 수 있음 26 = 5^2 + 1^2 혹은 4^2 + 3^2 + 1^2 이런식 최소 ..
오랜만에 시간초로 낚인 문제가 있었으니... 바로 동물원... 2초라는 시간대가 여유롭다고 착각하고, PowerSet으로 돌렸다가 N=100000이 시간초과로 안돌아가는 상황을 목격했다. 충격~ 15초 내로 N=21까지만 돌아간다 ㅋㅋ 그래서 아... 이거 DP였구나를 깨달아버렸다. 1. 출처 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net N이 주어진다. N은 행이다. 열은 2로 고정이다 (N,2) 행렬에서 사자를 우리에 넣을 수 있는 경우의 수를 구하는 것 한 사자를 넣을 때 근접한 가로, 세로에 사자가 들어있으면 그 위치에 사자를 넣을 수 없음 (4방 탐색) 2. 설계 그래서 DP면 공식이 뭐지?... 이중그래프를 그려놓고, 한칸 한칸 ..
DFS와 DP의 조합은 어렵다 ㅠ 다시 공부해야짓! 1. 출처 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 지도 상에 건물의 높이가 주어짐 높이가 현재 건물보다 낮은 곳만 이동할 수 있음 내리막길로만 가고 싶음 (우, 하, 좌) 갈 수 있는 경로는 몇 개인지 계산하는 문제 2. 설계 처음엔 BFS로 좌, 하, 우 방향 탐색해서 갈 수 있는 경로가 몇 개인지 계산하고자 하였다. 그런데 16%만에 메모리 초과가 났다. 가로x세로 = 500x500이기..
원래는 못 푼 문제가 아니여서 작성을 아니하려다... 푼 사람도 별로 없고, 후기도 별로 없길래 써본다. 원래 빈틈 시장 노리는 것 아니겠어? ㅎㅎ Collection 구현에 관심이 있다면 풀어보는 것도 낫밷이다! 1. 출처 3961번: 터치스크린 키보드 첫째 줄에 테스트 케이스의 개수 t (0 < t < 20)가 주어진다. 각 테스트 케이스의 첫째 줄에는 사용자가 입력한 단어와 프로그램이 가지고 있는 단어의 개수 l이 주어진다. (0 < l ≤ 10) 다음 l개의 줄 www.acmicpc.net 내가 딱 100번째이다 ㅎㅎ 의미부여중 ㅎㅎ... 사용자가 어떤 단어를 입력한다. 컴퓨터에는 예비 단어 N가지가 있다. 사용자의 단어와 컴퓨터의 예비 단어 사이 거리를 구한다. 거리는 단어에 속해있는 각 캐릭터..
