나그네

11966번: 2의 제곱인가? 문제 https://www.acmicpc.net/problem/11966 11966번: 2의 제곱인가? 자연수 N이 주어졌을 때, 2의 제곱수면 1을 아니면 0을 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 2의 제곱수면 log2를 씌웠을 때 정수가 나올 것이다. 따라서 log2(n)이 정수이면 1, 아니면 0을 출력하면 된다. log2의 return 값은 double 형태이다. 원래 수에서 int로 형변환한 값을 뺀 값이 0이면 log2(n)은 정수이다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; cout

16507번: 어두운 건 무서워 문제 https://www.acmicpc.net/problem/16507 16507번: 어두운 건 무서워 첫 번째 줄에는 사진의 크기를 의미하는 정수 R, C (1 ≤ R, C ≤ 1,000)와 사진 일부분의 밝기 평균을 알아볼 개수를 의미하는 정수 Q (1 ≤ Q ≤ 10,000)가 주어진다. 다음 R개의 줄에 걸쳐 R×C 크기의 사 www.acmicpc.net 풀이 [백준 / BOJ] C++ 11660 구간 합 구하기 5와 같은 문제다. [백준 / BOJ] C++ 11660 구간 합 구하기 5 11660번: 구간 합 구하기 5 문제 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해..

28014번: 첨탑 밀어서 부수기 문제 https://www.acmicpc.net/problem/28014 28014번: 첨탑 밀어서 부수기 첫째 줄에 첨탑의 개수 $N$이 주어진다. $(1\leq N\leq 5\,000\,000)$ 둘째 줄에는 앞에서부터 차례대로 첨탑의 높이 $H_1, H_2, \cdots, H_n (1\leq H_i\leq 1\,000\,000)$ 이 주어진다. 입력으로 주어지는 모든 수는 정 www.acmicpc.net 풀이 밀려 넘어지는 첨탑의 높이가 바로 그다음 첨탑의 높이보다 클 때만 그다음 첨탑도 밀려 넘어진다는 것은 밀려 넘어지는 첨탑의 높이가 바로 그다음 첨탑의 높이보다 작거나 같을 때 다음 첨탑을 밀어야 한다. 즉, i번째 첨탑과 i+1번째 첨탑의 높이를 비교해 i+1..

2583번: 영역 구하기 문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 풀이 모눈종이 위의 몇 가지 직사각형을 제외한 공간의 수와 각각의 넓이를 오름차순으로 출력하는 문제다. 먼저 2차원 배열을 만들고 직사각형을 채워야 하는데 입력은 모눈종이의 좌표로 입력되는 반면 배열의 인덱스와 맞추기 위해서 2중 for문을 사용해 (x1, y1)부터 (x2, y2)까지 -1로 색칠을 해준다. 배열이 -1이 아닌 공간에 대해 bfs..

19568번: 직사각형 문제 https://www.acmicpc.net/problem/19568 19568번: 직사각형 당신이 만든 표에 적힌 수를 한 줄에 30개씩, 30줄로 출력하여라. 정확한 형식은 예제 출력을 참고하자. www.acmicpc.net 풀이 2차원 약 팔기다. 아직 약 팔기 문제를 풀지 않았다면 아래 문제를 풀어보고 오는 것을 추천한다. [15311 약 팔기 문제] [15311 약 팔기 풀이] 힌트 더보기 약 팔기 문제처럼 진수를 이용한다. 풀이 더보기 30×30 배열을 사용하므로 중간인 15를 기준으로 삼아 15진수를 사용한다. 중심을 기준으로 좌우로 1, 15를 채우고 상하로 15^2, 15^3을 채운다. 나머지 칸은 모두 0으로 채우면 50000을 조금 상회하는 수까지 나타낼 수..

11441번: 합 구하기 문제 https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 풀이 최대 10만 개의 연속된 수의 합을 구해야 한다. 따라서 입력과 동시에 모든 구간 합을 구할 수 있도록 구현이 가능한 누적 합 배열을 만들어 해결할 수 있다. 누적 합 알고리즘은 수열의 합 Sn에 대해 Sn - Sm-1 이 Am ~ An까지의 합과 같음을 이용하는 알고리즘이다. 코드 #inc..

27972번: 악보는 거들 뿐 문제 https://www.acmicpc.net/problem/27972 27972번: 악보는 거들 뿐 키위새는 피아노를 잘 치고 싶었지만 악보를 볼 줄 몰랐다. 그러다 동영상 사이트에서 수열만 보고 피아노를 연주하는 동영상을 찾아냈다! 하지만 동영상에서 보여주는 수에 맞는 음을 누르자 www.acmicpc.net 풀이 음의 높낮이가 변하면 수를 1씩 늘리고 줄이기만 하므로 가장 긴 연속된 증가/감소하는 부분 수열의 길이가 정답이 된다. 연속이 끊길 때 길이 초기화를 1로 해야 함에 주의하자. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int m, a = 1, b = 1..

27970번: OX 문제 https://www.acmicpc.net/problem/27970 27970번: OX O와 X로 이루어진 문자열이 주어진다. 모든 문자를 X로 만들 때까지 다음 연산을 반복할 때, 시행하는 연산의 횟수를 구하시오. 문자열의 가장 왼쪽에 있는 O를 X로 바꾸고, 그보다 왼쪽에 있는 X www.acmicpc.net 풀이 i번째 인덱스에 O가 있으면 이 O를 X로 바꾸기 위해서는 2^i번 연산을 수행해야 한다. O가 있는 인덱스 i에 대해 2^i의 합을 출력하면 된다. int 범위를 벗어날 수 있으므로 long long을 쓰고 모듈러 연산을 계속 해줘야 한다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(0)..

15311번: 약 팔기 문제 https://www.acmicpc.net/problem/15311 15311번: 약 팔기 첫 번째 줄에 동규의 최대 약 요구량을 나타내는 정수 N ($=1\, 000\, 000$) 이 주어진다. www.acmicpc.net 풀이 친구의 추천으로 며칠간 고민하다가 갑자기 풀이가 떠올랐다. 1부터 1,000,000까지 모두 나타낼 수 있어야 하는데, 1,000,000 = 1,000 * 1,000이고 배열의 최대 크기 2,000 = 2 * 1,000이다. 그래서 1000을 1000개 넣고 나머지 1000칸에 모두 1을 넣으면 1부터 1,000,000까지 만들 수 있다. 코드 #include using namespace std; int main() { ios::sync_with_s..

27969번: I LOVE JavaScript 문제 https://www.acmicpc.net/problem/27969 27969번: I LOVE JavaScript 한 줄에 걸쳐, ASON 객체의 유효한 표기가 주어진다. 주어지는 문자열의 길이는 스페이스 문자를 제외하고 $15\,000$ 이하이다. www.acmicpc.net 풀이 ASON을 구성하는 것은 [, ], 문자열, 정수가 있고 각각 공백으로 구분되어 있으므로 각각을 토큰화하기 위해 while문 조건 안에 cin을 넣어 EOF가 발생할 때까지 공백을 기준으로 문자열을 입력받는다. 스택을 사용해 객체의 시작을 의미하는 [가 입력되면 0을 push한다.push 한다. 마찬가지로 정수가 입력되면 8을, 문자열이 들어오면 길이+12를 push 한다...