본문 바로가기

C++ 코딩 문제 풀이151

[Programmers] 숫자의 표현 https://school.programmers.co.kr/learn/courses/30/lessons/12924 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 자연수 $N$이 2 개 이상의 연속된 자연수들로 표현이 가능한지 확인하기 위해 1부터 최대 $N/2$ 이하의 자연수까지 반복하며 연속된 숫자의 합을 구해 $N$과 비교함으로써 표현 가능한 수를 구한 다음, 1을 더한 값($N = N$ 으로도 표현이 가능하므로)을 문제의 답안으로 사용하고자 하였다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 .. 2023. 8. 15.
[Baekjoon] 17179번: 케이크 자르기 https://www.acmicpc.net/problem/17179 17179번: 케이크 자르기 첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는 www.acmicpc.net 문제 해결 과정 착안 자르고자 하는 케이크 조각 수를 만족하기 위해 자연수 1부터 $L$까지의 길이 중 가능한 길이의 최댓값을 이진 탐색(binary search, 이분 탐색)을 응용하여 구한다. 구현 편의상 시작 탐색 구간의 우측 끝값을 불가능한 길이인 $L+1$로 설정하여 탐색을 시작하고 아래 코드와 같이 탐색 알고리즘을 구현하였다. [스포 주의].. 2023. 8. 14.
[Baekjoon] 16493번: 최대 페이지 수 https://www.acmicpc.net/problem/16493 16493번: 최대 페이지 수 첫째 줄에 N(1 ≤ N ≤ 200)과 챕터의 수 M(1 ≤ M ≤ 20)이 주어진다. 둘째 줄부터 각 챕터 당 읽는데 소요되는 일 수와 페이지 수가 주어진다. 소요되는 일 수는 20보다 작거나 같은 자연수이고, 페이 www.acmicpc.net 문제 해결 과정 착안 이전 포스트에서와 동일한 원리로, 동적계획법(dynamic programming)에 기반하여 문제를 해결하였다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include #include using namespace std; struct Chapter { int Days; int Pages; }; Chapte.. 2023. 8. 8.
[Baekjoon] 12865번: 평범한 배낭 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 문제 해결 과정 착안 배낭에 넣고자 하는 물건의 무게의 총합이 $k \space (1 \leq k \leq K)$일 때, 같은 무게로 만들 수 있는 가치의 총합 중 가장 큰 값을 배열에 저장하기 위해 동적계획법을 사용하여 문제를 해결하고자 하였다. $i$번째 물건의 무게를 $w_i$, 가치를 $v_i$라고 하면, $1, 2,\cdo.. 2023. 8. 1.
[Baekjoon] 1629번: 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 문제 해결 과정 착안 단순하게 반복적으로 같은 수를 곱하며 거듭제곱을 계산하면 지수 $E$에 대해 $O(E)$의 시간 복잡도를 소요하므로, 재귀를 활용하여 지수를 절반씩 줄여나가 $O(\log E)$의 시간 복잡도로 계산하고자 하였다. 한편, 나머지 연산(modulo operation)의 특성에 따라 다음과 같은 성질들이 성립함을 이용하였다. 자연수 $A, B, C$에 대하여 $A$를 $C$로 나눈 나머지를 $a \space (0 \leq a < C)$ 라고 할.. 2023. 7. 31.
[Programmers] 이진 변환 반복하기 https://school.programmers.co.kr/learn/courses/30/lessons/70129 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 문제에서 요구한 것과 같이, 주어진 문자열에서 0을 제거하면서 횟수를 계산하고 0을 제외한 나머지 문자열의 길이를 이진법으로 변환하는 과정을 반복하면서 변환 횟수를 계산한다. 구현 십진법의 숫자를 이진법으로 변환하는 과정은 비트 연산을 활용하여 구현하였다. [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include #include using na.. 2023. 7. 30.

티스토리툴바