알고리즘
-
5002번 도어맨알고리즘 2023. 2. 8. 10:15
문제 설명 이번 문제는 클럽의 출입구에서 남녀 수의 차이를 맞춰주는 도어맨이 있고 도어맨이 기억할 수 있는 수 차이의 최대값이 주어졌을 때, 이 도어맨이 아래 규칙을 지키면서 사람들을 들여보낼 수 있는 최대 수를 구하는 문제입니다. 줄의 맨 앞에 줄 서 있는 사람을 들여보내야 되는 것은 아니다. 남녀 수의 차이를 고려해 두 번째 사람을 들여보내도 된다. 문제 풀이 아이디어 탐색 이번 문제는 주어진 순서를 모두 파악해야 하므로 모두 탐색해봐야 한다. 비교는 절대값으로 앞에서부터 사람을 들여보낼 때, 도어맨이 기억할 수 있는 수 차이의 최대값을 넘기지 않는 선에서 앞 사람이나 두 번째 사람을 들여보내야 합니다. 여기서, 남자를 1, 여자를 -1이라 하면 첫 번째 사람이나 두 번째 사람을 들여보냈을 경우 현재..
-
17615번 볼 모으기알고리즘 2023. 2. 6. 10:04
문제 설명 이번 문제는 빨강색, 파랑색 볼이 주어졌을 때, 다음과 같은 규칙으로 볼을 이동시켜서 같은 색의 볼들이 모여있도록 할 때의 최소 이동횟수를 구하는 문제입니다. 바로 옆에 다른 색의 볼이 있으면 그 볼들을 모두 뛰어넘을 수 있다. 옮길 수 있는 볼의 색은 한 가지이다. 처음에 빨간 볼을 움직였다면 다음에는 파란 볼을 움직여야 한다. 문제 풀이 아이디어 공을 최소 횟수로 움직일 수 있는 순서 공들을 움직일 경우 바로 옆의 다른 색의 볼은 모두 뛰어넘을 수 있다는 규칙이 있다. 이것을 만족하되, 공을 모으는 최소 이동횟수를 구하는 움직이는 순서는 가장 자리 쪽의 공을 먼저 움직이는 것이다. 그림 1에서 파란 색 공을 움직이는 상황을 살펴보겠습니다. 만약, 4번 공을 먼저 움직인다면 6번 앞에 5번에..
-
18352번 특정 거리의 도시 찾기알고리즘 2023. 2. 5. 11:24
문제 설명 이번 문제는 각 도시마다 다른 도시로 갈 수 있는 단 방향 도로가 존재할 경우, 주어진 도시 X에서 최단 거리 K로 갈 수 있는 도시를 출력하는 문제입니다. 문제 풀이 아이디어 bfs 최단거리로 갈 수 있다는 말을 보자마자 bfs를 떠올렸습니다. 풀이 변수 단방향 도로에 대한 정보를 저장할 roads dict를 선언했습니다. bfs를 이용한 풀이를 위해 우선 queue 배열을 선언했습니다. 그리고 원소는 [0, X]와 같은 형식으로 두었습니다. (0 => 현재 이동한 횟수, X => 현재 도시 ) 그리고 해당 도시를 방문했음을 알려주는 boolean 타입의 visited 배열을 선언해주었습니다. (visited의 원소는 False로 채워줍니다.) 결과값을 저장할 result 배열도 선언해주었습..
-
27172번 수 나누기 게임알고리즘 2023. 2. 4. 14:50
문제 설명 이번 문제는 아래의 규칙으로 카드 게임을 실시하고 각 플레이어가 얻은 점수를 출력하는 문제입니다. 각 사람이 카드를 한 개씩 받게 됩니다. (카드는 1~1,000,000 사이의 수) 카드 게임은 두 명이서 진행됩니다. 각 사람이 자신의 카드를 냈을 때 자신의 수로 다른 사람의 수를 나눴을 때 나머지가 0이면 승, 자신의 수가 다른 사람의 수에 적힌 수로 나누어 떨어지면 패, 둘 다 아니라면 무승부 승리한 플레이어는 1점을 얻고 패배한 플레이어는 1점을 잃습니다. 무승부인 경우 점수의 변화가 없습니다. 본인을 제외한 모든 플레이와 정확히 한 번씩만 게임을 실시합니다. 문제 풀이 아이디어 시간 복잡도 플레이어의 수가 100,000이므로, 모든 플레이어들의 모든 플레이를 for문으로 반복하면서 결과..
-
2022번 사다리알고리즘 2023. 1. 30. 09:21
문제 설명 이번 문제는 길이가 x, y인 사다리가 있고 두 빌딩에 기대져 있을 때, 두 사다리가 땅에서부터 정확하게 c인 지점에서 서로 교차한다면 두 빌딩은 얼마나 떨어져 있는지 찾는 문제입니다. 문제 풀이 아이디어 x,y 식 구하기 x가 빌딩과 닿아있는 지점부터 바닥까지의 길이를 b, y가 빌딩과 닿아있는 지점부터 바닥까지의 길이를 d 빌딩이 떨어져 있는 거리를 a라고 할 때 x,y,a,b,c를 이용해 문제에서 주어진 조건으로 식을 만들어 보겠습니다. 피타고라스의 정리를 이용해 x^2 = b^2+a^2 y^2 = d^2+a^2 식을 구할 수 있습니다. 또한 닮음을 이용한 식을 구할 수 있습니다. x빌딩의 바닥 부분을 0,0이라고 한다면 y사다리는 y=(d/a)x 그래프가 되므로 x빌딩으로부터 두 사다..
-
24092번 알고리즘 수업 - 퀵 정렬 3알고리즘 2023. 1. 29. 17:11
문제 설명 이번 문제는 두 수열 A, B가 주어졌을 경우 A 수열이 퀵 정렬로 정렬되는 과정에서 생길 수 있는 수열 중 B와 동일한 수열이 있는지 확인하는 문제입니다. 문제 풀이 의사 코드 설명 이번 문제는 퀵정렬에 대한 의사코드가 주어져 있으므로, 코드 그대로 퀵 정렬을 구현해보면 됩니다. quick_sort(A[p..r]) { # A[p..r]을 오름차순 정렬한다. if (p 2 5 1 4 3(i=1, j=2) -> 2 5 1 4 3(i=1, j=3, A[2]와 A[3]이 교환됨) -> 2 1 5 4 3(i=2, j=4) -> 2 1 5 4 3(i=2, j=5,..
-
21738번 얼음깨기 펭귄알고리즘 2023. 1. 25. 10:14
문제 설명 이번 문제는 얼음깨기 게임의 업그레이드 버전을 플레이하면서 펭귄을 떨어뜨리지 않고 가장 많은 얼음을 깰 수 있는 방법을 찾는 문제입니다. 얼음깨기 게임의 업그레이드버전에 추가된 규칙은 다음과 같습니다. 얼음의 종류는 지지대의 역할을 하는 얼음과 일반 얼음 두 가지가 있다. 일반 얼음들은 지지대가 연결되어 있어야만 깨지지 않고 있는다. 펭귄이 올라가 있는 일반 얼음은 두 개의 지지대가 연결되어 있어야지만 깨지지 않는다. 연결된다는 의미는 지지대로부터 서로 다른 일반 얼음들을 통해 연결 관계가 이어져 있는 것을 이야기 한다. 서로 다른 지지대가 펭귄이 올라가 있는 얼음을 거치지 않고 연결되는 경우는 없다. 지지대도 깨지는 얼음입니다. 문제 풀이 아이디어 1. 펭귄을 거치지 않으면 1개의 지지대만 ..