Simple Explain

#10825 국영수 https://www.acmicpc.net/problem/10825  정렬 관련 문제였다.  내 초기 코드는 다음과 같았다. from sys import stdininput = stdin.readlinen = int(input())students = []for _ in range(n): x = input().split() student, grades = x[0], list(map(int, x[1:])) students.append([student] + grades)# 국어 점수가 감소하는 순서로# 국어 점수가 같으면 영어 점수가 증가하는 순서로# 국어 점수와 영어 점수가 같으면 수학 점수가 감소하는 순서로# 모든 점수가 같으면 이름이 사전 순으로 증가하는 순서로 (단,..

#17144 미세먼지 안녕! https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 토요일에 시도했다가 포기하고 죽어있었다. 뭔가 잘못 구현한 부분이 있었는데 눈에 보이지 않았기 때문이다. 하지만 해결해냈다. 문제는 다음과 같았다. 먼지 데이터를 조금 더 효율적으로 관리하고 싶었다. 그래서 먼지의 위치를 저장한 리스트를 만들었었는데 공기청정기가 작동하게되면 먼지의 위치가 바뀐다. 이걸 반영을 안해줬기 때문에 문제가 발생했다. 이걸 파악한 뒤, 먼지의..

#3190 뱀 https://www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제가 짧아서인지 알고리즘을 꽤 풀어내서인지는 잘 모르겠지만 문제를 푸는 방법이 명료하게 보였다. 그래서 바로바로 구현했다. 뱀의 이동을 고민하던 터에, 큐를 사용하면 된다는 아이디어가 떠올랐고 적중했다. from copy import deepcopy n = int(input()) maps = [[0 for _ in range(n)] for __ in range(n)] for _ in ra..

#14499 주사위 굴리기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 일단 주사위를 구현하는 것 부터가 빡셌다. 처음엔 리스트 두개로 구현하려고 했는데 리스트 간에 값을 교환하는 횟수가 너무 많을 것 같다는 생각이 들었다. 주사위가 동서남북으로 움직일 때마다 각 6면의 변화를 상상했다. 이렇게 변화하는 모습을 보였다. (사실 처음에 잘못 판단해서 삽질을 좀 했다.) 따라서 ..

#14503 로봇청소기 https://www.acmicpc.net/problem/14503 14503번: 로봇 청소기 첫째 줄에 방의 크기 $N$과 $M$이 입력된다. $(3 \le N, M \le 50)$ 둘째 줄에 처음에 로봇 청소기가 있는 칸의 좌표 $(r, c)$와 처음에 로봇 청소기가 바라보는 방향 $d$가 입력된다. $d$가 $0$인 경우 북쪽 www.acmicpc.net 고민도 필요없었다. 문제의 설명을 그대로 코드로 옮겼다. (말 그대로 구현) # 1. get input h, w = map(int, input().split()) # map size width - height x, y, d = map(int, input().split()) # start position, x, y, direc..

#14888 연산자 끼워넣기 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 쉽다고 생각했다. 브루트포스 알고리즘을 사용해야하는 만큼 시간 초과가 마음에 걸렸지만 그래도 일단 해봤다. 시간초과 코드 import sys input = sys.stdin.readline num = int(input()) nums = [int(x) for x in input().split()] # +, -, ..

#11727 또 다시 타일링 https://www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 이번 문제의 점화식은 내 힘으로 찾았다. (노가다) 팁? 이라 하면, An 을 An-1과 An-2등 이 전의 값으로 조합하여 찾는게 팁이 될 수 있을지도 모르겠다. 그렇게 제출 했는데 또 자꾸 틀려서 많이 화가 났다. 자꾸 출력 형식을 무시하고 제출해서 그런거였다. 그렇게 세 번을 틀렸다. 병X.... 어제도 그러더니... 실수가 반복되면 실력이랬다. 엥 근데 또 틀렸다 (100%에서) 뭐지?.....

내가 생각하는 다이나믹 프로그래밍의 핵심은 점화식을 파악하는데 있다. 그러니까 고등학교 때 봤던 확률과 통계 느낌 나는 문제들을 이해하는게 아주 중요하다. #11726번 2xn 타일링 https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net n의 변화에 따른 타일링의 경우의 수를 계산해주면 되는데 내가 처음 판단한 점화식은 이렇다. An = An-1 + (n-2) 였다. 뭐 예상한 결과다. 고민고민 하다가 결국엔 서치... 결론은 An = An-1 + An-2 였고 맞추긴 ..

#1935 https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 후위표기식이라는 새로운 개념을 만났다. 기존의 수학 표기법은 중위표기식 이라고 하는데 A + (B*C) - D/E 이렇게 연산자(기호)가 피연산자(수) 사이에 위치한다. 반면에 후위 표기식은 연산자가 피연산자 뒤에 위치하는데, 위 식과 동일한 형태의 식이 ABC*+DE/- 이다. 어떻게 처리하나 고민을 많이 했지만, 역시나 Stack을 사용하면 됐다. 기호가 나오기 전 까지 ..