본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 7490번 0 만들기 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 22/11/23 파이썬에 특화된 문제로, 만약 다른 언어로 이 문제를 풀었다면 힘들게 풀었을 것이다. 문제 접근 방식: 기껏 해봤자 입력으로 받는 자연수의 범위가 $9$까지 이기 때문에 그냥 깡으로 구현하면 될 것이라고 생각했다. $N$개의 자연수가 있다면 그 사이에 공백이든, 더하기 기호든, 빼기 기호든지 간에 $N-1$개의 기호가 들어가므로 가능한 모든 조합들을 itertools모듈의 product함수를 사용하여 구현하였다. 만약 product함..
[Python] 4179번 불! https://www.acmicpc.net/problem/4179 4179번: 불! 입력의 첫째 줄에는 공백으로 구분된 두 정수 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1000 이다. R은 미로 행의 개수, C는 열의 개수이다. 다음 입력으로 R줄동안 각각의 미로 행이 주어진다. 각각의 문 www.acmicpc.net 22/11/24 2022.11.29 - [백준 문제 풀이] - [Python] 5427번 불 [Python] 5427번 불 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 lighter.tistory..
[Python] 5427번 불 https://www.acmicpc.net/problem/5427 5427번: 불 상근이는 빈 공간과 벽으로 이루어진 건물에 갇혀있다. 건물의 일부에는 불이 났고, 상근이는 출구를 향해 뛰고 있다. 매 초마다, 불은 동서남북 방향으로 인접한 빈 공간으로 퍼져나간다. 벽에 www.acmicpc.net 22/11/20 전형적인 BFS문제로, 아이디어 하나만 떠올리면 쉽게 풀 수 있는 문제이다. 문제 접근 방식: 일반적인 BFS문제 같은 경우는, 시작점이 하나만 주어져서 그냥 하면 되는데, 이 문제 같은 경우, 불도 상근이처럼 네 방향으로 퍼진다고 했으므로, 불도 시작점에 넣고 BFS를 돌려주어야 한다. 이때, 불과 상근이는 당연히 따로따로 처리해줘야한다. 불과 상근이를 시작점으로 맨 처음에 넣을 때 유의해야..
[Python] 11729번 하노이 탑 이동 순서 https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 22/11/25 전형적인 웰 노운 재귀 문제이다. 근데 솔직히 나는 사람들이 웰 노운 문제라면서 내려치기 하는 거 별로 안 좋아한다. 이 문제는 하노이 탑의 움직임이 어떻게 분할되는가에 집중하면 재귀적으로 쉽게 해결할 수 있는 문제이다. 문제 접근 방식: 하노이 탑의 움직임이 어떻게 분할되는지 한번 그림으로 살펴보자. 예를 들어 $N = 4$일 때의 경우를 살펴보자. 그림을 보면, 먼..
[Python] 2036번 수열의 점수 / 1744번 수 묶기 https://www.acmicpc.net/problem/2036 2036번: 수열의 점수 n개의 정수로 이루어진 수열이 있다. 이 수열에서 한 정수를 제거하거나, 또는 두 정수를 제거할 수 있다. 한 정수를 제거하는 경우에는 그 정수가 점수가 되고, 두 정수를 제거하는 경우에는 두 www.acmicpc.net https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 22/11/20 / 22/11/23 두 문제는 $N$의 크기만 다르고 솔루션이 완전히..
[Python] 17430번 가로등 https://www.acmicpc.net/problem/17430 17430번: 가로등 2차원 공간 위에 가로등이 N개 배치되어 있다. i번째 가로등의 위치는 (xi, yi)이고, 각 좌표는 정수이다. 서로 다른 가로등의 위치가 같은 경우는 없다. 두 가로등 i와 j(i < j)가 있을 때, (xi, yj)와 (xj www.acmicpc.net 22/11/22 예전에 해결하려다가 실패하여 오랫동안 북마크란에 있었던 문제로, 드디어 해결하였다. 개인적으로는 왜 기하학 문제인지 잘 모르겠고, 오히려 정렬 문제에 가까운 문제라고 생각한다. 문제 접근 방식: 문제 자체는 정말 간단하다. 2차원 공간 위에 가로등이 $N$개 배치되어 있다. $i$번째 가로등의 위치는 $(x_i, y_i)$이고, 각 좌표는 정수이..
[Python] 1584번 게임 https://www.acmicpc.net/problem/1584 1584번: 게임 첫째 줄에 위험한 구역의 수 N이 주어진다. 다음 줄부터 N개의 줄에는 X1 Y1 X2 Y2와 같은 형식으로 위험한 구역의 정보가 주어진다. (X1, Y1)은 위험한 구역의 한 모서리이고, (X2, Y2)는 위험한 구역의 www.acmicpc.net 22/11/20 전형적인 그래프 탐색 문제로, 간선의 가중치 정보가 0과 1밖에 없기 때문에 다익스트라 대신 0-1 BFS로 풀어도 무방한 문제이다. 2022.09.02 - [백준 문제 풀이] - [Python] 13549번 숨바꼭질 3 (추후 보강 예정) [Python] 13549번 숨바꼭질 3 (추후 보강 예정) https://www.acmicpc.net/problem/1..
[Python] 23815번 똥게임 https://www.acmicpc.net/problem/23815 23815번: 똥게임 이 게임은 똥냄새가 너무 나서 도저히 볼 수가 없다! 따라서 당신은 직접 똥게임을 하지 않고 프로그램한테 똥게임을 시킬 것이다. 처음에는 사람 1명으로 시작한다. 당신에게는 총 $N$번의 턴 www.acmicpc.net 22/11/17 그리디와 DP를 섞은 문제로, 실수하기가 좋은 문제라고 생각한다. 문제 접근 방식: 나는 문제에서 주어진 선택지 $N$개의 제한이 최대 $100,000$개라는 것에 주목하였다. 일단, 두 가지 선택지 중에서 선택을 할 때 항상 큰 것을 선택해야 된다는 점은 너무나도 당연한 사실이다.(그리디 적인 접근) 문제는 스킵을 최대 한 번까지 할 수 있다는 점이다. 여기서 DP를 사용해야 한다...

티스토리툴바