본문 바로가기

Algorithm

 (130)
[C++] 백준 1927번 : 최소 힙 (S1) &11279번 : 최대 힙 (S2) #문제 www.acmicpc.net/problem/1927 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net www.acmicpc.net/problem/11279 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이� www.acmicpc.net #풀이 Min/Max heap을 구현해야 하는 문제들이다. 힙은 배열을 ..
[C++] 백준 2798번 : 거꾸로 구구단 (B2) #문제https://www.acmicpc.net/problem/1341013410번: 거꾸로 구구단일반적인 구구단에서 가장 큰 수는 마지막 항의 값이 제일 크다. 거꾸로 구구단에서는, 각 항에 구구단의 계산 결과로 나온 값을 뒤집어 저장을 한다. 이렇게 하면 가장 큰 값이 항상 마지막이 ��www.acmicpc.net#풀이처음에 풀이 방향을 잘못 잡아 매우 고생했던 문제이다. 문제 의도가 수를 직접 직접 뒤집어 대소비교를 하는 게 아니라, 수는 가만히 내버려 둔 상태에서 거꾸로 읽으며 대소 비교를 하게 하는 것이라고 생각했기 때문이다. 물론 이 방법으로도 문제를 해결할 수 있겠지만, 고려해야 할 점이 너무 많았다. 특히 자리에 0이 들어가 있는 경우에 대소비교 처리가 매우 힘들었다.이번 문제를 통해 수를..
[C++] 백준 4641번 : Doubles (B1) #문제 https://www.acmicpc.net/problem/4641 4641번: Doubles 문제 2~15개의 서로 다른 자연수로 이루어진 리스트가 있을 때, 이들 중 리스트 안에 자신의 정확히 2배인 수가 있는 수의 개수를 구하여라. 예를 들어, 리스트가 "1 4 3 2 9 7 18 22"라면 2가 1의 2배, 4� www.acmicpc.net #풀이 이러한 유형의 문제가 처음 이해가 잘 되지 않았다. 그 이유는 이와 같은 입출력 예시를 보고 왼쪽의 숫자들의 입력이 모두 끝나면 오른쪽과 같이 출력이 돼야 한다고 생각했기 때문이다. 하지만 "각 테스트 케이스마다 한 줄에 걸쳐 정답을 출력한다."라는 의미는 다음과 같았다. 테스트 케이스를 입력할 때마다 정답이 출력되는 형태인 것이다. 이와 비슷한 ..
[C++] 백준 1065번 : 한수 (S4) #문제 https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 �� www.acmicpc.net #풀이 문제에서 N이 1000 이하의 자연수라고 하였으므로 경우를 그냥 나누어 문제를 풀 수 있다. 우선 1부터 99까지는 모두 한수이고, 1000은 한수가 아니다. 따라서 우리는 세 자릿수가 한수인지 판단하기만 하면 문제가 해결된다. 이는 각 자릿수를 살펴보는 법을 이용하면 된다.(10으로 나눈 나머지를 구하고 10으로 나눈다) 만약 N이 매우 큰 수로 주어진다면 이러한 방법을 이용할 ..
[C++] 백준 7568번 : 덩치 (S5) #문제 https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩� www.acmicpc.net #풀이 따로 등수를 저장할 배열을 선언해야겠다는 생각을 하는 것이 중요한 문제다. 그리고 각 사람에 대해 그 사람을 제외한 모든 사람과 비교를 해야 하는데, 이는 2중 for문을 이용한다. 본인이 본인과 비교를 하는 경우는 부등호에 등호를 제외시킴으로써 간단하게 제외시킬 수 있다. 그리고 항상 개수를 세는 변수는 for문 앞에서 0으로 초기화해주는 것 잊지 말자. #소스코드 1..
[C++] 백준 2858번 : 기숙사 바닥 (B2) #문제 https://www.acmicpc.net/problem/2858 2858번: 기숙사 바닥 문제 상근이는 기숙사 생활을 한다. 상근이의 방의 크기는 L*W 이다. 수업시간에 타일 채우기 경우의 수를 계산하던 상근이는 자신의 방도 1*1크기 타일로 채우려고 한다. 이때, 가장자리는 빨간�� www.acmicpc.net #풀이 문제를 읽고 문제에서 주어진 조건들을 수식으로 표현해서 적고 살펴보는 것이 중요하다. 그리고 주어진 수식들을 조합하여 얻을 수 있는 식들을 먼저 정리한다. 그리고 코드를 어떻게 구성할지 생각해본다. 이 문제의 경우, 두 가지 수식 WL-(W-2)(L-2)=R, (W-2)(L-2)=B을 통해 WL=B+R, W+L=2+R/2를 얻을 수 있었다. 정답이 유일한 경우만 주어진다고 했으..
[C++] 백준 1436번 : 영화감독 숌 (S5) #문제 https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net #풀이 우선 특별한 풀이법을 생각하기보단 1부터 모든 수를 순서대로 살펴보면 되겠다고 생각하는 것이 중요하다. 그리고 처음 풀이에서 실수했던 것은 6이 3개 이상 존재해야 한다는 점에만 주목해서 연속으로 나타나야 한다는 점을 고려하지 못했다. 그래서 코드를 수정했는데, 이때는 6이 연속으로 3개 존재한다는 것이 확인만 되면 반복문을 탈출하도록 짰다. 연속으로 6이 3개 이상이기만 하면 되..
[C++] 백준 1018번 : 체스판 다시 칠하기 (S5) #문제 https://www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net #풀이 직사각형에 정사각형을 덧대어 두 사각형의 같은 곳과 다른 곳을 어떻게 check할 것인지에 대해 고민해 봐야 한다. 이 문제는 정사각형이 체스판의 형태로 그 무늬가 규칙적이기 때문에 특별한 방법을 생각해 볼 수 있다. 가로의 인덱스와 세로의 인덱스의 합으로 색을 파악할 수 있다는 점에 주목해보자. 또, 이 문제에서 학습할 중요한 점은 2가지 경우 중 1가지 경우를 구하면, 다..

티스토리툴바