본문 바로가기

Problem Solving/[C++] Boj

(59)
[C++] 백준 12904: A와 B 문제 이해- 두 문자열 S와 T가 주어졌을 때, S를 T로 바꾸는 게 가능한지 알아내는 프로그램- 연산은 총 두 가지이다.1. 문자열의 뒤에 A 추가2. 문자열을 뒤집고, 뒤에 B 추가 - S (길이: 1 ~ 999)- T (길이: 2 ~ 1,000) - S를 T로 바꿀 수 있다면 1, 없다면 0을 출력하라.    문제 풀이처음에는 역시나 완전 탐색으로 접근해봤다.백트래킹을 통해 구현했는데, 역시나 시간초과였다.  이 문제의 정해는 바로 그리디이다.핵심은 역으로 과정을 진행하는 것이다.   즉 S -> T가 아니라 T -> S를 구하는 것.이것만 안다면 쉽게 문제를 풀 수 있을 것이다.    전체 코드#include #include #include using namespace std;int main() ..
[C++] 백준 7579: 앱 문제 이해- 현재 N개의 앱, A1, ..., An이 활성화 되어있다.- 이들 앱은 각각 mi바이트만큼 메모리를 사용한다.- 각 앱을 다시 실행하고자 할 때 ci의 비용이 들어간다.- N개의 앱 중 몇 개를 비활성화 하여 M 바이트 이상의 메모리를 확보하고자 할 때, 비용 ci의 합을 최소화하는 방법을 구하라. - 시간 제한: 1초- 메모리 제한: 128MB - N: 활성화된 앱의 개수 (1 ~ 100, 10^2)- M: 필요한 메모리의 크기 (1 ~ 10,000,000, 10^7)- mi: Ai가 사용중인 메모리의 바이트 크기 (1 ~ 10,000,000, 10^7)- ci: Ai를 비활성화 했을 때 비용 (0 ~ 100, 10^2)※ M  - 필요한 메모리 M 바이트를 확보하기 위한 앱 비활성화의 최..
[C++] 백준 1717: 집합의 표현 문제 이해- 초기에 n+1개의 집합이 있다.- {0}, {1}, ..., {n}- 합집합 연산과 두 집합이 같은 집합에 포함되어 있는지 확인하는 연산이 존재한다.- 집합을 표현하는 프로그램을 작성하라.  - 시간 제한: 2초- 메모리 제한: 128MB - n: 집합의 개수 관련 변수 (1 ~ 1,000,000, 10^6)- m: 연산의 개수 (1 ~ 100,000, 10^5)- 연산: 합집합(0 a b), 같은 집합에 포함되어 있는지 확인(1 a b) - 1로 시작하는 입력에 대해서 a와 b가 같은 집합에 포함되어 있으면 yes, 있지않으면 no를 출력하라.   문제 풀이두 원소가 같은 집합에 속하는지 아닌지를 판단하는 유니온 파인드의 기본 문제이다.  유니온 파인드 알고리즘은 같은 집합에 속하는 원소들..
[C++] 백준 1107: 리모컨 문제 이해- 리모컨 버튼은 숫자 0~9, +, -가 존재한다.- +버튼을 누르면 현재 채널에서 +1된 채널로 이동한다.- -버튼을 누르면 현재 채널에서 -1된 채널로 이동한다.※단, 현재 채널이 0일때 -를 누를경우 변화는 없다.- 채널은 무한대이며, N번으로 이동하고자 한다.- N번으로 이동할 때 버튼을 누르는 횟수의 최솟값을 구하라.- 현재 채널은 100이다. - 시간 제한: 2초- 메모리 제한: 256MB - N: 이동하려는 채널(0 ~ 500,000, 10^5)- M: 고장난 버튼의 개수 (0 ~ 10) - N번으로 이동하기 위해 눌러야하는 버튼의 최솟값을 구하라.   문제 풀이처음엔 수학적으로 접근해서 이것저것 경우의 수를 생각해봤는데 고려해야할 게 너무 많았다.  결국 인터넷 풀이를 참고하였는..
[C++] 백준 5052: 전화번호 목록 문제 이해- 전화번호 목록이 주어진다.- 전화목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없어야 한다.- 전화번호 목록이 일관성이 있는지 없는지 구하라. - 시간 제한: 1초- 메모리 제한: 256MB t: 테스트 케이스 개수 (1 ~ 50, 10^1)n: 전화번호 수 (1 ~ 10,000, 10^4) 각 테스트 케이스에 대하여, 일관성이 있다면 YES, 없다면 NO를 출력하라.  문제 풀이전화 번호 수의 최댓값이 10,000이고, 테스트 케이스가 최대 50개까지 가능하므로한 케이스가 O(n^2)의 복잡도를 가질경우 시간초과가 날 수밖에 없다.  그러므로, 브루트포스로는 풀 수 없었다.  이 문제를 푸는 핵심은 바로 string 배열의 정렬에 있었다.  stl 라이브러리에 있는 s..
[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이 주어진다.- 지울 노드의 번호 - 노드를 지운 후 리프 노드의 개수  문제 풀이이 문제의 핵심은 그래프의 방향성에 있다고 생각한다.  보통의 트리 문제는트리도 결국 그래프의 일종이니만큼 정점을 인접 그래프로 표현할 때,양방향으로 집어넣는다.  하지만, 이 문제의 경우 리프 노드, 즉 제일 아래의 노드가 우리의 관심사이고위로 올라갈 필요는 전혀 없다.아니,..