코딩테스트 - 그래프 - 가장 먼 노드 [Level3] 문제링크 : 가장 먼 노드 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr 문제풀이 그래프 문제입니다. 기존 BFS 풀이를 가지고 풀면 7,8,9 케이스에서 "시간 초과"를 만나게 됩니다. 그러기 위해서 그래프의 방법 중 "인접 행렬" 이 아닌 "인접 리스트"를 사용해야 합니다. list = [[0 for _ in range(n+1)] for _ in range(n+1)] 위 행렬 생성 코드 작성만 해놔도 시간 초과가 걸립니다. 인접 행렬의 경우 연결할 수 있는 모든 경우의 수를 체크를 하고 인접 리스트는 연결된 경우의 수만..

코딩테스트 - 깊이/너비 우선 탐색(DFS/BFS) - 네트워크 [Level3] 문제링크 : 네트워크 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제풀이 DFS 문제입니다. conected_check 배열에는 컴퓨터의 연결을 체크합니다. 연결 안 되어 있으면 False 되어있으면 True 연결 안되어 있는 컴퓨터의 경우 (connected_check == False) 이를 기점으로 dfs함수를 실행해 연결된 컴퓨터를 체크합니다. 기점과 연결된 컴퓨터를 conected_check에 tmp배열에 넣어 ..

코딩테스트 - 동적계획법(Dynamic Programming) - 정수 삼각형 [Level3] 문제링크 :정수 삼각형 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 문제풀이 다이나믹프로그래밍(DP) 문제입니다. 삼각형을 거꾸로 거슬러 올라간다고 생각하면 편합니다. 끝에서부터 시작을 해서 자신과 옆에 있는 숫자를 위에 있는 숫자와 더했을 때 더 큰 값을 위에 할당시켜줍니다. 할당이 끝나면 삼각형의 가장 밑줄을 없애고 반복합니다. 삼각형 원소가 1개가 남으면 자연스레 최댓값이 남게 됩니다. 가장 인기 많은 답변 코드는 간단하지만 막상 봤을때는 많이 난해하다고 느껴졌습니다. 분석하기도 힘..

코딩테스트 - 힙(Heap) - 디스크 컨트롤러 [Level3] 문제링크 : 디스크 컨트롤러 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 문제풀이 Heap 문제입니다. 그런데 저는 힙 없이 사용했습니다. 일단 가장 먼저 핵심적인 것은 "할 수 있는 작업에서 시간이 짧은 거부터 시작한다"라는 점입니다. 긴 작업 소요시간이 걸리면 그만큼 시간이 남은 작업만큼 배로 더해지기 때문입니다. 처음에 jobs를 "작업이 요청되는 시점, 작업의 소요시간" 순으로 정렬합니다. (정렬이 안되어 있음!!) jobs의 처..

코딩테스트 - 이분탐색 - 입국심사 [Level3] 문제링크 : 입국심사 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 문제풀이 이분탐색 문제입니다. 정답 시간의 범위를 생각하면 최솟값은 "1" 최댓값은 "가장 오래 걸리는 시간 X n명" 사이에 정답이 있습니다. 이제 최솟값과 최댓값의 중간값을 기준으로 해당 시간 때의 사람 수를 구해서 최소, 최대 시간을 중간값으로 이동하며 범위를 줄입니다. 1. 해당 시간에 사람이 더 많다? 최댓값을 중간값으로 해서 범위 줄이기 2. 해당 시간에 사람이 더 적다? 최솟값을..

[Level1] 코딩테스트 연습 - 정렬 - K번째수 문제링크 : K번째수 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr 문제풀이 forEach를 통해서 배열 안에 있는 조건을 순회합니다. 구조분해 할당을 사용해서 해당값을 받아줍니다. (start, end, target) (한번 배열에 안넣고 해봤는데 안되네요 ㅎㅎ;) 그리고 slice를 활용하여 배열을 잘라줍니다. 자른 배열을 정렬하고 target를 answer 배열에 넣으면 끝! 풀이 코드 가장 인기많은 답변 filter를 사용하고 sort를 체이닝해서 구현했다는 점 저와는 다르게 slice를 사용한게 아닌 filter..