백준
-
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이 되는 팀이 있는지 확인해보면 됩니다. ..
-
16713번 Generic Queries알고리즘 2023. 1. 21. 10:15
문제 설명 주어진 수열에서 XOR 연산을 하는 query를 여러 개 수행한 결과값들을 다시 XOR연산을 한 값을 구하는 문제입니다. 문제 풀이 선행 지식 XOR Python에서 XOR 연산은 "^"를 통해 이루어진다. XOR 연산의 결과 값 0 ^ 0 = 0 0 ^ 1 = 1 1 ^ 0 = 1 1 ^ 1 = 0 a1^a2^a3^a4 = A라고 할 경우 A^a1 = a2^a3^a4이다. 풀이 개념 이번 문제는 XOR의 개념을 생각하는 데에 오래 걸린 것 같습니다.. 수열의 길이 N과 쿼리의 개수가 모두 10^6로 큰 수 입니다. 그러므로 한 쿼리마다 XOR 연산을 하는 것은 비효율적이므로 누적합을 통해 이용해보도록 하겠습니다. 여기서 헷깔렸던 점은 수열의 홀수번째부터 시작하는 누적합과 짝수번째부터 시작하는..
-
1304번 지역알고리즘 2023. 1. 20. 18:27
문제 설명 이번 문제는 1~N의 도시에서 1->2, 2->3, i->i+1, N-1->N으로 가는 고속 도로가 있고 문제에서 일반 도로가 주어질 경우, 아래 조건을 만족하도록 지역을 나눌 경우 지역의 개수의 최대값을 구하는 문제입니다. 조건 지역 A의 어떤 도시에서 지역 B의 어떤 도시로 넘어갈 수 있는 경로가 있다면, B에 속해 있는 어떤 도시에서 A에 속해 있는 어떤 도시로 가는 경로는 없어야 합니다. 모든 지역의 도시 개수는 같아야 한다. 문제 풀이 아이디어 1 문제의 조건을 다시 생각해보기 위의 조건에 만족하도록 지역을 나눌 경우를 생각해보겠습니다. 모든 도시는 이미 자기보다 +1이 되는 도시로 향하는 도로가 하나씩 있다. 그렇다는 말은, 1에서 3으로 2에서 8로 X에서 Y(X E인 경우만 생각..
-
24453번 디버깅알고리즘 2023. 1. 20. 17:29
문제 설명 이 번 문제는 자동으로 생성된 코드에 오류가 반드시 존재할 때, 이 오류를 자동으로 고쳐주는 커맨드를 누르기 위해 필요한 전제 조건을 만족하여 커맨드를 누를경우 해결되는 오류의 개수를 최대로 하는 문제입니다. 전제 조건 작성된 코드에서 오류가 없는 연속된 X줄이 존재 사용자는 오류를 Y개 이상을 찾아 해결한 뒤에 커맨드를 누르고 싶다 문제 풀이 아이디어 이번 문제는 Y와 관련된 전제 조건을 마지막에 생각하는 것이 핵심인 것 같습니다. X에 관련된 조건과 문제의 답을 연관 시켜보면, 연속된 X줄에서 찾게되는 오류의 개수를 최소로 해야한다는 것을 알 수 있습니다. 그 이유는 이 개수가 최소여야지만, 에디터가 해결할 오류의 개수를 최대로 할 수 있기 때문입니다. 따라서, 연속된 X줄 중에서 나올 수..
-
14570번 나무 위의 구술알고리즘 2023. 1. 3. 15:25
문제 설명 이번 문제는 트리에 구술을 밑의 규칙대로 떨어뜨릴 경우, k번째 구술이 멈추게 될 노드의 위치를 찾는 문제입니다. 규칙 현재 구슬이 놓인 노드의 자식이 없다면 그 자리에서 멈춘다. 1을 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 한 개라면 해당 자식 노드로 떨어진다. 1, 2를 만족하지 않으며, 만일 현재 구슬이 놓인 노드의 자식 노드가 두 개라면, 현재 노드의 왼쪽 서브트리에 담긴 모든 구슬의 수 오 -> 왼 -> 오... 로 반복된다는 것을 알 수 있다. 즉, k가 홀수일 경우에는 왼쪽으로 짝수일 경우에는 오른쪽으로 구술이 떨어지게 된다. 노드의 레벨마다 k를 2로 나눈 몫으로 교체해야 되는데, 이 때 k가 홀수일 경우에는 추가적으로 1을 더해주어야 한다. 그 이유는 N이..
-
1980번 햄버거 사랑알고리즘 2023. 1. 3. 15:00
문제 설명 두 개의 햄버거를 먹는 속도와 총 시간이 주어진다. 어떤 햄버거도 먹고 있지 않을 경우 콜라를 마신다. 이럴 경우 콜라를 마시는 시간을 최소한으로 하고, 햄버거를 최대한 많이 먹을 경우의 햄버거 개수를 구하는 문제이다. 문제 풀이 이번 문제는 1부터 주어진 시간 t까지 for문을 돌면서, 콜라를 가장 적게 마신 시간 중에서 햄버거를 가장 많이 먹은 개수를 구할 수 있도록 했습니다. 1. 햄버거를 먹는 시간이 적은 시간을 기준으로 주어진 시간내에 최대 먹을 수 있는 개수를 range로 for문을 돌도록했습니다. 2. 해당 시간의 햄버거를 먹었을 때 다른 햄버거를 먹는 개수와 콜라를 마신 시간을 계산해줍니다. 콜라는 현재까지의 최소 콜라 시간과 비교해줍니다. 3. 현재까지의 최소 콜라 시간과 비교..