본문 바로가기

백준

 (22)
백준 1107 리모컨 - 브루트포스 - c++ https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 여러 번 주어지는 경우는 없다. www.acmicpc.net 우선 이 문제를 풀기 전 내 아이디어(브루트 포스 첫 문제다.) 고장난 리모컨 버튼들을 입력받아서, 0-9에서 뺀다. 그럼 잘 작동하는 리모컨 버튼만 입력을 받을 수 있을 것.(arr나 벡터에 저장하기.) 가장 큰 자리수부터 검사해서, 배열에 있는지 없는지 확인. 없으면 차이의 절댓값이 제일 작은 녀석을 골라서 다 밑의 자리..
백준 1992 - 쿼드트리 (분할정복) C++ https://www.acmicpc.net/problem/1992 1992번: 쿼드트리 첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다. www.acmicpc.net 언제 괄호를 출력해야 하는지 확실히 구분해야 한다. 분할정복이 이뤄지는 시점 시작과 끝에만 괄호를 집어 넣을 것. 그 부분 에만 괄호가 들어가야 하고, 그 이외의 시점에는 숫자만 출력하는 것을 확실히 해야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 2..
백준 1780 종이의 개수 - 분할정복 - C++ https://www.acmicpc.net/problem/1780 1780번: 종이의 개수 N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다. 이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으 www.acmicpc.net 전형적인 분할정복 알고리즘이다. n*n짜리 배열에서 같은 숫자가 나오면 패스고, 다른 숫자가 검출이 되면 n/3*n/3짜리 배열 9개..
백준 2110 공유기 설치 - 이분탐색 C++ https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다. www.acmicpc.net main 함수의 이분탐색 방식은 똑같고, 어떤 interval을 두고 공유기를 설치할수 있냐 없냐를 판단 하는 여부가 조금 까다로운 부분이지 않았나 싶었다. 13번째 줄에 current_x를 current_x+interval로 두지 않고 x[i]로 두어야 하는 부분을 조심하자. 어떤 인터벌을 두고 공유기를 n개 이상 설..
백준 1654 랜선자르기(이분탐색)-C++ https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net 오늘부터 이분탐색 문제를 풀기 시작했다. 이분탐색 알고리즘은 간단하다. 찾고자 하는 값을 정렬시킨다음에(여기서는 자르려는 길이이므로 정렬할 필요가 없음) 제일 큰값 제일 작은값의 중간을 탐색. 그것보다 크냐 작냐를 가지고 최댓값 또..
백준 1931 회의실 배정-greedy algorithm(C++) https://www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디 알고리즘의 전형적인 예시이다. 학교 알고리즘 시간에 거의 똑같은 문제를 다뤄봐서 쉽게 풀줄 알았는데, 막상 어려웠던 부분은 구현단계였다. 우선 문제를 풀기 위해서는 끝나는 시간에 주목해야한다. 1.끝나는 시간이 가장 빠른 녀석을 골라서, 2.그 끝나는 시간보다 시작시간이 빠른 녀석들을 골라 3.그 녀석들을 전부 지우고, 1~3의 과정을 반복하는 식이다. 시작시간과 끝시간을 배열로 넣어서 그걸 다시 벡터로 저장한 다음에, 벡터를 끝 시간을 기준으로 오름차순으로 정렬해야한다. (pair를 가진 벡터는, 정렬하고..

티스토리툴바