분류 전체보기
-
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개의 지지대만 ..
-
2705번 팰린드룸 파티션알고리즘 2023. 1. 24. 09:16
문제 설명 이번 문제는 1+2+1+7+1+2+1과 같이 읽을 때 재귀적으로 왼쪽 절반과 오른쪽 절반이 같은 재귀적인 팰린드룸 파티션의 개수를 출력하는 문제입니다. 7의 재귀적 팰린드룸 7 1+5+1 2+3+2 1+1+3+1+1 1+1+1+1+1+1+1+1 문제 풀이 아이디어 dp 양의 정수 N을 양의 정수의 합으로 나타낸다는 것에 초점을 맞춰보겠습니다. N을 임의의 수 a+b+a라는 숫자로 나타냈을 경우(N>=b>=0, N/2>=a>0) 이는 재귀적인 팰린드룸이 됩니다. 여기서, 양쪽 a를 또 재귀적인 팰린드룸으로 나타낸다면 이 또한 재귀적인 팰린드룸이 됩니다. 이와 같은 풀이는 피보나치 수열과 같이 이전의 결과값을 저장하고 현재 값을 계산할 경우 이전의 결과값을 사용하는 dynamic programmi..
-
12026번 BOJ 거리알고리즘 2023. 1. 23. 16:40
문제 설명 이번 문제는 B, O, J 중 한 문자로 이루어진 타일에서 아래 규칙대로 걸을 경우 필요한 에너지의 양의 최소값을 구하는 문제입니다. 보도블럭을 밟는 순서는 B, O, J, B, O, J ... 순서대로 걷게 된다. i에서 k 타일로 이동하는데 필요한 에너지는 (k-i)^2이다. 첫 번째 타일은 무조건 B이고, 마지막 타일에 무조건 도착해야 한다. (마지막 타일에 도착할 수 없을 경우 -1을 출력) 문제 풀이 아이디어 1. 우선 문제의 조건을 살펴봐야 합니다. 보도블럭의 개수가 1000개로 비교적 작은 개수이므로, N^2의 풀이법도 가능할 것으로 보입니다. 2. i번째 타일에서 i+1~N번째 타일로 넘어가는 경우를 생각할 때, 1~i번째 타일은 해당 타일까지 이동할 때 필요한 에너지의 최소값을..
-
2327번 말아톤알고리즘 2023. 1. 22. 09:24
문제 설명 이번 문제는 사람들의 키의 합이 H가 되도록하는 팀 중에서 가장 느린 사람이 가장 빠르게 되도록 팀을 선발하는 방법을 찾는 문제입니다. 팀의 학생들의 키 총합이 H만 된다면 구성원이 몇 명이든 상관 없습니다. 각 i번째 학생의 정보는 hi, si가 주어집니다.(hi = i 번째 학생의 키, si = i 번째 학생의 속도) 문제 풀이 아이디어 dynamic programming 현재 내가 살펴보고 있는 선수 i가 팀의 구성원이 될 경우를 살펴보도록 하겠습니다. 이 선수가 속한 팀의 다른 구성원들의 키의 합은 H-hi가 될 것입니다. 만약, 지금까지 살펴본 선수들로 구성할 수 있는 팀의 키의 총합이 될 수 있는 경우를 저장하고 있었다면, 키의 합이 H-hi이 되는 팀이 있는지 확인해보면 됩니다. ..