본문 바로가기

알고리즘

 (368)
[Python] 10978번 기숙사 재배정 https://www.acmicpc.net/problem/10978 10978번: 기숙사 재배정 N이 4인 경우, 봄학기 때 4명의 학생 (민수, 동화, 갑도, 석주)이 각각 기숙사 A,B,C,D에 배정이 되었다면, (민수-B, 동화-A, 갑도-D, 석주-C), (민수-B, 동화-C, 갑도-D, 석주-A), (민수-B, 동화-D, 갑도-A, 석주 www.acmicpc.net 23/12/08 단순 교란 순열 문제이다. 알면 매우 쉽게 해결할 수 있다. 문제 접근 방식: 그냥 문제를 보면 교란 순열의 개수를 구하는 것과 같음을 알 수 있다. 교란 순열에 대한 간략한 설명은 다음 링크를 참고하자. https://ko.wikipedia.org/wiki/%EC%99%84%EC%A0%84%EC%88%9C%EC%97..
[Python] 14503번 로봇 청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 24/01/07 구현/시뮬레이션 문제로, 문제에서 요구하는 바를 그대로 구현하면 맞았습니다를 받을 수 있는 정직한 문제다. 문제 접근 방식: 이 문제를 접근할 때에 기존에 이렇게 $N \times M$형태의 map이 주어지고 이 위에서 BFS나 DFS를 진행하는 문제를 풀어봤다면 어떻게 접근할지 조금은 감이 잡힐 수 있을 것이다. 북, 동, 남, ..
[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도 만큼을 돌아가는 것..

티스토리툴바