https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만-포드 알고리즘을 사용하는 문제이다. 그래프에서 음의 가중치가 등장한다면, 다익스트라로 해결할 수 없으므로 벨만-포드 알고리즘을 적용하자. 벨만 포드 알고리즘이란? 그래프의 최소비용을 구하는 알고리즘 중 하나로, "모든 경우의 수를 전부 탐색하여 최소비용을 찾는다." 자세히 말하자면, N개의 정점이 존재할 때 N-1번 탐색해야한..
https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 우선 이 문제는 RGB거리1의 확장판이다. 직전에 고른 색만 고를 수 없는 것이 아니라, 1번째 집과 N번째 집의 색도 달라야 하므로 원형문제라고 볼 수 있다! 우선, RGB색으로 칠하는 비용을 2차원 배열에 모조리 저장한다. for문을 3번 돌려서 1번 집이 R, G, B 색을 차례로 하나씩 선택하는 경우의 최솟값을 계산한다. 1번 집이 만약 Red를 골랐다면, ..
https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 기본적인 bfs문제에 약간의 테크닉을 요구하는 문제이다. 우선 C가 두개 주어지므로 그냥 먼저 나오는 C를 시작점이라고 치고, 늦게 나오는 C를 도착점이라 친다. 그리고 시작점을 큐에 넣고 bfs를 시작하는데, 큐의 맨 앞에 것을 가져와서 4가지 방향을 탐색하는 건 기존 bfs와 동일하다. 그러나 여기서 레이저의 특징을 이용해야한다! 레이저는 한 방향으로만 직진하므로, while문을 통해..
https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 매번 입력마다 정렬해서 가운데 값을 출력하면 시간초과가 난다ㅜㅜ 0.1초안에 해결해야하는데, 최대 입력이 100,000이므로 O(N^2)으로는 해결할 수 없다는 뜻이다. 이 문제는 2개의 우선순위 큐를 활용하면 되는데, 활용조건은 다음과 같다. 1. 최소 힙의 값들은 모두 최대 힙보다 커야한다. 2. 최대 힙의 크기가 최소 힙의 크기보다 1보다 크거나 같도록 유지한다. 3. 최..
https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 얼핏보면 그냥 행렬 곱을 반복해주면 되는거 아닌가? 싶을 수도 있다. 하지만! 최대 천억제곱까지 주어지므로 O(N)에는 해결할 수 없다! 때문에 빠른 거듭제곱 알고리즘을 사용해야한다. 즉, N이 홀수일 땐 밑을 하나 꺼내서 N을 짝수로 만든다. N이 짝수일 땐 밑을 제곱하고 N을 2로 나눈다. 그럼 어떻게 이 문제를 풀어야할까? 우선 행렬곱을 해주는 함수를 하나 만든다. 배열을 파라미터로 넘길 땐 주소가 넘..
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 맨날 다익스트라나 bfs만 연습하다가 오랜만에 풀어본 dfs문제이다. dfs를 익히기에 아주 좋은 문제라고 생각되어 포스팅해본다! 크게 어렵지도 않아서 dfs에 능숙하지 않은 나같은 사람도 잘(?) 풀 수 있으리라 생각한다. 풀이 1. 우선, R x C 모양의 보드를 입력받아준다. 2. 그리고 0,0 위치(=시작 위치)도 말이 갈 수 있는 칸 중 하나로 친다고 하였으므로 해당 위치의 알파벳..
