본문 바로가기

파이썬

 (320)
[Python] 1229번 육각수 https://www.acmicpc.net/problem/1229 1229번: 육각수 육각수는 육각형을 이용해 정의할 수 있다. hn은 한 변에 점 1, 2, ..., n개가 있는 육각형을 점 하나만 겹치게 그렸을 때 존재하는 서로 다른 점의 개수이다. 그림 1 그림1은 h1, h2, h3, h4를 의미하며, www.acmicpc.net 23/03/09 조금은 독특한 방식의 DP문제로, 문제에서 주어진 정보를 적극 활용하여 미리 전처리를 해 시간을 대폭 줄여야 하는 문제이다. 만약 문제에서 주어진 정보가 없었더라면 조금은 더 까다로웠을 지 모른다. 이전에 도전했다가 시간초과를 여러 번 받아 실패했던 문제로, 이 글을 통해 도움을 받았으면 좋겠다. 문제 접근 방식: 이 문제는 캡틴 이다솜 문제와 유사한 방..
[Python] 2421번 저금통 https://www.acmicpc.net/problem/2421 2421번: 저금통 홍태석은 저금통 2개를 가지고 있다. 홍태석은 매일매일 하나의 저금통에 1원을 넣는다. 두 저금통에 모두 N원이 모이면 태석이는 새로운 장난감을 살 수 있기 때문에, 저금을 멈춘다. 홍태석은 www.acmicpc.net 23/03/12 전형적인 2차원 DP문제로, 현재 상태를 잘 정의하고 점화식을 세우면 쉽게 해결할 수 있다. 문제 접근 방식: 문제를 보고 처음에 발견한 사실은, 첫번째 저금통에 돈을 넣거나 두번째 저금통에 돈을 넣거나 둘 중 하나의 상태로만 갈 수 있다는 사실을 알아냈다. 이를 통해 $\mathrm{DP}[i][j]$ $=$ 첫번째 저금통에 $i$원을 넣고, 두번째 저금통에 $j$원을 넣었을 때, 소수..
[Python] 22770번 Ellipse Intersection https://www.acmicpc.net/problem/22770 22770번: Ellipse Intersection Input may contain multiple test cases. The first line is a positive integer n (n ≤ 100), denoting the number of test cases below. Each case is composed of two lines, the first one is the description of orbit A, and the second one the description of orbit www.acmicpc.net 22/12/31 전형적인 수학문제로, 극좌표로 적분을 해야하는 문제이다. 극좌표 적분에 관한 내용은 미적분학..
[Python] 1389번 케빈 베이컨의 6단계 법칙 https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 22/12/05 플로이드-워셜이나 BFS응용으로 풀 수 있는 문제로, BFS응용풀이에 대한 아이디어는 14217번과 같은 아이디어를 공유하고 있다. 2022.11.29 - [백준 문제 풀이] - [Python] 14217번 그래프 탐색 [Python] 14217번 그래프 탐색 https://www.acmicpc.net/problem/14217 142..
[Python] 1107번 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 22/12/04 조금 생각해야되는 브루트 포스 문제로, 조금만 생각한다면 그리디 알고리즘으로도 풀 수 있을 것 같다. 문제 접근 방식: 이 문제는 두가지 방법으로 풀 수 있다. 어떻게 하면 최소버튼을 누르게 만드는 번호를 찾을 수 있을까?로 접근한다면 그리디적인 접근으로 푸는 것이고, 그냥 생각 없이 채널 번호를 $0$부터 $1,000,000$까지 확인하면서 돌리면 브루트 포스로 ..
[Python] 26006번 K-Queen https://www.acmicpc.net/problem/26006 26006번: K-Queen 재헌이는 생일 선물로 크기가 $N \times N$인 체스판과 백색 킹 하나, 흑색 퀸 $100\ 000$개를 받았다. 킹은 8방향(상하좌우 및 대각선)으로 한 칸씩 이동할 수 있고, 퀸은 같은 행, 열, 대각선에 있는 상 www.acmicpc.net 22/12/01 그룹 연습 문제로 나왔던 문제를 풀었다. 실버 3치고는 개인적으로 어려웠던 편에 속해서, 실버 2로 충분히 올라가도 될 것 같다. 문제 접근 방식: 전형적인 구현 문제이지만, 구현을 잘 못한다면 어렵게 돌아갈 가능성이 존재한다. 먼저, 나는 흰색 킹이 8방향으로 움직일 수 있다는 점에 착안하여, BFS를 구현할 때처럼 dr, dc배열을 선언해주었..
[Python] 15650번 N과 M (2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 22/06/25 옛날에 풀었던 문제를 오늘(22/12/01) 백트래킹으로 다시 풀어보았다. 이전에는 파이썬의 itertools묘듈의 combinations를 사용해서 문제를 해결했지만, 백트래킹을 연습하는 문제로, 백트래킹으로 풀어보기로 했다. 문제 접근 방식: 첫 번째 접근 방법은 N과 M (1)의 코드를 변형한 코드이다. 2022.12.01 - [백준 문제 풀이] - [Python] 1564..
[Python] 15649번 N과 M (1) https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 22/11/30 백트래킹의 기초적인 문제로, 단계별로 풀어보기에서 풀어볼 수 있다. 문제 접근 방식: 백트래킹은 주로 재귀+가지치기로 접근이 되어진다. 말 그대로 Backtrack이기 때문에, 쭉 갔다가 다시 돌아오는 작업이 필요하다. 때문에 깊이 있게 들어가는 dfs탐색으로 대부분의 문제가 풀린다. dfs는 스택을 이용할 수도 있고, 재귀를 이용할 수도 있지만, 일반적으로 재귀를 이용한 구현이..

티스토리툴바