안녕

0. 문제 링크 https://www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net 1. 풀이 방법 **코드 길이 주의 해당 알고리즘은 브루트포스로 풀었다. 최대 길이는 19이고, 따라서 연산자는 최대 9개가 가능하다. 중첩된 괄호는 불가능하므로, 연산자는 최대 5개까지 선택이 가능하다. 물론 연산자 5개는 단 한 번만 가능하다. 연산자 4개를 뽑는 경우도 의외로 적다. 중첩된 괄호라는 조건을 제외하면 최대 9C5 + 9C4 + 9C3 + 9C2 ..

0. 문제 링크 https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net 1. 풀이 방법 해당 문제의 핵심은 그룹 번호이다. DFS를 수행하던 도중 같은 그룹 번호를 만난다면 이는 싸이클이 생긴 것이고, Safe Zone을 하나 추가해야 한다. 하지만 만약 다른 그룹 번호를 만난다면, 그 그룹은 이미 Safe Zone이 있으므로, 그냥 break 하면 된다. 내 그룹이 해당 그룹에 편입한다고 생각하면 편할 것이다. (..

0. 문제 링크 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 1. 풀이 방법 입력을 받을 때, 사다리가 있는 곳이라면 왼쪽을 1, 오른쪽을 -1로 설정했다. 이제 사다리를 놓을 수 있는 곳을 후보군으로 찾는다. 이것을 이용해서 백트래킹 재귀를 돌리면 끝. 매우 간단하다. 추가로 각 라인 2. 코드 import sys input = sys.stdin.readline def solve(total, next): global minimum if ..

0. 문제 링크 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 1. 풀이 방법 해당 문제는 위상 정렬 알고리즘을 사용해야 한다. 위상 정렬 알고리즘은 싸이클이 없는 그래프에서, 각 노드들이 순서를 지켜야 할 때 사용된다고 한다. 해당 문제의 풀이 방법은 다음과 같다. 우선 나의 자식이 되는 문제들을 입력한다. -> 즉 인접한 노드를 입력한다. 또한 자식 노드는 앞서서 몇 개의 문제를 풀어야 하는지 기록해 놓는다...

0. 문제 링크 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 1. 풀이 방법 기본적으로 덱으로 해야 한다. 이유는 링크드 리스트이기 때문에 리스트로 관리한다면 pop(0) 과정에서 리스트의 모든 원소를 앞으로 가져오기 때문에 O(n)의 시간이 걸린다. 그리고 뒤집는 것도 하면 안 된다. 왜냐면 뒤집는 과정이 O(n)이기 때문이다. 따라서 뒤집는 '표시'를 써야한다. 2. 코드 import sys from collections import deque input = sys.stdin.readline ..

0. 문제 링크 https://www.acmicpc.net/problem/18808 18808번: 스티커 붙이기 혜윤이는 최근에 다양한 대회를 참여하면서 노트북에 붙일 수 있는 스티커들을 많이 받았다. 스티커는 아래와 같이 사각 모눈종이 위에 인쇄되어 있으며, 스티커의 각 칸은 상하좌우로 모두 연 www.acmicpc.net 1. 풀이 방법 가능한 좌표를 찾는 함수 놓을 수 있는지 판단하는 함수 스티커 붙이는 함수 회전 함수 이 모든 것을 조화롭게 사용하면 풀 수 있음 2. 코드 import sys input = sys.stdin.readline def canCoordinate(sticker): # 가능한 좌표를 찾는 함수 coordinate = [] yOffset = len(sticker) xOffse..

0. 문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 칸이거나 벽이며, 두 칸은 'C'로 표시되어 있는 칸이다. 'C'로 표시되어 있는 두 칸을 레이저로 통신하기 위해서 www.acmicpc.net 이전 풀이 2023.02.03 - [Computer Science/알고리즘] - [백준 - Python] 6087 - 레이저 통신 [백준 - Python] 6087 - 레이저 통신 0. 문제 링크 https://www.acmicpc.net/problem/6087 6087번: 레이저 통신 크기가 1×1인 정사각형으로 나누어진 W×H 크기의 지도가 있다. 지도의 각 칸은 빈 ..

0. 문제 링크 https://www.acmicpc.net/problem/3197 3197번: 백조의 호수 입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500. 다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다. www.acmicpc.net 1. 풀이 방법 큐를 4개 사용했음. (백조가 움직이는 큐, 물이 녹는 큐, 다음 턴에 백조가 움직여야 하는 큐, 다음 턴에 물이 녹아야 하는 큐) 사실 이것만 있어도 충분히 풀 수 있을거라 생각함 2. 코드 import sys from collections import deque input = sys.stdin.readline def waterMelt..

0. 문제 링크 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 1. 풀이 방법 이분 탐색 + 매개변수 탐색 풀이로 풀었다. 정답이 시간이므로, 시간의 리스트 내에서 매개 변수를 탐색하는 방식 start, end 시간은 아래의 코드와 같이 설정했음. 이유는 최솟값은 무조건 불가능한 것, 최댓값은 무조건 가능한 것으로 설정해야 하기 때문 이후 while 문을 돌면서, 각 심사대마다 정해진 시간만큼 받을 수 있는 인원 세었음. 받을 ..

0. 문제 링크 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 1. 풀이 방법 이 문제는 DFS + DP이다. 안 그래도 어려운 두 개를 붙였으니 더 어려웠던 것 같다. https://minny27.tistory.com/42 [백준 1937] 욕심쟁이 판다 (Python) 문제 : https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤..