코딩테스트 - 그래프 - 가장 먼 노드 [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] 코딩테스트 연습 - 완전탐색 - 모의고사 문제링크 : 모의고사 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 programmers.co.kr 문제풀이 패턴을 따로 배열에 저장한 이후 answers의 한 원소마다 순회하며 정답을 체크합니다. 정답 패턴이 넘어가는 것을 방지하기 위해 % 를 통해 순환하도록 만듭니다. 각 삼인방에 정답을 맞힐 때마다 카운트할 수 있는 배열을 만듭니다.(count) Math.max를 활용해 카운트 값 중 최댓값을 구하고 해당 값을 출력합니다. 풀이 코드 가장 인기 많은 답변 filter를 사용했다..