[Python] 백준 27961 - 고양이는 많을수록 좋다
문제https://www.acmicpc.net/problem/27961 해설2배수로 늘려가며 탐색해 보면 쉽게 해결된다. 0이 될 수 있는 조건은 주의해야 한다. Pythonfrom sys import stdindef magic(n: int): if n == 0: return 0 cnt = 1 cat = 1 while cat
문제https://www.acmicpc.net/problem/27961 해설2배수로 늘려가며 탐색해 보면 쉽게 해결된다. 0이 될 수 있는 조건은 주의해야 한다. Pythonfrom sys import stdindef magic(n: int): if n == 0: return 0 cnt = 1 cat = 1 while cat
문제https://www.acmicpc.net/problem/15686 해설각 치킨집의 조합을 만들어서 Brute Force를 이용하여 해결하였다. 백준이 지금 시간 기준으로 이상한건지는 모르겠지만 Python과 Java 코드 모두 제출하면 성공일 때도 있고 컴파일 에러나 런타임 에러(NZEC)가 발생할 때도 있다. 정답이었던 코드를 그대로 제출해도 이런 결과가 나와서 원인이 뭔지 찾지 못하였다. 혹시 비슷한 현상이 일어나거나 업로드한 코드에서 문제가 있는 부분을 알고 계신다면 댓글 부탁드립니다. Pythonfrom sys import stdindef get_distance(combination: list): total_distance = 0 for hx, hy in houses: ..
문제https://www.acmicpc.net/problem/2615 해설반복문을 이용한 완전 탐색 방법으로 해결할 수 있었다. DFS로도 접근해보았는데 잘 해결되지 않아 방법을 바꾸어 다시 접근하였다. 6목이 되는 케이스에 대한 검사가 필요했고, directions 부분에 왔던 방향을 되돌아가지 않도록 설정하는 아이디어도 주요했던 것 같다. Pythonfrom sys import stdin# 방향: 오른쪽, 아래, 대각선(↘), 대각선(↗)directions = [(0, 1), (1, 0), (1, 1), (-1, 1)]def check_winner(row: int, col: int, direction: tuple): stone = board[row][col] depth = 1 x, y..
문제https://www.acmicpc.net/problem/2529 해설Brute Force로 접근하였는데 생각보다 풀어내기 쉽지 않았다. 이후 생각을 바꿔 DFS를 이용하였다. 뿐만 아니라 백트래킹(Backtracking)에 대한 이해도 필요하다. 탐색 도중 더 깊은 depth에 대한 탐색이 필요 없을 때 pruning이라 불리는 가지치기를 이용하여 유망한(promising) 경로만 계속 진행한다. 이 과정은 "선택 - 탐색 - 복구" 구조로 구성되어 있고, 이를 통해 가능한 모든 경우의 수를 탐색할 수 있다. 이 Backtracking은 마치 임계구역 문제에서 한 번에 한 경로만 특정 숫자를 사용할 수 있도록 보호하는 역할과 유사한데, 공유 메모리 문제에서 고려되는 Critical Section에 ..
문제https://www.acmicpc.net/problem/1051 해설Brute Force를 이용하여 모든 경우의 수를 탐색하여 해결하였다. CNN에서의 Sliding Window를 연상해보면 더 쉽게 해결할 수 있다. Pythonfrom sys import stdindef brute_force(matrix: list, n: int, m: int): max_size = n if n Javaimport java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new Inpu..
문제https://www.acmicpc.net/problem/1018 해설BFS로 접근하는 것으로 착각하여 시간 소비를 많이 하였다. Brute Force를 이용하여 완전 탐색을 진행하면 쉽게 해결할 수 있는 문제였다. Pythonfrom sys import stdindef brute_force(matrix: list, x: int, y: int): w_start = 0 b_start = 0 for i in range(8): for j in range(8): if (i+j) % 2 == 0: if matrix[x+i][y+j] != "W": w_start += 1 eli..