C++ 코딩 문제 풀이/백준113 [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. [Baekjoon] 1932번: 정수 삼각형 https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 문제 해결 과정 착안 처음 착안에서 크기 $N$의 정수 삼각형을 구성하는 수들을 모두 입력받은 다음, 삼각형의 가장 아래 층부터 인접한 숫자끼리 비교하여 큰 숫자를 위 층의 숫자에 더하는 방식으로 구현하고자 하였다(동적계획법, dynamic programming). 문제를 해결한 뒤, 계산하고 난 다음에는 사용되지 않는 숫자 층들을 모두 저장하지 않고 메모리 공간을 절약해보고자, 숫자를 입력받는 순서대로 계산을 수행(위층에서부터 아래층으로 순차적 계산)하는 코드도 작성.. 2023. 6. 5. [Baekjoon] 1018번: 체스판 다시 칠하기 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 문제 해결 과정 착안 주어지는 $M \times N$ 크기의 보드 내에서 $8 \times 8$ 크기 단위의 격자를 이동해가며 체스판을 다시 칠하는 횟수를 모두 구해본 다음(브루트 포스(brute force) 알고리즘), 작은 값이 구해졌을 때마다 갱신하고자 하였다. 한편, 체스판을 다시 칠하는 과정에서 가장 위의 왼쪽 칸이 $B$인 경우 다시 칠하는 횟수를 $c_b$와 $W$인 경우 다시.. 2023. 6. 4. 이전 1 ··· 8 9 10 11 12 13 14 ··· 19 다음
