본문 바로가기

분류 전체보기166

[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.
[Programmers] 최솟값 만들기 https://school.programmers.co.kr/learn/courses/30/lessons/12941 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 길이가 같은 배열에서 각각 하나씩 숫자를 뽑아 곱한 값을 누적하여 더할 때, 누적된 값이 가장 작도록 하기 위해서는 두 배열 중 하나는 오름차순으로, 하나는 내림차순으로 정렬하여 인덱스 순서대로 곱한다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include #include #include using namespace std; int s.. 2023. 7. 30.
[Baekjoon] 13305번: 주유소 https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 해결 과정 착안 아래와 같이 탐욕(greedy) 알고리즘에 기반하여 문제를 해결할 수 있다. 현재 위치해 있는 도시의 주유 비용을 기준으로 삼는다. 순차적으로 우측 도시를 탐색하며 현재 도시의 주유 비용보다 주유 비용이 더 저렴한 도시를 탐색한다. 탐색에 성공하면, 현재 도시에서 주유하여 해당 도시까지 한 번에 이동한다. 탐색에 실패하면, 현재 도시에서 마지막 도시까지 한 번에.. 2023. 7. 28.
[Programmers] JadenCase 문자열 만들기 https://school.programmers.co.kr/learn/courses/30/lessons/12951 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 공백을 기준으로 단어를 나눈 다음, 단어의 첫 글자를 대문자, 나머지 글자를 소문자로 변환한 결과 문자열을 누적하여 연결(concatenation)함으로써 문제를 해결하고자 하였다. 공백의 경우에는 별도의 처리 없이 문자열을 연결하고자 하였다. 구현 주어진 문자열 내의 단어들을 공백을 기준으로 구분하여 부분문자열(substring)을 구하기 위해 헤더에 포함된 find_fir.. 2023. 7. 28.

티스토리툴바