본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 16939번 2×2×2 큐브 https://www.acmicpc.net/problem/16939 16939번: 2×2×2 큐브 첫째 줄에 2×2×2 루빅스 큐브 각 면의 각 칸 색상이 주어진다. 색상은 1부터 6까지의 자연수로 나타내며, 각 자연수는 총 4번 등장한다. i번째 수가 의미하는 칸은 아래와 같다. www.acmicpc.net 22/11/10 전형적인 구현 문제로, 큐브의 움직임을 따라가며 차근차근 구현하면 맞을 수 있는 문제이다. 문제 접근 방식: 아래 그림을 보자. 2*2*2 큐브에서 나올 수 있는 모든 회전들을 기호로 표현한 것으로, 총 12가지가 있다. 나는 5678이 새겨진 면을 맨 윗면으로 고정시켜놓고, 저렇게 한 번 회전시키는 것을 각각의 함수로 구현하였다. 다시 말해, 총 12가지의 함수를 구현한 것이다. ..
[Python] 11973번 Angry Cows (Silver) https://www.acmicpc.net/problem/11973 11973번: Angry Cows (Silver) The first line of input contains \(N\) (\(1 \leq N \leq 50,000\)) and \(K\) (\(1 \leq K \leq 10\)). The remaining \(N\) lines all contain integers \(x_1 \ldots x_N\) (each in the range \(0 \ldots 1,000,000,000\)). www.acmicpc.net 22/11/05 전형적인 이분 탐색 문제로, 외국어 문제여서 문제를 해석하는 것이 어려운 문제이다. 문제 접근 방식: 먼저 외국어 문제이기에 문제 요약을 하자면 다음과 같다. 건초더미..
[Python] 7869번 두 원 https://www.acmicpc.net/problem/7869 7869번: 두 원 첫째 줄에 두 원의 중심과 반지름 x1, y1, r1, x2, y2, r2가 주어진다. 실수는 최대 소수점 둘째자리까지 주어진다. www.acmicpc.net 22/11/09 전형적인 수학, 기하학 문제로, 제2코사인 법칙을 사용하여 문제를 해결할 수 있다. 문제 접근 방식: 이 문제를 풀기 위해서는 먼저 제2코사인 법칙을 알아야 한다. 제2코사인 법칙이란, 어떤 삼각형의 세 변과 그 대각 사이에 성립되는 관계로, 위와 같은 식을 따른다. 따라서, 내가 예를 들어, 각 B를 구하고 싶으면 저 식 중 2번째 식을 변형하여 아래와 같이 구할 수 있다. 이 식을 이용할 것이다. 먼저, 원의 위치 관계에 따라 3가지 경우로 나..
[Python] 25921번 건너 아는 사이 https://www.acmicpc.net/problem/25921 25921번: 건너 아는 사이 첫째 줄에 비용의 최솟값을 출력한다. www.acmicpc.net 22/11/06 대회 도중에는 거의 접근을 가까이했지만 풀지 못했으나, 이후 살짝 고쳐서 맞았습니다를 받은 문제이다. 그래프 문제처럼 보이는 소수 판정 문제로, 참 기발하다고 생각했다. 문제 접근 방식: 음식의 가격의 합을 작게 하려면 최대한 음식을 먹는 횟수가 적어야 할 것이다. 다시 말해, 밥을 먹는 사람들의 번호를 노드, 서로 밥을 먹는 사람들끼리 잇는 것을 간선이라고 한다면, 우리는 이 간선의 개수를 최소한으로 만들어야 한다. 쉽게 이야기하자면 서로 만나서 밥 먹는 횟수가 적어야 된다. 따라서, 이 그래프에서는 사이클이 없어야 된다. ..
[Python] 25916번 싫은데요 https://www.acmicpc.net/problem/25916 25916번: 싫은데요 $6$번째 구멍부터 $8$번째 구멍까지 막으면 총 $9$의 부피를 소모하고, 최대값인 $9$를 출력한다 www.acmicpc.net 22/11/06 전형적인 투 포인터 문제로, 대회 도중에 쉽게 풀 수 있었다. 문제 접근 방식: 햄스터의 머리를 end포인터라고 하고, 햄스터의 꼬리를 start포인터라고 하자. 햄스터의 몸을 한 칸씩 늘리는 것은 end포인터를 뒤로 한 칸씩 당기는 것과 같다. 그러면, 생각을 한번 해보자. 우리는 햄스터가 몸을 늘릴 수 있을 만큼 최대한 늘리고 싶다는 사실을 아주 잘 안다. 그 말인즉슨, 한 칸을 만약에 늘릴 수 있을 때(몸을 늘릴 수 있는 공간이 있을 때) 햄스터가 괜찮다면(햄스터..
[Python] 25915번 연세여 사랑한다 https://www.acmicpc.net/problem/25915 25915번: 연세여 사랑한다 훈규가 비밀번호를 모두 입력하기 위한 이동 거리의 최솟값을 출력한다. www.acmicpc.net 22/11/06 단순한 구현 문제로, 예제를 잘 보면 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 훈규가 비밀번호를 출력하기 위한 이동거리의 최솟값을 출력해야 한다. 근데 어차피 순서대로 입력해야 하므로, I에서 L로, L에서 O로, O에서 V로, V에서 E로... 그렇게 가는 이동거리는 고정되어있다. 때문에 처음 위치에만 관련이 있다. 예제에서는 처음 위치가 I일 때, 다시 말해 처음에 움직이지 않고 바로 출력해도 될 때의 경우의 이동거리를 줬으므로(84), 이를 이용해서, 입력받은 알파벳이 I에서 얼마..
[Python] 25918번 북극곰은 괄호를 찢어 https://www.acmicpc.net/problem/25918 25918번: 북극곰은 괄호를 찢어 극지 연구소에서 연구 중인 협이는 새로운 북극곰의 특성을 발견했다. 그것은 바로 북극곰이 $O$와 $X$를 보면 $()$와 $)($로 찢어버린다는 것이다. 협이는 이러한 북극곰의 특성을 이용하여 길이 $N www.acmicpc.net 22/11/07 에디토리얼에서는 그리디 문제라고 나와있었으나, 조금 스택을 곁들인 애드 혹 스러운 문제로, 쉬운 방법으로 구현할 수 있는 문제이다. 문제 접근 방식: 카운터 변수를 하나 선언을 해주고 괄호 문자열에서 (가 나오면 그 변수에 1을 더하고 )가 나오면 1을 뺐다. 북극곰은 항상 () 또는 )(처럼 열린 괄호와 닫힌 괄호를 쌍으로 생성하기 때문에, 북극곰이 생성..
[Python] 1737번 Pibonacci https://www.acmicpc.net/problem/1737 1737번: Pibonacci 첫째 줄에 P[n]을 출력한다. 값이 매우 커질 수 있으므로 1,000,000,000,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 22/11/08 신박한 2차원 DP문제로, 처음에는 재귀를 이용한 탑다운 방식으로 접근했었으나, 재귀 시간이 너무 오래 걸려 바텀업 방식으로 전환하여 풀 수 있었던 문제다. 문제 접근 방식: 이 문제를 보면, 기존 피보나치수열의 점화식과는 다르게 아래와 같은 점화식을 가지고 있다. 맨 처음 생각한 풀이는 위의 점화식을 재귀로 구현하고, DP테이블은 딕셔너리로 구현함으로써 하려고 했다. 딕셔너리의 키는 실수 연산을 통해서 구현하려고 했다. 근데, 이..

티스토리툴바