분류 전체보기
-
백준 3541번 상근타워알고리즘 2023. 2. 22. 14:56
문제 설명 엘리베이터의 개수가 m개인 매우 높은 타워에서 하나의 엘리베이터만 정해서 탈 때, n번의 버튼을 눌러서 갈 수 있는 가장 낮은 층을 구하는 문제입니다. 문제 풀이 아이디어 엘리베이터가 움직일 수 있는 층 상근 타워는 0층부터 매우 높은 층까지, 지상에만 존재하기 때문에 지하로는 내려갈 수 없다. 그러므로 우선 엘리베이터를 위로 올린다음에 아래로 내려서 최대한 낮은 층에 머물 수 있도록 해줘야합니다. 낮은 층을 찾는 방법 엘리베이터를 타고 가장 낮은 층에 도착하는 경우의 수는 다시 로비로 되돌아올 경우입니다. 엘리베이터가 다시 로비로 도착할 수 있는 방법은 엘리베이터를 타고 올라간 층수와 내려올 수 있는 층수가 같을 경우입니다. -> 최소 공배수 풀이 반복 찾기 버튼을 누를 때마다 낮은 층수를 ..
-
백준 15686번 치킨 배달알고리즘 2023. 2. 21. 22:33
문제 설명 이번 문제는 좌표에 치킨 집과 가정 집이 있고 남길 치킨 집의 개수가 주어졌을 경우, 가정 집과 가장 가까운 치킨 집 사이의 거리를 치킨 거리라고 할 경우, 모든 가정 집의 치킨 거리의 합의 최소값을 구하는 문제입니다. 문제 풀이 아이디어 치킨 거리의 합의 최소값 구하는 방법 이번 문제는 각 가정집에서 치킨 집까지의 거리를 모두 구해야지만 최소값을 구할 수 있습니다. 그리고 남길 M개의 치킨 집 조합에 따라 각 가정집의 치킨 거리는 달라집니다. 그러므로 이번 문제는 모든 경우의 수를 다 살펴봐야지만 정답을 구할 수 있습니다. -> 브루트포스 알고리즘 풀이 풀이 1. 각 치킨 집 중 m개의 조합을 구해서 각 조합의 치킨 거리를 구한 다음 비교하여 최소값을 구해냅니다. ->필자는 위의 방법을 사용..
-
백준 2487번 섞기 수열알고리즘 2023. 2. 20. 11:34
문제 설명 이번 문제는 처음에 [A1,A2,A3, ... ,An]의 카드가 순서대로 있을 때, 주어진 수열대로 섞을 경우 처음 상태로 돌아오는 최소 섞기 횟수를 구하는 문제입니다. 문제 풀이 아이디어 각 자리가 움직이는 규칙 [A1, A2, A3, ... An] 카드를 문제에서 제시한 예시 수열 [A3, A2, A5, A6, A1, A4] 대로 섞는 경우 각 자리의 움직임을 살펴보도록 하겠습니다. A1은 첫 섞기에서 A3으로 이동하고 두 번째 섞기에서 A5, 세 번째 섞기에서 A1으로 되돌아옵니다. 그러므로 A1의 섞기 수열의 궤적은 3입니다. A2는 첫 섞기에서 A2로 이동합니다. 그러므로 A2의 섞기 수열의 궤적은 1입니다. A3는 A1섞기 수열의 궤적 내에 포함되어 있으므로 섞기 수열의 궤적은 3입..
-
10589번 마법의 체스판알고리즘 2023. 2. 18. 11:09
문제 설명 이번 문제는 크기가 n * m인 마법의 체스판에서 직사각형을 선택해서 검은색은 흰색으로 흰색은 검은색을 바꿀 수 있을 때, 모든 칸의 색상을 같게 만들 수 있는 직사각형의 좌표를 출력하는 문제입니다. 문제 풀이 아이디어 체스판의 길이가 짝수일 때와 홀수일 때의 규칙을 찾아보겠습니다. 모든 칸을 채울 색 정하기 우선 짝수이든 홀수이든, 가장 왼쪽의 가장 윗칸의 색이 다른 색보다 많거나 같다는 것을 알 수 있습니다. 그러므로, 모든 칸을 가장 왼쪽 윗 칸의 색(이하 A색으로 부르겠습니다.)으로 바꾸도록 하겠습니다. 대칭 이루기 경우 2번 홀수 * 홀수 인 체스판을 보도록 하겠습니다. 홀수 * 홀수인 체스판은 좌우상하로 대칭을 이루고 있습니다. 이럴 경우, 모든 색을 A로 바꾸는 회수를 살펴보도록 ..
-
18352번 특정 거리의 도시 찾기알고리즘 2023. 2. 17. 13:30
문제 설명 이번 문제는 어떤 나라에서 단 방향 도로만 존재할 경우 주어진 도시 X에서 최단 거리 K만큼 떨어진 도시를 출력하는 문제입니다. 문제 풀이 아이디어 bfs 이번 문제는 한 노드에서 다른 노드로 가는 최단 거리를 구하는 문제이므로 bfs를 생각해낼 수 있습니다. 풀이 bfs 구현 (queue사용) queue를 통해 bfs를 구현해보도록 하겠습니다. queue의 원소는 도시 번호와 현재 이동 거리를 원소로 하는 배열이 됩니다. visited라는 배열을 둬서, 해당 도시를 방문했다면 visited[해당 도시]=True로 바꿔서 해당 도시를 최단거리로 방문했음을 알 수 있도록 해줍니다. 각 도시에 방문했을 경우, 해당 도시에서 단 방향 도로를 통해 갈 수 있는 도시 중 방문하지 않은 도시를 queue..
-
26646번 알프스 케이블카알고리즘 2023. 2. 16. 10:59
문제 설명 이번 문제는 여러 산맥의 정상을 다른 산의 정상으로 잇는 와이어를 설치해서 이동할 경우, 노선의 설치 비용을 최소화하는 경우를 구하는 문제입니다. 와이어의 설치 비용 - 와이어 길이의 제곱 노선의 설치 비용 - 와이어의 설치 비용의 합 문제 풀이 아이디어 와이어 설치 비용의 최소값 위의 사진 예시를 보도록 하겠습니다. A-B-C를 잇는 경우와 A-C를 잇는 경우의 설치 비용을 비교해보면, A-B-C를 잇는 경우의 설치 비용은 66 A-C를 잇는 경우의 설치 비용은 122가 됩니다. 위에서 확인할 수 있듯이, 산 정상을 하나라도 건너 뛰어서 와이어를 잇게 된다면 설치 비용이 커짐을 알 수 있습니다. (모든 산은 직각 이등변 삼각형이므로 어떤 예시를 들게 되더라도, 정상 하나를 건너 뛰어서 와이어..
-
11501번 주식알고리즘 2023. 2. 15. 12:05
문제 설명 홍준이가 미래의 주식 가격 변동에 대한 정보를 알고 있고, 매일 아래 3가지 행동 중 한 개의 행동만 할 경우, 벌 수 있는 최대 이익을 구하는 문제입니다. 주식 하나를 산다 원하는 만큼 가지고 있는 주식을 판다 아무것도 안한다 문제 풀이 아이디어 주식을 사는 타이밍 홍준이가 주식 가격 정보를 알고 있으므로, 주식이 오를 때까지는 계속 사고 최고점일 경우에 모두 팔아버리면 최고 이익이 나게 됩니다. 최고점 이후 최고점이 지나고 난 뒤에도 고점이 있을 수 있습니다. 그러므로 최고점 이후 날짜들에 대한 주식 최고값을 다시 구해주고, 그 날짜가 되기 전까지 주식을 모두 사면 이익을 가질 수 있게 됩니다. 풀이 최고점 찾기의 반복 우선 첫 날부터 마지막 날까지, 최고점이 되는 날을 찾고 첫 날부터 최..
-
10476번 좁은 미술관알고리즘 2023. 2. 13. 11:37
문제 설명 이번 문제는 가로로 두칸 세로로 N칸이 있는 미술관에서 각 방마다 가치가 정해져 있을 때, 아래 규칙대로 K개의 방을 닫아서 공개된 방의 가치의 합을 최대로 하는 경우를 구하는 문제입니다. 한쪽 끝의 두 방중 적어도 한 방에는 방문할 수 있어야 하고 다른 쪽 끝의 두 방중 한 방으로 나갈 수 있어야 한다. 즉, 같은 줄의 두 방을 모두 닫거나 대각선으로 붙어있는 두 방을 닫아서는 안 된다. 문제 풀이 아이디어 한 줄을 닫을 수 있는 방법의 수 한 줄에 있는 두 방을 모두 동시에 닫을 수 없으므로, 한 줄을 닫는 방법은 아래와 같습니다. 왼쪽만 닫는다 오른쪽만 닫는다 모두 열어 둔다 위와 같이 3가지 경우만 있습니다. 최대값을 구하는 방법 위에서부터 닫을 방을 정할 때, 현재 위치에서 각 방법에..