본문 바로가기

C++ 코딩 문제 풀이151

[Baekjoon] 1874번: 스택 수열 https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 해결 과정 착안 수열을 만들 수 있는지 확인하는 별다른 방법이 떠오르지는 않아, 문제에서 제시한 과정을 그대로 구현하여 문제를 해결하고자 하였다. 구체적으로는 아래와 같이 구현하고자 했다. 스택이 비어있거나 Top에 위치한 요소가 현재 수열의 항보다 작으면 push를 반복 (위 반복이 끝난 후) 스택의 Top에.. 2023. 6. 12.
[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] 2579번: 계단 오르기 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 문제 해결 과정 착안 정해진 규칙에 따라 계단을 오를 때 점수를 누적하므로 동적계획법(dynamic programming)을 이용하며, 규칙에 따라 식을 세우는 것에 의하여 문제를 해결하고자 하였다. 구현 문제에서 주어지는 규칙 중에서 연달아 3 개의 계단을 오를 수 없다는 규칙에 의해, $i$ 번째 계단($i \geq 3$)에 도착했을 때 누적 점수의 최댓값을 아래와 같이 구해야 한다(편의상 $i = 0$ .. 2023. 6. 9.
[Baekjoon] 1920번: 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 해결 과정 착안 반복적으로 탐색을 빠르게 수행하는 것이 문제에서 요구하는 핵심이므로, 아래와 같이 일반적으로 탐색 속도가 매우 빠른 것으로 알려져 있는 방법으로 각각 문제를 해결하고자 하였다. 해시(hash) 맵을 사용한 방법 이진 탐색(binary search, 이분 탐색)을 사용하는 방법 구현 [스포 주의] (해시 맵 사용) 아래 '더보기'.. 2023. 6. 9.
[Baekjoon] 7785번: 회사에 있는 사람 https://www.acmicpc.net/problem/7785 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net 문제 해결 과정 착안 많은 문자열에 대해, 입출력마다 요소를 보관할 컨테이너에 요소가 존재하는지 판단해야하기 때문에 해시(hash) 코드를 키로 가지는 std::map 클래스를 이용하고자 했다. 이때 주어지는 문자열의 길이가 5 이하이므로 매우 짧은 편에 속해, unsigned long long 자료형과 다항 롤링 해시(polynomial rolling ha.. 2023. 6. 7.

티스토리툴바