Algorithm

프로그래머스: 게임 맵 최단거리(파이썬, DFS, BFS)

N*M 행렬에서 (0,0)에서 (N,M)까지 도달하는 최단경로를 찾아야 하는 문제이다. 최단거리를 구할때는 BFS를 이용하는 것이 좋다. 왜냐하면 DFS는 노드의 끝까지 도달하기에 여러 경로를 비교하기에는 시간복잡도가 크기 때문이다. DFS와 BFS를 구현해본지 오래 되었기에 공부하는 차원에서 두가지 방법 모두로 풀어보려 했다. 먼저 DFS이다. DFS는 분기점에서 트리의 끝까지 탐색하고 돌아오기에 탐색 시간이 길고 deepcopy를 이용해 행렬을 탐색마다 새로 할당해주어야 해서 일반적으로 시간초과가 잘 난다. BFS가 아닌 방법으로 최단경로를 찾으려면 사실 DFS말고 DP를 쓰는게 시간복잡도면에서 좋긴하다. from copy import deepcopy import sys sys.setrecursion..

프로그래머스: 햄버거 만들기(파이썬, 스택)

파이썬의 index에 접근하는 기능과 스택을 이용하면 쉽게 풀 수 있는 문제이다. 보통 list에서 원소들이 문제 조건에 맞는지 판단하는 문제는 스택, while문, 재귀를 이용하면 풀린다. 이 문제는 원소의 순서가 중요하므로 스택을 이용하여 풀어보았다. 리스트에 원소들을 계속 집어놓고 -index를 이용하여 리스트의 원소끝부터 4번째 원소까지가 [1, 2, 3, 1]이라면 리스트의 원소들을 4번 제거하고 count를 1 증가시키는 방식이다. def solution(ingredient): s = [] cnt = 0 for i in ingredient: s.append(i) if s[-4:] == [1, 2, 3, 1]: cnt += 1 for i in range(4): s.pop() return cnt

프로그래머스: 문자열 나누기 (파이썬, 반복문)

레벨2를 집중적으로 풀던 중 레벨1에 새로운 문제가 추가되어 풀어본 문제이다. 수를 계속 세야하므로 while문, 재귀함수 혹은 stack등 다양한 풀이가 있겠으나 제일 구현하기 쉬운 while문으로 풀어보았다. 문자열이 하나 남는경우만 잘 처리해준다면 까다롭지 않은 문제였던 것 같다. 나는 python의 list slicing을 이용하여 첫번째 문자 x와 x가 아닌 문자들이 갯수가 같아질 때마다 전체 문자열 s를 줄여주고, 문자열이 남은 경우 답을 하나 더해줌으로써 해결하였다. def solution(s): answer = 0 i,j = 0, 1 # cnt1은 첫번째 문자를 카운트하기 위한 용도이므로 미리 1로 지정하고, 반복문 시작구간을 첫번째문자 +1로함 cnt1, cnt2 = 1, 0 while ..

프로그래머스: 전화번호 목록 (파이썬, hash, dictionary)

hash문제이다. 자바에서는 해시값을 사용하는 자료형이 hashmap이고 파이썬에서는 dictionary이다. 내가 푼 문제가 아닌건 블로그에 기록하지 않는데 풀이가 너무 좋아서 내 나름의 수정을 더해 코드와 깨달은 점을 올려본다. 전화번호부가 10^6이기에 완전탐색을 하면 시간복잡도가 O(n^2)이므로 10^12이 되어 시간초과가 날 것 같았다. 따라서 처음에 푼 풀이는 비교하려는 수보다 큰 수일때만 접두사가 될 수 있다는 점, 비교하려는 수보다 값이 커지면 더 비교를 할 필요가 없다는 점을 이용해 반복문에 조건문을 추가하여 탐색을 중간에 멈추게 함으로써 시간복잡도를 nO(logn)으로 만들어 6*10^6으로 풀려고 시도했으나 보기좋게 마지막시도에서 계속 시간초과가 났다. 예를 들어 [121, 83, ..

프로그래머스: 숫자블록 (파이썬, 구현)

프로그래머스에는 약수를 구하는 문제가 꽤 많은데 그 중 한 문제이다. 길의 길이는 10^9이고 블록의 길이는 최대 10^7이기에 완전탐색을 하면 틀리는 문제이다. 약수를 효율적으로 구하는 것이 문제의 핵심인데 약수는 일일이 나눠서 구해야하므로 완전탐색으로 구해야하고, 더 빠르게 구하려면 약수는 제곱근 전 후로 쌍을 이룬다는 성질을 응용하여 제곱근까지만 약수를 구하고 그 약수들로 수를 나누어 나머지 약수들을 찾아야 한다. 먼저 내가 푼 코드이다. from bisect import bisect_left def get_yaksu(num): # 1은 모든 수의 약수 yaksu = [1] # 제곱근까지 약수를 구함 으로써 탐색 범위를 줄임 for i in range(2, int(num**0.5)+1): if nu..

백준 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: ..

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

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