백준

백준 17135번: 캐슬 디펜스 (파이썬, 완전탐색, 구현)

정말 어려운 문제였다. 처음 문제를 봤을때 완전탐색 혹은 DP중에 고민했는데 시간복잡도가 M개 중에 3 개를 뽑는 조합 mC3 = m(m-1)(m-2)/6, 적들이 N번 움직이므로 반복문 O(N), 사정거리 D만큼, M열에 대해 거리를 탐색해야 하니 O(N^2)으로 M= 15, N = 15일 때 455*15*15*10= 10^6으로 시간제한인 1초에 넉넉하게 맞출 수 있어 완전탐색으로 풀어야 겠다고 생각할 수 있었다. 그러나 구현 문제를 거의 처음 풀어봐서 시간이 오래 걸렸는데 반복문이 많이 중첩되다 보니 순서나 반복값에 있어서 헷갈림이 많았다. 알고리즘은 간단하다. 먼저 조합으로 [0:M]에 대해 3개를 뽑는다. 이때 궁수의 위치는 N행에 고정이므로 열의 크기에 대해서 조합을 뽑아야 한다. 그다음 적과..

백준 2623번: 음악프로그램 (파이썬, 위상정렬, Cycle)

유향그래프를 정렬하는 문제이고 사이클이 없으므로 위상정렬을 이용하여 풀었다. 앞서 푼 '2252번: 줄세우기' 문제와 사이클이 존재할 때와 존재 안할 때를 판별하는 것이 차이점이 였다. 위상 정렬을 하기 위해서는 사이클이 없어야 하므로 문제의 조건을 하나 추가한 것 같다. 위상정렬은 DFS로 그래프를 정렬 후 뒤짚는 방식으로 구현하였다. 사이클 판별은 두가지로 해보았다. 첫번째 방법은 노드 수 N과 크기가 같은 boolean 배열을 하나 만들어서 V의 종단노드부터 boolean 배열의 원소 값을 True로 한다. 그 후 종단노드의 부모노드 순으로 boolean 배열의 원소 값을 True로 한다. 이때 부모노드의 boolean 배열의 원소값이 False라면 Cycle이 존재한다고 판별하는 방법이다. 왜냐하..

백준 13565번: 침투 (파이썬, DFS)

전류가 통하는 격자는 0, 통하지 않는 격자는 1이다. outder side에서 inner side로 침투하면 성공이므로, 첫번째 행의 원소들에 대해서만 DFS를 하면 된다. 마지막 행에 도달했다는것을 알기 위해 방문을 확인하는 배열을 따로 만들었다. outer side에서만 DFS를 하므로(방문), inner side에 방문을 했다면 침투에 성공한 것이기 때문이다. 여담으로 출력을 Yes로 했다가 계속 틀려서 머리가 터지는 줄 알았는데 대소문자 구별을 잘해야 하고 문제 조건을 꼼꼼히 읽어야 한다.. import sys sys.setrecursionlimit(10**9) dx = [0, 1, 0, -1] dy = [1, 0, -1, 0] def dfs(x, y): visited[x][y] = True f..

백준 2468번: 안전영역 (파이썬, DFS)

문제 자체는 기본적인 DFS의 구현이였으나 안전한 영역의 최대 개수를 구하기 위해 한번의 과정이 더 필요하였다. 2차원 배열이기 때문에 각 배열의 원소들에 접근하기 위해서는 2중 반복문이 필수이다. 이때 높이는 1이상 100이하 정수이고 N은 100보다 작으므로 3중 반복문이라 하더라도 100^3=10^6, 시간복잡도는 O(N^3)으로 시간초과에 걸리지는 않는다. 따라서 입력되는 배열들 각각에 max함수를 적용후, 그 값들에 다시 max함수를 적용하여 반복문의 최대 range를 정하고 dfs를 적용하면 된다. import sys sys.setrecursionlimit(1000000) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def dfs(x, y): visited[x][y] =..

백준 2667번: 단지번호 붙이기 (파이썬, BFS)

BFS로 푸는 문제이다. 아파트가 있는곳은 1, 아파트가 없는곳은 0으로 표시되기 때문에(이진법) 방문여부를 확인하는 배열을 따로 만들지 않고 방문 시 배열값을 0으로 함으로써 다시 방문할 일이 없게 하였다. 근소한 차이긴 하지만 실행시간을 약간이라도 줄이는 것을 확인하였다. import sys from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(x, y): global cnt graph[x][y] = 0 q = deque([(x, y)]) while q: now = q.popleft() for i in range(4): nx = now[0] + dx[i] ny = now[1] + dy[i] if 0

백준 7576번: 토마토 (파이썬, BFS)

개인적으로 좀 어려웠던 문제였다. 왜냐하면 쉬운 BFS문제들은 보통 탐색을 한 회 할 때마다 카운트를 늘리면 되는데, 이 문제는 한 계층을 다 탐색한후에 카운트를 늘려야 했기 때문이다. 왜냐하면 1초가 지날때, 익은 토마토 주변의 토마토들이 모두 익기때문이다. 따라서 1초마다 익은 토마토 주변의 모든 토마토가 익는다는것을 구현하기 위해 입력받은 값에서 값이 1인 값들을 새로운 배열에 저장하고, 그 배열을 BFS의 입력으로 썼다. 그리고 while문 안에도 빈 배열을 선언하였는데, 입력받은 값들 중 값이 1인값들 주변을 탐색하였을 때 1초후에 값이 1이 되는 값들(0)을 배열에 모아 덱에 저장하기 위함이다. 이렇게 덱에 있는 원소(배열)를 다 탐색한 후에 카운트를 늘리면 통과한다. 또한 모두 익지는 못했을..

백준 1931번: 회의실 배정 (파이썬, 그리디 알고리즘)

그리디 알고리즘 문제의 유명한 예시이다. 그리디 알고리즘을 풀기 위해서는 최적해를 구해야하는데, 최적해라는것을 증명하기가 쉽지 않아 대부분 풀이를 떠올리고 반례를 생각해보는것 같다. 반례가 없으면 최적해라고 생각하는 것이다. 나도 처음에는 단순하게 끝나는 시간을 기준으로 정렬하였다. 그러나 끝나는 시간순으로 답을 골랐을때는 틀렸었다. 왜인지를 계속 고민했는데 예시에만 집중하여 끝나는시간에 중복이 있을수도 있다는 생각을 간과한 것이다. 따라서 lambda식으로 끝나는시간으로 먼저 정렬 후 그다음 정렬 순위로 시작하는 시간을 주었다. 그렇게 정렬 후 첫번째 끝나는 시간보다 큰 시간이 있으면 그 시간을 고르는 식으로 알고리즘을 짜주었더니 맞았다. import sys num = int(sys.stdin.read..

백준 1198번: 삼각형으로 자르기 (파이썬, 완전탐색)

완전탐색 알고리즘으로 최댓값을 구하기 위해 꼭지점을 하나씩 지워가며 그 값들을 배열에 넣고, max함수를 이용해서 최댓값을 구하였다. 삼각형의 넓이는 꼭지점들이 주어지므로 꼭지점 공식을 이용하였다. N각형에서 나올수 있는 삼각형의 경우의 수(갯수)는 nC3이므로 n(n-1)(n-2)/6이다. 완전탐색으로 풀기 위하여 N각형에서 시계방향으로 점을 하나씩 지워가며 계산하였다. 오각형을 예시로 들자면 다음과 같다. 물론 완전탐색문제는 파이썬 library인 combination을 이용하여 풀수도 있다. 완전탐색이나 조합이나 가능한 모든 경우의 수를 구하는 것이기 때문이다. 조합을 이용하여 푼 풀이는 다음과 같다. from itertools import combinations import sys def tria..