본문 바로가기

글

 (385)
[Python] 23630번 가장 긴 부분 수열 구하기 https://www.acmicpc.net/problem/23630 23630번: 가장 긴 부분 수열 구하기 $N$개의 자연수로 이루어진 수열 $A = \{A_1, A_2, …, A_N\}$가 주어진다. 다음의 조건을 모두 만족하는 $A$의 부분 수열 $\{A_{i_1}, A_{i_2}, ..., A_{i_m}\}$ 중 가장 긴 수열의 길이를 출력하라. $A_{i_1} ~\&~ A_{i www.acmicpc.net 24/01/04 비트마스킹의 아이디어를 사용하는 애드 혹 문제이다. 문제 접근 방식: 처음에 아주 나이브하게 접근해서 틀렸습니다를 받았다. 이 접근 방식은, 모든 배열의 값을 AND연산했을 때 0이 나온다면 (배열의 길이)-1이 답이 된다는 접근이었다. 생각해 보니 정말 틀린 접근 방식이었고,..
[Python] 14502번 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 24/01/06 BFS와 브루트포스 연습 문제로, 구현하는 중간에 조금 꼬여서 살짝 해멨던 문제이다. 문제 접근 방식: 문제 자체는 단순하다. 벽을 $3$개 세워야만 하고, 그렇게 벽을 세운 뒤에는 BFS를 돌리면 된다. 즉, $64\times 64\times 64 \approx 260,000$번 정도의 BFS를 수행하면 된다. BFS를 진행할 때에는 바이러스가 있는 부분을 큐에 넣고 BFS를 진행하면 된다...
[Python] 1708번 볼록 껍질 https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 모든 점의 좌표는 다르다. x좌표와 y좌표의 범 www.acmicpc.net 23/10/02 기하 알고리즘 중 대표적인 알고리즘, 볼록 껍질 알고리즘을 연습할 수 있는 좋은 문제이다. 이 문제를 통해 볼록 껍질을 구현하는 템플릿 코드를 구성하면 좋을 것이다. 문제 접근 방식: 일반적으로 볼록 껍질을 구현하는 데에는 두 가지 방법이 존재한다. 이 문제의 해설에서는 두 가지 방법 모두 소개할 것이다. 첫번째 방법은 그라함 스캔이다. 그라함 스캔의 원리는 간..
[Python] 중간에서 만나기(MITM) 문제 모음 관련 글이 모아지면 계속 업데이트를 하도록 하겠습니다. 2024.01.02 - [알고리즘/백준 문제 풀이] - [Python] 7453번 합이 0인 네 정수 [Python] 7453번 합이 0인 네 정수 https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들 lighter.tistory.com 2024.01.04 - [알고리즘/백준 문제 풀이] - [Python] 9007번 카누 선수 [Python] 9007번 카누 선수 https://www.acmicpc.net/problem/9007 9007번: ..
[Python] 17953번 디저트 https://www.acmicpc.net/problem/17953 17953번: 디저트 창호는 매일 점심마다 디저트를 먹는다. 그런데 같은 디저트라도 매일 느끼는 맛이 달라진다. 어떤 날에는 마카롱을 먹고 매우 행복함을 느끼는 반면 어떤 날에는 ‘차라리 케이크를 먹는게 나 www.acmicpc.net 23/09/26 무난한 2차원 DP문제로, DP 테이블의 의미를 생각하면 쉽게 점화식을 세울 수 있다. 문제 접근 방식: 문제를 보면 전날에 먹었던 디저트와 같은 디저트를 먹으면 그 날에 얻을 수 있는 만족감보다 절반의 만족감만을 얻을 수 있다고 했다. 특정한 날에 디저트를 먹을 수 있는 선택지가 최대 $M = 10$까지의 제한이 있으므로, 즉, 최대 10개의 디저트가 선택지로 놓여있으므로, 이를 브루트포..
[Python] 17370번 육각형 우리 속의 개미 https://www.acmicpc.net/problem/17370 17370번: 육각형 우리 속의 개미 무한히 많은 정육각형이 서로 맞닿아 놓인 형태의 개미 우리가 있다. 다음 그림과 같은 형태이고, 하얀색 변으로만 개미가 다닐 수 있다. 개미 우리의 모습 곤충 관찰이 취미인 유이는 세 정육각 www.acmicpc.net 23/09/25 육각형을 어떻게 적절하게 잘 변형시키는 가가 관건인 문제다. 문제 접근 방식: 문제를 처음 보고 규칙성이 있는 DP문제인 줄 알고 한참 동안 점화식을 찾아 해맸다. 이후 규칙성이 없음을 깨닫고 백트래킹으로 접근했다. 이 문제의 핵심은 육각형을 어떻게 적절하게 잘 변형 시킬 수 있는가 이다. 일반적인 2차원 격자로는 상하좌우로 움직이기 때문에 120도 만큼을 돌아가는 것..
[Python] 1562번 계단 수 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 23/12/05 비트마스킹을 이용한 DP를 연습하기 좋은 문제이다. 클래스 5에도 있으니, 비트마스킹에 대한 개념을 이해한 뒤에 조금 생각해보고 풀면 더욱 도움이 될 것 같다. 문제 접근 방식: 길이가 매우 긴 자리수를 가지고 있는 특정한 계단 수에 대한 경우의 수를 구하는 문제이다. 계단 수이긴 하지만, $0$부터 $9$까지의 모든 숫자를 써야 한다는 점이 다르다. 즉, 우리는 숫자의 사용 여부를 관리해야 할 필요성이 있다. 그걸 DP 배열에 넣고 관리하기에는 조금 까다로운 면이 있다. 이럴 때 비트마스킹을 이용할 수..
[Python] 27172번 수 나누기 게임 https://www.acmicpc.net/problem/27172 27172번: 수 나누기 게임 《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다. 《수 나누기 게임》의 규칙은 다음과 같습니다. www.acmicpc.net 23/12/05 기존 에라토스테네스의 체 알고리즘을 응용한 문제로, 정확히 말하면 체의 원리를 이용한 문제여서 조금 신선하다고 할 수 있다. 클래스 5에도 있는 교육적인 문제이니, 안보고 해결하면 좋을 문제인 것 같다. 문제 접근 방식: 어떤 수가 다른 수의 약수가 되면, 그 수는 점수를 얻는 방식이다. 예를 들어 $3$과 $12$가 서로 게임을 한다고하면 $3$은 1점을 얻고 $12$는 1점을 잃는다...

티스토리툴바