Algorithm
백준 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)을 배열에 모아 덱에 저장하기 위함이다. 이렇게 덱에 있는 원소(배열)를 다 탐색한 후에 카운트를 늘리면 통과한다. 또한 모두 익지는 못했을..
백준 1654번: 랜선 자르기 (파이썬, 이분탐색)
랜선을 잘라서 N개의 랜선을 만들어야 한다. 시작값을 1로 설정하고, N이 1일때는 랜선중에 가장 큰값을 써야하기때문에 max(랜선)을 끝값으로 설정하였다. 그 후 입력으로 받은 랜선들을 각각 중간값으로 나누어 그 몫을 더하고, 그 값이 N보다 크면 시작값을 중간값으로 하여 몫들의 합이 더 작아지게 한다. import sys K, N = map(int, sys.stdin.readline().split()) wires = [] for i in range(K): wires.append(int(sys.stdin.readline())) start, end = 1, max(wires) while start = N: start = mid + 1 else: end = mid - 1 print(end)
백준 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..
백준 14786번: Ax+Bsin(x)=C ② (파이썬, 이분탐색)
이번 주에는 이분탐색을 공부 하고있었고, 이분탐색으로 푼 문제중 난도가 가장 높았던 문제였다. 다항함수와 삼각함수의 합으로 이루어진 그래프와 상수와의 교점을 구하는 문제이기에 답이 정수로 떨어지지 않고, 오차를 허용하는 형태의 처음보는 문제였다. 구간을 정한후 이분탐색을 해야 할것 같았는데 구간을 어떻게 정할지를 구하기 위해서 그래프부터 살펴보았다. 구간을 최대한 좁게 잡아야 탐색시간을 줄일 수 있다고 생각했기 때문이다. 처음에는 탐색구간을 정하기 위해 함수의 최대값을 가지는 지점을 구하려 하였으나 y =x는 x가 무한대일때 발산하고, y=sinx는 진동하므로 x+sinx는 발산한다. 따라서 구간설정에 극대점, 최댓값등은 구간설정에 이용할 수 없을것 같았다. 다음으로 함수의 그래프를 그려보면서 A,B,C..