이항 조건(binary predicate)6 [Baekjoon] 20920번: 영단어 암기는 괴로워 https://www.acmicpc.net/problem/20920 20920번: 영단어 암기는 괴로워 첫째 줄에는 영어 지문에 나오는 단어의 개수 $N$과 외울 단어의 길이 기준이 되는 $M$이 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\,000$, $1 \leq M \leq 10$) 둘째 줄부터 $N+1$번째 줄까지 외울 단 www.acmicpc.net 문제 해결 과정 착안 문자열을 키로 가지며, 등장하는 빈도 수를 값으로 저장하여 문제를 해결하고자 std::map과 같은 컨테이너를 활용하고자 하였다. 이때 키의 자료형이 문자열 형이므로 해시 테이블(hash table)을 사용하는 것이 일반적으로 속도 측면에서 유리하기 때문에 std::unordered_map 클래스를 사용해 데.. 2023. 7. 9. [Baekjoon] 10814번: 나이순 정렬 https://www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 문제 해결 과정 착안 가입한 사람들의 정보를 구조체를 활용해 저장한 뒤 이를 배열로 저장하여 정렬하고자 하였다. 나이가 같은 경우, 가입한 순으로 정렬하기 위해 별도로 가입한 순서를 표시하기 위한 변수를 구조체에 포함하였다. 구현 STL의 헤더에 포함된 std::sort() 함수를 사용하고, 정렬하는 기준을 람다 표현식(lambda expression)의 형태로 전달하여 구현하였다. [스포 주의] 아래.. 2023. 6. 25. [Baekjoon] 1931번: 회의실 배정 https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 해결 과정 착안 문제를 처음 접하고 어떻게 해결할 지 막연해서 꽤 오래 고민을 했다. 최대한 많은 회의에 대해 회의실을 배정하려면 어떻게 해야할지 열심히 생각해보다가, 아래와 같은 조건들이 문제 해결의 핵심이라고 생각을 했다. 처음 생각한 조건 회의 시간이 짧은 회의들을 가능한 한 많이 배정한다. 회의실이 비는 시간을 최소로 한다(단, 회의실 배정 가능한 시간에 대해 별도의 제약이 없음에 유의) 위의 조건을 만족하면서 회의를 순차적으로 배정하다보면 결과적으로 최대한 많은 회의에 대해 회의실을 배정할 수 있을.. 2023. 6. 21. [Baekjoon] 1181번: 단어 정렬 https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 해결 과정 착안 정렬에 사용할 비교 연산자를 람다 표현식(lambda expression)을 활용한 이항 조건(binary predicate)으로 정의하여 문제를 해결하고자 하였다. 구현 편의상 STL의 헤더에 포함되어있는 std::sort() 함수를 사용하여 정렬하되, 람다 표현식을 활용해 이항 조건을 정의한 다음 함수에 전달하여 문제를 해결하였다. * 어제 포스팅했던 문제와 동.. 2023. 6. 11. [Baekjoon] 11650번: 좌표 정렬하기 https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net 문제 해결 과정 착안 정렬에 사용할 비교 연산자를 정의하여 정렬 알고리즘을 작성함으로써 문제를 해결하고자 하였다. 비교 연산자를 정의하는 방법은 연산자 오버로딩(operator overloading) 또는 비교 연산 함수 포인터를 사용하는 방법이 있는데, 이 포스팅에서는 함수 포인터를 사용하는 여러 방법 중 람다 표현식(lambda expres.. 2023. 6. 11. [Baekjoon] 16236번: 아기 상어 https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 문제 해결 과정 착안 문제에서 아기 상어가 물고기를 먹기 위해 이동하는 최소 경로가 크기에 따라 달라지는 상황에서, 아기 상어가 먹이를 찾아 탐색하는 과정을 구현하는 문제이다. 문제를 처음 접했을 때, 아기 상어의 1 초당 이동 반경을 중심으로 전방향으로 탐색을 하는 방법을 생각해보았다. 즉, 너비 우선 탐색(breadth-first search, BFS)의 원리에 기반하여 주어진 공간 내.. 2023. 5. 30. 이전 1 다음
