개발의 꿈을 개발하는 꿈을 개발하려는 꿈

목차 개요 12100번: 2048 (Easy) (acmicpc.net) 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 2048이라는 퍼즐 게임을 재현하는 문제이다. 다만 우리가 구하는 것은 5턴이 주어졌을 때 우리가 해낼 수 있는 최대한의 큰 수를 출력하는 것. 자세한 규칙은 문제를 알아서 읽어보는 것이 좋다. 간단하게만 보자면, 1. 한 턴에 상하좌우 중 하나를 선택할 수 있고 그쪽 방향으로 모든 블럭이 쏠린다. 2. 쏠릴 때 같은 숫자의 블럭 2개가 부딪히게 되면 합체가 일어나..

목차 개요 1918번: 후위 표기식 (acmicpc.net) 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 우리가 흔히 쓰는 식 표기법은 중위 표현식. 이것을 후위 표기식으로 바꾼 결과를 출력해야 한다. 괄호도 들어온다는 것에 주의해야 한다. 풀이 발상이 잘 안 돼서 혼자 힘으로 푸는 것은 실패.. 후위 표기식의 장점은 괄호가 필요 없다는 것. 이 말인 즉슨, 기호가 쓰인 위치에 따라 쉽게 계산 순서를 명시할 수 있다는 것이다. 보기는 어려울지 모르지만, 괄호 없이 온전히 원하는 연산을 해낼 수 있다. ..

목차 개요 26035번: $0101$ (acmicpc.net) 26035번: $0101$ $N\times M$ 크기의 배열의 각 칸에 $0$과 $1$중 하나를 적는다. 이때, 모든 $2\times 2$ 크기의 부분 배열 안에 적힌 수의 합이 $2$로 같아지도록 배열을 채우는 방법의 수를 구하여라. www.acmicpc.net 문제 설명은 간단하다. 풀이 입력 제한이 $10^{18}$이다. 이는 $10^9 \times 10^9$니까, 억에 억을 곱한 자릿수가 들어온다는 것이다;; n의 시간복잡도를 가진 알고리즘을 짜게 된다고 해도 문제를 풀 수 없다는 뜻이다. 출력은 나머지를 출력하라고 한다. 이렇게 나머지를 출력하라고 하는 경우는 보통 값이 너무 커서 나머지로만 출력을 하라는 건데, 그것도 해당 값을 모..

목차 개요 1662번: 압축 (acmicpc.net) 1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 문제를 잘 읽어야 한다. 압축된 문자열인 상태일 때 압축하지 않은 상태의 문자열 길이를 반환하라고 한다. 이 압축은 k(q)의 형태를 하고 있고, k는 '한자리' 정수이다. q는 임의의 문자열이 들어올 수 있다. 예시들이 좋아서 예시들을 잘 이해하면 쉽게 문제 파악을 할 수 있다. 풀이 내가 생각한 방법은 재귀. (가 나올 때 해당 괄호가 닫히기까지의 문자열에 대해 재귀를 들어가 해당 위치에서 나오는 값..

목차 개요 1030번: 프렉탈 평면 (acmicpc.net) 1030번: 프렉탈 평면 첫째 줄에 7개의 정수 s, N, K, R1, R2, C1, C2가 주어진다. www.acmicpc.net 정해진 횟수 s만큼 프랙탈 동작을 한다. 이 프랙탈 동작은 현재 주어진 공간을 n*n으로 분할하고, 그 중 k*k에 해당하는 중앙 부분을 검은색으로 칠하는 행위이다. 이런 s,n,k가 주어지고 또 출력하고 싶은 프랙탈의 공간 부분이 주어진다. 원하는 부분을 출력하면 된다. 풀이 프랙탈 동작은 공간이 쪼개지고 그 쪼개진 공간에 대해 다시 프랙탈 동작을 이어나간다. 즉 문제가 부분으로 쪼개지고, 각 부분이 전체에 대해 이뤄진 동작과 같은 수행을 한다는 것. 부분 문제로 쪼갤 수 있고, 같은 수행을 한다는 것은 재귀로 ..

목차 개요 9252번: LCS 2 (acmicpc.net) 9252번: LCS 2 LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 부분수열은 수열의 부분 중 연속되는 부분을 말하는 것이 아니라 순서를 지켜서 임의의 인덱스를 추출하여 만든 수열이다. 풀이 최장 공통 부분 수열 문제. LCS 1 문제가 있으며 해당 문제와 접근법은 완전히 동일하기 때문에 그 문제부터 푸는 것이 좋다. DP로 풀이할 수 있는 문제이다. 두 개의 문자열을 받으니 각 문자열을 행과 열로 삼는 2차원 배열을 만든..

목차 개요 17299번: 오등큰수 (acmicpc.net) 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 풀이 17298번: 오큰수 (acmicpc.net) 이 문제에서 파생된 문제라고 보면 된다. 어떤 배열을 받아서 새로운 배열을 만드는데, 새로운 배열의 각 원소는 원래 배열을 기준으로 오른쪽에 위치한 원소들 중에서 가장 큰 놈을 값으로 삼는다. 오른쪽에서 가장 큰 수, 줄여서 오큰수. 이 놈은 거기에서 한 스텝 더 나아가서 오른쪽에서 가장 등장 횟수가 큰 수, 오등큰수! 그래서 오큰수 풀이에서 Counter만 추가해서..

목차 개요 9935번: 문자열 폭발 (acmicpc.net) 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net 풀이 스택을 활용하는 문제. 출력할 리스트를 만들고 입력받은 문자열에서 문자를 하나하나 출력 리스트에 넣으면서 폭발 문자열이 있는지 체크한다. 있으면 해당 문자열을 바로 없애고 이후 계속 문자를 하나씩 넣으면 된다. 스택으로 차곡차곡 출력 문자열이 쌓이다가 폭발할 문자열이 만들어진다면 그 놈만 날리고 다시 문자열을 쌓는다는 것. 원리는 어렵지 않다. 코드 inlst = input() ex..

목차 개요 2444번: 별 찍기 - 7 (acmicpc.net) 2444번: 별 찍기 - 7 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 풀이 문제 설명이 간략해서 좋구만. 이런 문제가 간단해보이지만, 인덱스에 조건을 걸거나 응용하는 류의 문제라서 막상 해보면 꽤 귀찮은 문제이기도 하다. 규칙을 찾는 것 자체도 코테를 하는데 있어서는 중요한 역량이기도 하고. 보아하니 중간을 두고 대칭의 모양을 띄고 있으니 가운데가 0 정도의 값, 그리고 위 아래로 이산하면 될 것 같다. 그렇다면 abs를 써서 절대값을 활용하면 되겠다. 별의 개수는 홀수이다. abs에 2를 곱하고 1을 빼는 식으로 하면 될 것 같다. 공백 수는 432101234이다. 절대값을 그대로 활용하면 될..

목차 개요 10811번: 바구니 뒤집기 (acmicpc.net) 10811번: 바구니 뒤집기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2 www.acmicpc.net 풀이 리스트 속에서 특정 범위를 주면 그 범위의 값을 거꾸로 만드는 문제. 파이썬에서는 reversed이라는 내장함수를 통해 원소들은 거꾸로 된 iterable한 객체를 만들 수 있다. 코드 import sys input = sys.stdin.readline N, M = map(int, input().split()) inlst = list(range(1, N+1)) for _ in range(..