파이썬

프로그래머스: 단어 변환 (파이썬, BFS)

변환 횟수가 최소인 경우를 구해야 하므로 BFS로 접근하였다. 처음에 단어들을 어떻게 그래프로 표현할까 하다가 변환 경우의 수를 그려보니 굳이 그래프로 표현 안해도 풀 수 있다는 생각이 들었다. 처음에 테스트케이스3에서 계속 틀렸었는데 그 이유는 두 단어간에 다른 알파벳 갯수를 셀 때 set을 이용해 세었기 때문이다. 그럼 'ccec'같은 단어는 'ce'가 되므로 적절한 비교가 이루어지지 않음을 알 수 있다. 아직 엣지케이스를 생각하는 능력이 부족한 것 같아 그 부분에 대해 좀 더 훈련이 필요하겠다.. 풀이 코드는다음과 같다. BFS는 넓이를 우선으로 탐색하므로 처음에 begin과 차이가 1인 단어들을 deque에 넣고 그 단어들에 대해 다시 차이가 1인 단어들을 deque에 넣으면 넓이 우선 탐색으로 ..

프로그래머스: 네트워크 (파이썬, DFS)

비교적 쉬운 난이도의 문제였다. DFS를 통해 그래프를 탐색하는 전형적인 문제였기 때문이다. LV3에서 정답률이 높은 문제가 LV2에서 정답률이 낮은 문제보다 쉬운 것 같다.. 먼저 두 노드간에 간선 유무를 2차원 배열을 통해서 알려주는데 인접 행렬을 이용해서 그래프를 표현한다. 그래프를 표현하는데는 인접 리스트와 인접 행렬이 있는데 난 인접 행렬을 선호하고 그 중에서도 본 문제풀이와 같이 부모, 자식을 각각의 인덱스에 해당하는 리스트에 넣어서 구현하는 방법을 선호한다. 문제풀이 코드는 다음과 같다. def dfs(node, graph, visited): visited[node] = True for child in graph[node]: if not visited[child]: dfs(child, gra..

프로그래머스: 게임 맵 최단거리(파이썬, 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..

밑바닥 부터 시작하는 딥러닝① 요약

딥러닝을 공부한지 두달정도가 지났고 딥러닝계의 바이블로 불리는 '밑바닥부터 시작하는 딥러닝①'로 시작하였다. 신경망(ANN)의 기초와 평가방법, 최적화 그리고 합성곱계층(CNN), 오버피팅 방지 등에 대해 배우는 책이였다. 책을 공부하며 정리한 요약본을 남겨본다. 책을 읽으며 생긴 의문점과 그에 대한 답은 후속 포스트에 남겨놓았다. 신경망에 대해 처음 배우는 장이다. ANN, 완전연결계층과 입력(label)을 이용해 머신러닝의 기초에 대하여 배웠다. ANN은 입력층, 은닉층, 출력층으로 나눌 수 있었고 층의 깊이를 깊게 할때는 은닉층을 깊게 쌓았다. 입력층에 데이터를 바로 입력하지 않고 데이터의 특성들을 고려하여 전처리 후, 입력하면 정확도를 더 높힐수 있었다. 모델을 평가할 때는 정확도와 손실함수라는 ..