알고리즘/백준

정답 코드 #15649번: N과 M(1) import sys def find_sequence(select): if len(select) == m: print(*select) for i in range(1, n+1): if i not in select: select.append(i) find_sequence(select) select.pop() return n, m = map(int, sys.stdin.readline().split()) find_sequence([]) 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc...

문제 접근 [백준 알고리즘] 7576번: 토마토 (Python / 파이썬) 문제 접근 헷갈렸던 문제이다. bfs를 사용하는데 시작 지점이 여러개다. 단순히 queue 사이클이 몇번 돌아갔는지 체크하면 당연히 더 큰 값이 나와 틀릴 것이기 때문에 한 사이클에 몇개의 요소가 gyujh.tistory.com 이전에 풀었던 7576번 토마토 문제의 3차원 버전이다. 이때 풀었던 방법과 다르게, 큐에 새로운 익은 토마토를 넣을 때 그 값에 이전 토마토 값 + 1 을 할당하여 날짜 계산을 더 쉽게 처리했다. 주의할 점으로는 시작점이 되는 토마토들이 1의 값을 가지고 있으므로, 위처럼 날짜 계산을 한다면 이 시작 값들은 0이 되거나 마지막에 최댓값을 구하고 1을 빼줘야 한다. 1의 의미는 하루가 지났음의 의미인데 ..

문제 접근 최단 경로를 구하는 문제이므로 bfs가 적합하다. n * m 행렬이 주어지고, 시작점이 정해져 있기에 생각보다 간단한 문제라고 생각했다. 벽(1)을 한 번만 부술 수 있으므로, 모든 벽들을 하나씩 부숴보고 bfs를 각각 돌려 최솟값을 구하면 된다고 생각했지만, n , m

문제 접근 deepcopy로 matrix를 하나 복사해서 색약용은 G -> R를 같은 문자로 만들어준다. 각각 순회하며 일반용은 값이 R, G, B일 때, 색약용은 R, B일 때 bfs를 호출한다. bfs 안에서는 방문한 곳을 X로 바꿔주고 탐색이 끝나고 1을 리턴한다. bfs가 실행된 횟수를 카운트하면 영역의 수가 된다. 정답 코드 # 10026번: 적록색약 import sys import copy from collections import deque def bfs(matrix, x, y, color): queue = deque() queue.append((x, y)) matrix[x][y] = 'X' dx, dy = [1, 0, 0, -1], [0, 1, -1, 0] while queue: cur =..

문제 접근 n x n 행렬을 받아, 안의 모든 요소가 같다면 그대로 리턴, 같지 않다면 행과 열을 절반으로 나누어 9개의 행렬로 분할하여 각각 재귀호출한다. 재귀함수를 하나 만들었고, 각 영역이 몇 개씩인지 세야 하므로 count[]라는 배열을 만들어 영역이 1로 채워진 경우 count[1]에, 영역이 0으로 채워진 경우 count[0]에, -1로 채워진 경우 count[-1]에 더해지도록 했다. 가장 중요한 부분은 행렬을 9개로 분할하는 것인데, 파이썬의 slicing을 사용했다. 현재 행(열) 사이즈를 1/3로 나누어 new_size에 할당하고 이를 이용해 3*3 for loop를 돌며 새로 만들(분할된) 행렬의 범위를 슬라이싱으로 정해주었다. 정답 풀이 #1780번: 종이의 개수 import sys..

문제 접근 n x n 행렬을 받아, 안의 모든 요소가 같다면 그대로 리턴, 같지 않다면 행과 열을 절반으로 나누어 4개의 행렬로 분할하여 각각 재귀호출한다. 재귀함수를 하나 만들었고, 하얀 색종이와 파란 색종이 영역이 각 몇 개씩인지 세야 하므로 count[]라는 배열을 만들어 영역이 1로 채워진 경우 count[1]에, 영역이 0으로 채워진 경우 count[0]에 더해지도록 했다. 가장 중요한 부분은 행렬을 4개로 분할하는 것인데, 파이썬의 slicing을 사용했다. 현재 행(열) 사이즈를 절반으로 나누어 new_size에 할당하고 이를 이용해 2*2 for loop를 돌며 새로 만들(분할된) 행렬의 범위를 슬라이싱으로 정해주었다. 정답 코드 #2630: 색종이 만들기 import sys def cou..

문제 접근 간단한 bfs 너비우선탐색 문제이다. 1) 밭을 돌면서 1을 발견할 때마다 bfs를 실행한다. 2) bfs 안에서, 이어진 1인 곳들을 방문하며 0으로 바꿔놓는다. 3) bfs가 끝날 때마다 정답에 1을 더한다. 정답 코드 #1012번: 유기농 배추 import sys from collections import deque def bfs(field, x, y): queue = deque() queue.append((x, y)) while queue: cur = queue.popleft() dx, dy = [0, 1, -1, 0], [1, 0, 0, -1] for i in range(4): nx, ny = cur[0] + dx[i], cur[1] + dy[i] if 0

문제 접근 헷갈렸던 문제이다. bfs를 사용하는데 시작 지점이 여러개다. 단순히 queue 사이클이 몇번 돌아갔는지 체크하면 당연히 더 큰 값이 나와 틀릴 것이기 때문에 한 사이클에 몇개의 요소가 큐에 들어갔고, 그것들에 의해서는 몇개가 큐에 추가되었는지 체크해야 한다. temp, count, answer 세 개의 변수를 사용해서 특정 주기에 초기화시켜서 풀었다. 예를 들어, 시작점(1)이 2개, 그 시작점으로 인해 생긴 것(2)이 2개, (2)에 의해 3개가 큐에 들어갔다면 날짜 카운트를 bfs 반복 주기의 2번째, 4번째(2+2), 7번째(4+3)마다 해줘야 한다. 내가 짠 대로 하면 마지막 토마토까지 다 익고 나서 그 토마토가 영향을 주는 시간까지 고려되기 때문에 -1을 해준다. 불가 판단(-1 ..

문제 접근 쉬운 문제인 줄 알았는데 시간이 많이 걸렸다. 올바른 괄호 체크는 ], )가 들어올 때만 체크해주면 된다. 숫자 계산이 헷갈리는데, 곱연산에 (,[ 왼쪽 괄호를 사용하고 합연산에 ),] 오른쪽 괄호를 사용한다. 이를 위해 temp와 answer 두 가지 변수를 선언했다. (()[[]]) 이 예제를 보고 설명해보면, 이는 2 * ( 2 + 3 * 3 ) = 22 로 나타낼 수 있다. 왼쪽 괄호가 들어올 때 1로 선언된 temp에 2 또는 3을 곱해준다. 그리고 (), []와 같이 바로 닫힐 때 answer에 temp를 더해준다. 이때 바로 닫히는 (), []와 같은 형태에서 합연산을 해주는 이유는 그것이 가장 깊은 괄호이기 때문이다. (), []의 형태가 등장할때까지 스택에는 곱해야 하는 (, ..

문제 접근 () 와 같이 내부가 없는 괄호는 레이저이다. 이외의 괄호들은 쇠막대를 표현한다. 이 부분을 보자. 스택에는 (, (, ( 3개가 들어가 있는 상태에서 레이저가 들어온다. 스택에 무언가 들어가 있다는 것은, 쇠막대기의 끝이 아직 발견되지 않았다는 뜻이고 이는 곧 레이저에 의해 영향을 받는다는 의미가 된다. 하나의 막대가 잘리면 두개가 된다. 따라 레이저가 들어올 때 현재 스택의 길이만큼 카운트를 추가해주면 된다. 이때 주의사항으로는 쇠막대기의 시작 지점에서 카운트를 1씩 미리 해줘야한다. 정답 코드 #10799번: 쇠막대기 import sys str = sys.stdin.readline().rstrip() stack = [] count = 0 for i in range(0, len(str)-1..