Let's Begin Programming

www.acmicpc.net/problem/1300 1300번: K번째 수 세준이는 크기가 N×N인 배열 A를 만들었다. 배열에 들어있는 수 A[i][j] = i×j 이다. 이 수를 일차원 배열 B에 넣으면 B의 크기는 N×N이 된다. B를 오름차순 정렬했을 때, B[k]를 구해보자. 배열 A와 B www.acmicpc.net 이 문제도 파라메트릭 서치 유형의 이분 탐색 문제이다. 이 문제도 해결 방법이 쉽게 떠오르지 않아 다른 사람들의 설명을 많이 참고했다. 해설을 들어도 바로 이해가 되지 않아서 예시를 하나 하나 따라가보면서 이해하려고 노력했다. 이해하고 코드를 작성하고 보니 문제의 길이만큼 코드의 길이도 짧았다. 하지만 만약 코딩테스트나 시험에서 이 문제를 만났다면 쉽게 이분 탐색을 생각하지 못했을..

개발 공부 (알고리즘) 2021. 2. 23. 06:15

www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 이 문제는 바로 해결 방법이 떠오르지 않아서 다른 분의 해결 방법을 참고했다. blog.naver.com/kks227/220444432628 [2110번] 공유기 설치 https://www.acmicpc.net/problem/21102110번: 공유기 설치www.acmic... blog.naver.com 사실 이전의 파라메트릭 서치 유형의 문제이고 크게 다르지..

개발 공부 (알고리즘) 2021. 2. 23. 03:45

www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 직전에 풀었던 랜선 자르기 문제와 거의 동일한 문제이다. 문제의 내용이나 숫자는 다르지만 결국 푸는 방식은 같고 중간값으로 나누지 않고 뺀다는 것이 다르다. 파라메트릭 서치 유형으로 결정을 하는 방식으로 문제를 해결할 수 있다. 절단기의 최대 높이를 구하는 문제이지만 h 높이로 잘랐을 때 필요한 나무 길이가 나오는 지를 결정하는 문제로 바꾸어 해결할 수 있다. 나무를 자를..

개발 공부 (알고리즘) 2021. 2. 23. 03:29

www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 앞선 문제들은 기본적인 이분 탐색 코드를 어느 정도 외우고 있으면 풀 수 있는 간단한 문제들이었다. 1654번: 랜선자르기 문제부터는 파라메트릭 서치 (Parametric Search) 유형의 문제들이 나왔다. 파라메트릭 서치란 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다. 범위 내의 가장 큰 값, 작은 값을 찾는 문제들이 주로 이 유형에 해당하며, 보통 코딩테스트에서는 이러..

개발 공부 (알고리즘) 2021. 2. 23. 02:49

www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 두 가지 조건을 이용해 정렬하는 문제이다. 이전 문제들과 다른 점은 두 조건의 자료형이 다르다는 점이었다. 좌표 정렬 문제에서는 x와 y모두 정수로 주어졌고, 단어 정렬 문제에서는 문자열만 주어졌다. 이번 문제에서는 입력 받는 한 쌍이 (숫자, 문자열)로 이루어져 있다. 먼저 나이 순으로 정렬하는 조건을 위해서 sort()함수의 key 파라미터에 현재 리스트의 첫 번째 원소, 나이(숫자)를 전달한다. 만약에 나이가 ..

개발 공부 (알고리즘) 2021. 2. 2. 02:16

www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문자열들을 입력 받아 주어진 조건에 맞게 정렬하는 문제이다. 이전에 좌표를 정렬했던 문제들과 유사한 문제였다. 두 가지 조건이 주어지고 이에 따라 정렬하면 되는 문제였다. 이전과 마찬가지로 sort() 함수의 key 파라미터에 두 가지 조건을 전달했다. 첫 번째 조건은 문자열의 길이였다. len() 함수를 이용해서 현재 문자열의 길이를 전달했다. 만약 문자열의 길이가 동일한 원소들이 존재할 경우 두 ..

개발 공부 (알고리즘) 2021. 2. 2. 02:10

www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 이전의 두 개의 정렬 조건을 이용해서 풀었던 문제와 유사한 문제이다. 이 문제에서는 두 조건의 우선 순위를 바꾸었다. y를 기준으로 먼저 정렬하고 동일하다면 x를 기준으로 정렬한다. 입력은 x, y 순이기 때문에 정렬하는 sort()함수의 key 파라미터의 순서만 변경해주면 된다. 만약 파이썬이 아닌 다른 언어였다면 아마 생각할 점과 수정해야될 부분들이 ..

개발 공부 (알고리즘) 2021. 2. 2. 02:04

www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 정렬 기준에 관련된 문제였다. 우선 정렬 기준과 차선 정렬 기준을 적용해서 정렬하는 문제이다. 파이썬에서는 정말 간단하게 두 가지 조건을 sort()나 sorted()함수에 적용할 수 있다. sort()의 파라미터에는 key= 을 지정할 수 있다. key= 뒤에는 lambda를 이용해서 함수를 구현할 수 있다. 미리 선언해놓은 함수의 이름을 써도 되고 이름 ..

개발 공부 (알고리즘) 2021. 2. 2. 02:01