분류 전체보기166 [Baekjoon] 11660번: 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 해결 과정 착안 이차원 배열 내에서 $x_1$행 $y_1$열을 좌상단, $x_2$행 $y_2$열을 우하단($x_2 \geq x_1, \space y_2 \geq y_1$)으로 하는 사각형 내의 숫자들의 누적 합을 계산하기 위해, 주어진 이차원 배열과 크기가 같은 배열을 선언하여 동적계획법(dynamic programming)에 활용한다. 이때, 메모.. 2023. 8. 24. [Baekjoon] 14502번: 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 해결 과정 착안 주어지는 연구소 모양에 대하여 백트래킹(backtracking, 퇴각검색) 알고리즘을 통해 빈 공간에 벽 3개를 세우면서, 바이러스 확산 예상 결과를 너비 우선 탐색(breadth-first search, BFS)을 통해 구하고자 하였다. 구현 편의상 벽의 개수를 파악하기 쉽도록 세우고자 하는 벽의 번호를 3, 4, 5로 정하여 프로그래밍 하였다. 한편 백트래킹 알고리즘에 기반하여 너비 .. 2023. 8. 15. [Programmers] 다음 큰 숫자 https://school.programmers.co.kr/learn/courses/30/lessons/12911 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 비트 연산을 활용하여 아래의 과정을 통해 규칙에 따라 주어지는 수 $N$의 다음 숫자를 구하고자 하였다. $N$을 이진법으로 표현하였을 때, 가장 오른쪽에서부터 시작하여 왼쪽 방향으로 '01' 비트가 처음 등장하는 부분을 찾는다(아래 코드의 while문). 해당 '01' 비트를 10으로 바꾼다(아래 코드의 while문 다음의 코드 두 줄에 해당). 해당 '01' 비트보다 오른.. 2023. 8. 15. [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. 이전 1 ··· 6 7 8 9 10 11 12 ··· 28 다음
