알고리즘

백준 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행에 고정이므로 열의 크기에 대해서 조합을 뽑아야 한다. 그다음 적과..

백준 17070번: 파이프 옮기기 1 (파이썬, DFS, DP)

멘탈이 나간 문제이다. 골드V에서 이정도로 헤멘건 처음이다.. 삼성 A형 기출문제중 하나인데 2차원 배열이 주어지길래 당연히 dfs, bfs로 접근하려 했다. 나는 bfs로 접근하였는데 파이프가 가로인지, 세로인지, 대각선인지 판단을 해야해서 queue에 두 점의 좌표를 튜플과 리스트로 감싸 넣었다. 대각선일땐 세점이 방문 불가하고 파이프의 왼쪽은 파이프가 옮겨질 때 옮겨지기 전 파이프 오른쪽의 좌표로 옮겨진다는 두 포인트를 잡고 코드를 짰다. import sys from collections import deque def bfs(n): global cnt queue = deque(n) while queue: now = queue.popleft() if now[0][0] - now[1][0] == 0: ..