Problem Solving/[C++] Boj (59) 썸네일형 리스트형 [C++] 백준 1011: Fly me to the Alpha Centauri 문제 이해- 지구에서 특정 행성으로 공간 이동을 한다고 하자.- 이전에 k광년 이동 시, k-1 or k or k+1 광년만큼만 이동할 수 있다.- x에서 y까지 가는데 필요한 최소한의 공간 이동 장치 작동 횟수를 구하라.- 단, y 지점 도착하기 바로 직전에는 반드시 1광년만큼만 이동해야 한다. - 시간 제한: 2초- 메모리 제한: 512MB T: 테스트 케이스x: 현재 위치 (0 ~ 2^31-1)y: 목표 위치 (0 ~ 2^31-1) - 각 테스트 케이스에 대하여 x에서 y까지 정확히 도달하는데 필요한 최소한의 공간이동 횟수를 구하라. 문제 풀이뭔가 수열 문제 같기도 했고, 투포인터처럼 풀어볼까도 생각했던 문제이다. 결국 30분 시간제한을 넘겨 인터넷 풀이를 참고하였다. 총 2가지의 풀이를 참고하.. [C++] 백준 11729: 하노이 탑 이동 순서 문제 이해- 3개의 장대가 존재한다.- 첫 번째 장대에 n개의 원판이 내림차순으로 쌓여있다.- 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려고 한다.- 규칙1. 한 번에 1개의 원판만을 다른 탑으로 옮길 수 있다.2. 쌓아놓은 원판은 항상 위의 것이 아래 것보다 작아야 한다.- 필요한 이동 순서의 최솟값을 출력하라. - 시간 제한: 1초- 메모리 제한: 256MB - N: 첫 번째 장대에 쌓인 원판의 개수 (1 ~ 20) K: 옮긴 횟수A, B: 수행 과정, A번째 탑의 가장 위에 있는 원판을 B번째 탑의 가장 위로 옮긴다는 뜻 문제 풀이n의 범위가 20까지인걸로 보아 재귀 형태로 푸는 문제 같았다. 문제는 거기서 멈췄다는 것...구현을 도저히 생각해낼 수 없었다.스택을 3개 사용하는 문제인가 .. [C++] 백준 12865: 평범한 배낭 문제 이해- 배낭 문제- N개의 물건이 있으며, 각 물건은 무게 W와 가치 V를 가진다.- 준서가 들 수 있는 무게는 최대 K이다.- 배낭에 넣을 수 있는 가치합의 최댓값을 구하라. - 시간 제한: 2초- 메모리 제한: 512MB - N: 물품의 수 (1 ~ 100, 10^2)- K: 버틸 수 있는 무게 (1 ~ 100,000, 10^5)- W: 무게 (1 ~ 100,000, 10^5)- V: 가치 (0 ~ 1,000, 10^3) - 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력하라. 문제 풀이이 문제는 배낭 문제의 제일 기본 문제이다.꼭 숙지해서 비슷한 유형에 적용할 수 있도록 하자! 먼저 배낭 문제는 DP 문제이다.DP이니만큼 배열의 인덱스와 값을 잘 설정하는 게 중요할 것이다. 배낭 문.. [C++] 백준 4134: 다음 소수 문제 이해- 정수 n이 주어졌을 때 n이상인 소수를 출력하라. - 시간 제한: 1초- 메모리 제한: 128MB T: 테스트 케이스 개수n: 정수 (0 ~ 4 * 10^9) 각각의 테스트 케이스에 대하여 n 이상인 소수를 출력하라. 문제 풀이처음에는 소수 문제라서 에라토스테네스의 체를 생각했는데n의 최댓값이 4 * 10^9으로 메모리 제한에 걸릴거 같았다. 다음으로 생각한게 1부터 n까지 탐색하는 완전 탐색인데이 방법 역시 O(n)의 시간복잡도로는 시간초과일것 같았다. 결국 인터넷을 참고하여 풀었는데핵심은 바로 이것이다.어떠한 값에 대하여 소수를 판단할 때, 그 값의 약수들의 곱은 그 값의 제곱근을 기준으로 대칭이기 때문에 제곱근 이하의 값 까지만 검사를 하면 나머지는 검사를 할 필요가 없다 즉, s.. [C++] 백준 1629: 곱셈 문제 이해- 자연수 A를 B번 곱한 수를 구하려고 한다.- 단 매우 커질 수 있으므로 C로 나눠주도록 하자. - 시간 제한: 0.5초- 메모리 제한: 128MB - A: 곱하는 수- B: 곱하는 횟수- C: 나누는 수A, B, C 모두 (1 ~ 2,147,483,647) 사이의 정수로 int형으로 표현할 수 있다. - A를 B번 곱한 수를 C로 나눈 나머지를 출력하자. 문제 풀이처음에 가장 먼저 생각한건 역시 브루트포스다A를 그냥 B번 곱해주는 것이다. 그런데, B의 최댓값은 2,147,483,647로 대략 10^9를 넘는다.즉, O(N)의 시간복잡도를 가져도 시간 초과로 AC를 받을 수 없을 것이다. 도저히 시간 복잡도를 줄일 방법이 생각나지 않아서 인터넷을 참고했다. 이 문제를 푸는 방법은 '.. [C++] 백준 11286: 절댓값 힙 문제 이해- 절댓값 힙을 구현하려고 한다.- 두 가지 연산을 지원한다.1. 배열에 정수 x (x != 0)를 넣는다.2. 배열에서 절댓값이 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.※단, 절댓값이 가장 작은 값이 여러개일 때는, 가장 작은 수를 출력하고, 그 값을 배열에서 제거한다.- 프로그램은 비어있는 배열에서 시작한다. - 시간 제한: 1초- 메모리 제한: 256MB N: 연산의 개수 (1 ~ 100,000, 10^5)x: 연산에 대한 정보- 만약 0이 아니라면 배열에 x값을 넣는 연산 (정수는 int형 범위 안의 수이다)- 만약 0이라면 배열에서 절댓값이 가장 작은 값을 배열에서 제거하는 경우 - 입력에서 0이 주어진 횟수만큼 답을 출력한다.- 만약 배열이 비어 있는 경우에 0이 입력됐.. [C++] 백준 1459: 걷기 문제 이해- 학교에서 집까지 가려고 한다.- 도시의 크기는 무한대이다.- 도로는 수평으로 또는 수직으로 모두 존재한다. -> 수직선을 생각하자.- 세준이의 현재 위치는 (0,0)이다.- 세준이는 가로로 걷거나, 세로로 걷거나, 대각선으로 가로지를 수 있다.- 집까지 가는 최소시간을 구하라. - 시간 제한: 2초- 메모리 제한: 128MB - x, y: 집의 위치 (0 ~ 1,000,000,000, 10^9)- w: 1블록을 가는데 걸리는 시간 (1 ~ 10,000, 10^4)- s: 1블록을 가로지르는데 걸리는 시간 (1 ~ 10,000, 10^4) - 세준이가 집까지 가는데 걸리는 최소시간을 구하라. 문제 풀이시작은 경우의 수를 나눠서 풀어야겠다고 생각했다.세준이는 가로로 이동, 세로로 이동, 대각.. [C++] 백준 1931: 회의실 배정 문제 이해- 1개의 회의실에 N개의 회의를 배정할 계획이다.- 시작 시간과 끝나는 시간이 주어진다.- 회의 사용표를 만들 때, 겹치지 않으며 할 수 있는 회의의 개수의 최댓값을 구하라- 회의의 경우 끝나는 것과 동시에 다음 회의가 시작할 수 있다.- 또한, 회의의 시작 시간과 끝나는 시간이 같을 수도 있다. - 시간 제한: 2초- 메모리 제한: 128MB - N: 회의의 수 (1 ~ 100,000, 10^5)- N개의 줄에 걸쳐 각 회의의 시작 시간, 끝나는 시간 (0 ~ 2^31-1) - 사용할 수 있는 회의의 최대 개수를 구하라. 문제 풀이회의를 최대한 많이 사용해야 하므로그리디 알고리즘과 정렬을 사용해야겠다고 생각했다. 그렇다면 중요한 건 정렬을 '무엇'을 기준으로 '오름차순 혹은 내림차순' 할.. 이전 1 2 3 4 5 ··· 8 다음 목록 더보기
