본문 바로가기

👨‍💻📱✍️🎢314

프로그래머스 Level 2 - 큰 수 만들기 문제 프로그래머스 - 큰 수 만들기 풀이 과정 k 개의 숫자를 제거하여 만들 수 있는 수 중에서 가장 큰 수를 찾는 문제입니다. 만약 브루트 포스 로 접근해 모든 조합을 만들어 본다면 최대 문자열의 길이 때문에 시간내에 수행이 불가능합니다. 대신에 큰 수를 구성하기 위한 조건으로 각 숫자를 탐욕적인 선택 에 따라 제거해준다면 선형 시간내에 수행이 가능합니다. 이를 위해서는 탐욕적인 선택 에 따라 우리가 절대 손해보는 일이 없음을 증명해야합니다. 어떤 숫자가 가장 큰 수가 되기 위해서는 가장 높은 자리수부터 큰 수를 가져야함은 자명합니다. 따라서 우리는 큰 자리수 부터 탐색을 수행하며 (인덱스로 따지면 0 부터) 가장 큰 수가 되기 위한 각 숫자들의 정당성을 따져도록 합니다. 어떤 수를 제거한다는 의미는 .. 2021. 3. 1.
프로그래머스 Level 3 - 섬 연결하기 문제 프로그래머스 - 섬 연결하기 풀이 과정 모든 정점을 연결하는 최소 신장 트리(MST)를 구하는 문제이다. 프림과 크루스칼 알고리즘을 활용할 수 있는데 이번에는 크루스칼을 사용했다. 크루스칼 알고리즘은 간선 정보들을 오름차순으로 정렬해준 다음, 사이클을 형성하지 않는 간선들을 탐욕적으로 선택해준다. 이를 위한 union-find 자료구조만 신경써서 구현하면 무난히 풀 수 있는 문제이다. 코드 def union(p, u, v): u, v = find(p, u), find(p, v) if u == v: return p[u] = v def find(p, u): if p[u] == u: return u p[u] = find(p, p[u]) return p[u] def kruskal(v, edges): ans.. 2021. 3. 1.
프로그래머스 Level 4 - 게임 맵 최단거리 문제 프로그래머스 - 게임 맵 최단거리 풀이 과정 BFS 를 통해 목표지점까지의 최단 거리를 탐색하는 문제이다. 방문여부와 거리 정보를 저장히기 위해서 딕셔너리 자료형을 사용할수도 있지만 게임맵과 동일한 이차원 배열을 선언해서 -1일 경우는 아직 방문하지 않은 지점, 그 외의 경우는 이미 방문해서 최단 경로를 구한 지점으로 판단하도록 했다. 이렇게 하면 트리 탐색시간을 절약할 수 있어서 더 빠른 수행시간을 가지게 된다. 코드 from collections import deque dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(maps, start): N, M = len(maps), len(maps[0]) q = deque() dist = [[-1 for _ in rang.. 2021. 3. 1.
프로그래머스 Level 3 - 입국 심사 문제 프로그래머스 - 입국 심사 풀이 과정 이 문제는 입력값이 매우 크게 주어져 있기 때문에 일반적인 방법으로 탐색을 수행하면 타임 아웃이 발생합니다. 효율성을 고려하지 않고 처음 떠올린 해법은 times 배열과 크기가 같은 jobs 배열을 생성한 뒤, 해당 배열에는 현재 손님의 업무가 끝나는 시간을 기록하고 다음번 손님의 입국 심사대를 고를때는 각 심사대의 시간을 jobs 배열에 각각 더해본 다음 가장 짧은 심사대로 배치시키는 것입니다. 하지만 이 방법은 배열의 크기에 비례하여 시간 복잡도가 증가하므로 보다 효울적인 탐색을 위해 이진 탐색 을 활용하기로 했습니다. 최악의 경우 소요되는 시간은 얼마일까요? 그건 바로 모든 손님이 가장 느린 심사대에서 심사를 받는 것입니다. 따라서 hi 를 이 값으로 설정.. 2021. 3. 1.
프로그래머스 Level 3 - 추석 트래픽 문제 프로그래머스 - 추석 트래픽 풀이 과정 주어진 문자열을 적절히 변환한 뒤 일정 크기의 윈도우와 최대한 많이 겹치는 트래픽의 수를 구하면 된다. 문자열 처리하기 밀리세컨드 단위의 시간 계산은 처음이라서 어떻게 해줘야할지 고민하다가 float 형으로 변환하여 사용하면 효율적일 것 같아서 이 방법을 사용했다. 다만 전날부터 트래픽이 시작 되었을 경우 트래픽 종료 시간 - 소요된 시간이 음수가 되는 경우가 있어서 이 부분에 대한 예외처리는 따로 해줘야 했다. 또한 float형으로 변환하고 산술연산을 수행하면 소수점 자리에 예상하지 못한 값들이 출력되는 경우가 있어서 round 함수를 통해 소수점 자리수를 고정시켜주는 작업이 필요했다. 최대 처리량 계산하기 최대 처리량을 구하는 부분이 예상보다 좀 까다로웠다.. 2021. 3. 1.
프로그래머스 Level 3 - 블록 이동하기 문제 프로그래머스 - 블록 이동하기 풀이 과정 로봇이 이동할 수 있는 모든 경우를 따져보며 탐색을 수행하면 된다. 최단 경로를 찾으면 바로 탐색을 종료하면되므로 같은 depth의 상태들을 탐색하기 위해 BFS를 사용했다. 다만 로봇의 상태와 회전 연산을 구현하는 부분이 매우 까다로웠다.. 로봇의 상태 나타내기 처음에는 board에 로봇의 상태를 표시해주며 이를 탐색에 활용하였지만 얼마 지나지 않아 이 방법이 굉장히 비효율적이라는 것을 알게 되었다. 어차피 board는 고정이고 우리는 로봇의 위치만 변경시키면서 탐색을 수행하면 되므로 board 대신 로봇의 죄표값을 통해 탐색을 수행하도록 하였다. 문제 풀이 후 다른 사람들의 코드도 봤는데 visited 배열을 따로 유지하고 Queue에 걸린 시간을 좌표값.. 2021. 3. 1.

티스토리툴바