분류 전체보기 (115) 썸네일형 리스트형 [C++] 백준 1074: Z 문제 이해- 크기가 2^N * 2^N인 2차원 배열- Z모양으로 탐색하고자 한다.- N > 1인 경우, 배열을 크기가 2^(N-1) * 2^(N-1)로 4등분 한 후에 재귀적으로 순서대로 방문한다.- N이 주어졌을 때, r행 c열을 몇 번째로 방문하는지 출력하라. - 시간 제한: 0.5초- 메모리 제한: 512MB - N: 배열의 크기 관련 정수 (1 ~ 15)- r, c: 몇 번째로 방문하는지 찾아야하는 좌표 (0 ~ 2^N-1) - (r, c)를 몇 번째로 방문했는지 출력하라. 문제 풀이4등분을 한다는 것에 분할정복 문제라는 것을 체크했다. 처음에는 단순히 4사분면으로 나누어 분할정복하여 각 방문마다 +1씩 해주었다.하지만, 이 풀이는 시간 초과였다. 결국 인터넷 풀이를 참고하여 문제를 풀었.. [C++] 백준 1167: 트리의 지름 문제 이해- 트리의 지름: 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것- 트리의 지름을 구하라 - 시간 제한: 2초- 메모리 제한: 256MB - V: 정점의 개수 (2 ~ 100,000, 10^5)- V개의 줄에 걸쳐 간선의 정보(시작 정점, 종료 정점, 정점까지의 거리)※ 거리 (1 ~ 10,000, 10^4)※ 각 줄의 마지막에는 -1이 입력으로 들어온다. - 트리의 지름을 출력하라. 문제 풀이이 문제는 트리의 지름과 관련된 정보를 알아야 풀 수 있다.임의의 정점에서 거리가 가장 먼 정점은 지름을 구성하는 한 정점이다.또한 지름을 구성하는 정점에서 거리가 가장 먼 정점또한 지름을 구성하는 정점이다. 위 정보만 알고 있다면 다들 쉽게 푸실거라 생각한다. 주의할 점1. 인접 그래프에 입력값을.. [C++] 백준 1068: 트리 문제 이해- 리프 노드: 자식의 개수가 0인 노드- 트리가 주어졌을 때, 노드 1개를 지울 것이다.- 남은 트리에서 리프 노드의 개수를 구하라.※ 단, 노드를 지울경우 그 노드와 노드의 모든 자손이 트리에서 제거된다. - 시간 제한: 2초- 메모리 제한: 128MB - N: 트리의 노드의 개수 (1 ~ 50)- 각 노드의 부모※ 부모가 없을경우, -1이 주어진다.- 지울 노드의 번호 - 노드를 지운 후 리프 노드의 개수 문제 풀이이 문제의 핵심은 그래프의 방향성에 있다고 생각한다. 보통의 트리 문제는트리도 결국 그래프의 일종이니만큼 정점을 인접 그래프로 표현할 때,양방향으로 집어넣는다. 하지만, 이 문제의 경우 리프 노드, 즉 제일 아래의 노드가 우리의 관심사이고위로 올라갈 필요는 전혀 없다.아니,.. [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를 받을 수 없을 것이다. 도저히 시간 복잡도를 줄일 방법이 생각나지 않아서 인터넷을 참고했다. 이 문제를 푸는 방법은 '.. 이전 1 2 3 4 5 6 7 ··· 15 다음 목록 더보기
