웨일의 블로그 웨일의 블로그

리트코드는 알고리즘 문제 사이트이다.그중 좋은 문제 150개를 엄선해서 모아놓은 분류가 있는데 이게 Top Interview 150이다.이거를 생각날 때마다 하나씩 풀다보니 어느새 다풀었다. 누구는 알고리즘이 현업에서 쓸 데 없다고도 하고누구는 알고리즘 잘하는 사람이 현업 개발 못하는걸 본 적 없다고 한다. 현업 개발을 많이 겪진 못했지만 지금까지 경험으로 보면일단 도메인을 많이 아는게 중요하다. 선임 개발자분들을 보면 개발 40 디버깅 40 회의 20의 비중을 두고 있다.디버깅 비중이 크다.예상치 못한 예외케이스가 발생할 수 있다는걸 알기 위해서는 일단 도메인에 대한 지식이 필요하다. 그리고 미처 처리하지 못한 예외케이스가 발생해 디버깅을 해야하는 경우에도 문제 발생 원인을 파악할 때 도메인 지식이 필..

문제 - 우박수열 정적분 문제링크 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 설명 우박수열 만드는법 양의 정수 k가 주어지고, k에서 시작하는 우박수열을 만듭니다. 이후, 우박수열을 y값으로 하고 x값은 0부터 각 수열 생성시마다 x = 1, x = 2 이런식으로 1씩 증가하도록 해서 (x, y)가 정해지며, 그래프를 그릴 수 있습니다. 마지막으로 넓이를 구해야 하는 x의 범위들이 주어지는데, 이때 해당 x 범위와 x축, y축, 그래프가 형성하는 영역의 넓이를 구하면 됩니다. 제한 사항 k: 1만 이하 ranges 길이: 1만 이하 풀이 과정 이..

문제1 - 부대 복귀 문제링크 문제 설명 양방향 그래프가 주어지고 출발지 노드들과 목적지가 주어질 때, 각 출발지에서 목적지 노드까지의 최단경로 거리를 구하는 문제입니다. 목적지에 도달할 수 없다면 -1입니다. 제약조건 노드n: 최대 10만개 간선roads: 최대 50만개 출발지sources: 최대 500개 풀이 과정 처음엔 그래프상에서 최단경로 길이를 구하는 문제라서 다익스트라를 사용해서 출발지 노드에서 목적지 노드까지의 최단경로거리를 구했습니다. 시행착오1(다익스트라, 실패) import heapq def solve(graph, dists, src, dest): q = [] dists[src][src] = 0 heapq.heappush(q, (0, src)) while q: curDist, curPo..

문제 - 양과 늑대 문제링크 문제 설명 이렇게 생긴 이진트리가 주어집니다. 0번 루트노드부터 탐색을 시작하는데, 노드에 양이 있으면 양 누적 카운트를 + 1 해주고, 늑대가 있으면 늑대 누적 카운트를 + 1 해줍니다. 그런데 [양 누적 1 해서 일단 왼쪽 양을 구한 후, 1->0->8->7->8->9 이렇게 이동해서 우측 서브트리의 양까지 다 구할 수 있습니다. 지금까지의 카운트는 양:4마리, 늑대:1마리이므로, 4번, 6번 늑대까지 방문해도 4대3으로 아직 괜찮습니다. 그래서 5번 양까지 구할 수 있습니다. 제한사항 트리의 노드 개수는 최대 17입니다. 풀이 과정 일단, 어떻게든 트리를 순회하면서 양과 늑대를 카운트해서 최대로 구할 수 있는 양을 구해야 합니다. 그리고, 한번 방문한 노드를 다시 방문할..

문제 - 타겟 넘버 문제링크 문제 설명 이렇게 numbers와 target이 입력으로 주어지면, numbers의 모든 숫자들을 각각 더하든지 빼든지 해서 target값을 만들어내는 경우의 수를 구하는 문제입니다. 첫번째 예시 입력에 대해 다음과 같은 경우의 수들이 있습니다. 이런식으로 각 숫자 앞에 +를 붙일건지 -를 붙일건지 선택해서 다 계산한 결과가 target이면 됩니다. 풀이 과정 각 숫자에는 부호가 할당되어야 합니다. 그리고 각 숫자마다 붙는 부호는 다른 숫자들과 독립적입니다. 이러면 각 숫자마다 +-의 두가지 경우가 있습니다. 모든 숫자에 대해 +-를 붙이는 경우의 수를 구하는 데 좋은 알고리즘은 DFS가 있습니다. """ 각 숫자에 대해 -, + 할당 dfs(order, val) """ de..

오늘 배운 점 갑자기 떠오른 아이디어가 실마리가 될 수 있습니다. 빠를거라고 예상한 풀이가 예상외로 느릴 수 있습니다. 문제 - 디펜스 게임 문제링크 문제 설명 병사 n명으로 enemy([n1, n2, n3,...])을 상대해야 합니다. 1라운드에는 n1, 2라운드에는 n2... 이런식으로 각 라운드마다 상대해야 하는 적의 수가 enemy에 담겨 있습니다. 그리고 병사와 적은 1대1 교환비로 적을 처리할 수 있습니다. k개의 무적권이 주어지는데, 무적권 1개를 사용하면 해당 라운드는 병사를 사용하지 않고 다음 라운드로 넘어갈 수 있습니다. 이때, 승리할 수 있는 최대 라운드를 구하면 됩니다. 제약 조건 n이 10억인 점은 문제가 되지 않지만 enemy가 100만이기 때문에 O(N)이나 O(NlogN) 과..

문제 - 등산코스 정하기 문제링크문제 설명산이 있고 산에는 지점들이 있습니다. 지점은 여러 개의 출발지와 여러 개의 정상, 그리고 일반 지점들이 있습니다. 출발지에서 시작해서 정상을 찍고 다시 원래 출발지로 돌아오는 경로가 있을 때, 해당 경로는 시작 출발지와 끝 출발지는 같고, 중간에 다른 출발지를 거치지 않고, 정상은 무조건 한번만 거쳐야 합니다. 이때, 위 조건을 만족하는 모든 경로 각각에서 각 지점을 건너는데 걸리는 시간 중 가장 긴 시간이 있을텐데 이를 intensity라 하고, 모든 경로를 통틀어 최소 intensity를 구하는 문제입니다. 풀이 과정처음에는 같은 지점을 여러번 반복해서 방문할 수 있으므로, 비트마스킹을 이용헤서 중복 경로 체크를 해야 하는 줄 알았습니다. 하지만 이전에 방문한..

문제 - 무인도 여행 문제링크 문제 설명 2차원 격자 maps가 주어지고, 격자는 바다를 의미하는 'X'와 1~9 사이의 숫자로 이루어져 있습니다. 해당 칸이 숫자라면 땅을 의미하고, 상하좌우로 서로 연결된 땅은 하나의 섬입니다. maps 내의 모든 섬에 방문할 때, 각 섬에 적혀있는 모든 숫자를 다 더한 값을 담아 반환하면 됩니다. 풀이 과정 일반적인 BFS 섬 찾기 문제입니다. maps를 2중 for 문 순회하며 섬을 찾아 마킹하며 숫자를 더한 후 BFS가 끝나면 더한 값을 저장해 놓다가 모든 순회가 끝나면 반환하면 됩니다. from collections import deque def solution(maps): answer = [] n = len(maps) m = len(maps[0]) dx = [..