문제 풀이

[baekjoon 3079] 입국심사 (매개변수탐색, 이분탐색) (C++)

https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 심사대의 개수와 심사를 할 사람 수가 주어진다. 각 심사대에서 걸릴 수 있는 시간은 최대 10^9이고, 총 10만 개가 있다. 매개 변수 탐색을 통해서 우리가 찾으려는 값은 최종 걸리는 시간이다. 만약 자리가 1 2 3 4 5가 있고, 최종 걸리는 시간이 10이라고 가정한 상황이면 총 10의 시간 동안 몇 명이 앉을 수 있을까? 1의 자리에 10명, 2의 자리에 5명, 3의 자리에 ..

[프로그래머스 카카오 블라인드 채용 2021 3번] 순위 검색 (구현, 이진탐색) [C++]

https://programmers.co.kr/learn/courses/30/lessons/72412

[baekjoon 2075] N번째 큰 수 (우선순위큐, 정렬) (C++)

https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 이런 표가 주어지고, 같은 열에 있는 수는 아래로 갈수록 커지는 특징이 있다. 이런 수의 구성 중에서 N번째 큰 수를 찾는 것이다. 이 문제의 메모리 제한은 4MB로, 모든 수를 입력받아서 정렬 후 N번째를 찾는 방법은 메모리 초과가 날 것으로 예상되었다. (N은 1500개까지) 따라서, 우선순위 큐나 벡터+정렬을 이용해서 한 줄을 입력받고 정렬한다. 이후에, 거기서 N개의 수만 남기고 모두 pop 한다..

[프로그래머스 위클리 챌린지 3주차] 퍼즐 조각 맞추기 (구현, BFS) [C++]

https://programmers.co.kr/learn/courses/30/lessons/84021 코딩테스트 연습 - 3주차 [[1,1,0,0,1,0],[0,0,1,0,1,0],[0,1,1,0,0,1],[1,1,0,1,1,1],[1,0,0,0,1,0],[0,1,1,1,0,0]] [[1,0,0,1,1,0],[1,0,1,0,1,0],[0,1,1,0,1,1],[0,0,1,0,0,0],[1,1,0,1,1,0],[0,1,0,0,0,0]] 14 [[0,0,0],[1,1,0],[1,1,1]] [[1,1,1],[1,0,0],[0,0,0]] 0 programmers.co.kr 퍼즐 조각 채우기 문제 설명 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸..

[프로그래머스 2020 카카오 인턴쉽 ] 키패드 누르기 (구현) [C++]

https://programmers.co.kr/learn/courses/30/lessons/67256 코딩테스트 연습 - 키패드 누르기 [1, 3, 4, 5, 8, 2, 1, 4, 5, 9, 5] "right" "LRLLLRLLRRL" [7, 0, 8, 2, 8, 3, 1, 5, 7, 6, 2] "left" "LRLLRRLLLRR" [1, 2, 3, 4, 5, 6, 7, 8, 9, 0] "right" "LLRLLRLLRL" programmers.co.kr 문제 설명 스마트폰 전화 키패드의 각 칸에 다음과 같이 숫자들이 적혀 있습니다. 이 전화 키패드에서 왼손과 오른손의 엄지손가락만을 이용해서 숫자만을 입력하려고 합니다. 맨 처음 왼손 엄지손가락은 * 키패드에 오른손 엄지손가락은 # 키패드 위치에서 시작하..

[baekjoon 11659] 구간 합 구하기 4 (누적합) (C++)

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 기본적인 누적합 문제이다. 누적합 문제를 최근에 안 풀었더니 투 포인터로 접근했다가 시간 초과가 났다. 입력을 받으면서 앞의 인덱스의 누적 합을 따로 저장해준다. 그러면 start와 end의 구간 합을 sum[end] - sum[start-1]의 식으로 O(1)에 구할 수 있다. 여기에 쿼리가 추가되어 값이 수정되면서 구간 결과을 구하려면 세그먼트 트리 문제로 된다. 수많은..