코딩테스트 - 깊이/너비 우선 탐색(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. 해당 시간에 사람이 더 적다? 최솟값을..

숫자판 점프 [2210] 백준 - https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 깃헙 - https://github.com/shs9509/study 문제 5×5 크기의 숫자판이 있다. 각각의 칸에는 숫자(digit, 0부터 9까지)가 적혀 있다. 이 숫자판의 임의의 위치에서 시작해서, 인접해 있는 네 방향으로 다섯 번 이동하면서, 각 칸에 적혀있는 숫자를 차례로 붙이면 6자리의 수가 된다. 이동을 할..