목록알고리즘/프로그래머스 (62)
어흥
문제 링크: programmers.co.kr/learn/courses/30/lessons/64063 코딩테스트 연습 - 호텔 방 배정 programmers.co.kr 1. 주의할 점 - 범위가 1~10^12를 어떻게 처리할 것인가 → 배열 시도시 컴파일 에러 - Room_Number 벡터로 1이 20만개 들어온다고 할때, 하나하나 다음칸을 확인한다 → O(N^2): TLE 2. 구현 - 해당 방이 배정되었다면, 다음 방을 가리키도록 한다 → '유니온 파인드' 처럼 생각한다 → O(NlgN) Ex. 순서대로 2,2,3이 들어오고 추가로 2가 들어온다면, 2,2,3은 모두 다음으로 비어있는 칸인 5를 가리키도록 하여 2가 5에 할당되도록 한다 - Map을 이용하여 10^12도 처리할 수 있도록 한다. Map..
문제 링크: programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 [23:59,23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59, 23:59] 18:00 programmers.co.kr 1. 주의할 점 - 문자열 처리를 통해 각 시간을 어떻게 저장할 것인지 정한다 2. 구현 - Arr[10] 벡터를 생성하여 셔틀의 수용인원만큼 수를 각 셔틀에 저장한다(최대 셔틀이 10개라고 적혀있다) - 각 시간을 분으로 환산하여 V 벡터에 저장한 이후, 오름차순으로 정렬한 이후, Queue에 수를 순차적으로 넣..
문제 링크: programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 1. 주의할 점 - Map이나 배열을 통해 몇번 만에 Words에 있는 단어에 도착했는지 저장해야 한다 2. 구현 - DFS(현재 문자열, 바꾼 횟수)를 수행하며 DFS 함수 내에는 다음과 같은 조건들이 있다 - DFS() 함수의 가장 처음에는 현재 바꾼 횟수가 이미 구한 정답보다 많다면 Return한다 - 현재 문자열이..
문제 링크: programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있�� programmers.co.kr 1. 주의할 점 - 이미 네트워크를 이룬 컴퓨터는 세지 않도록 한다 - 기본적인 BFS문제 2. 구현 - 전달받는 배열을 바탕으로, 1의 원소를 가지고 있다면(열!=행) V[] 벡터에 간선을 저장한다 - 0번부터 컴퓨터의 수-1 까지 For문을 돌리고 아직 네트워크를 형성하지 않은 컴퓨터라면(Check[] 값이 false) Queue에 넣고 해당 컴퓨터와..
문제 링크: programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 � programmers.co.kr 1. 주의할 점 - 이분탐색으로 해결한다 - Right 포인터의 값이 Int값을 벗어날 수 있다 (Long Long으로 형변환 필요) -> 8번 TC 2. 구현 - Tip) Mid의 값을 구할 때 Left+(Right-Left)/2로 한다. Right+Left/2로 할 경우, Int 혹은 Long Long의 범위를 벗어나면 음수값이 저장되므로 사전에 예방한다. ..
문제 링크: programmers.co.kr/learn/courses/30/lessons/43237 코딩테스트 연습 - 예산 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그�� programmers.co.kr 1. 주의할 점 - 이분탐색을 통해 접근하며, 입력 받는 벡터를 미리 Sort 하면 편하다 2. 구현 - 입력 받는 벡터를 Sort한 후, 이분탐색을 통해 상한액을 Mid만큼으로 잡았을 때, M 이하의 예산으로 배분 가능하면 Mid를 늘리고, 아니라면 Mid를 줄이면서 Mid를 구한다 - Mid로 배분이 가능할때마다 Answer의 값을 Mid로 갱신한다 #inclu..