s0n9h2

문제 https://www.acmicpc.net/problem/17352

문제 https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 사용 언어 Python3 풀이 과정 DP를 이용해 풀었는데 Python3로는 시간 초과로 실패했다. from sys import stdin input = stdin.readline n = int(input()) # dp[i] = 숫자 i가 가지는 제곱수 합 최소개수 dp = [float("inf")] * (n + 1) dp[0] = 0 dp[1] = 1 f..

문제 https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 사용 언어 Python3 풀이 과정 오랜만의 골드 문제!! 처음 내가 짰던 코드는 다음과 같다. 나름 붙어있는 RR은 원래대로 돌아오기 때문에 없애는 처리를 했는데도 시간초과가 났다..! 심지어 pypy3로도... from collections import deque from sys import stdin input = stdin.readline def func (functions, array): for func in functions: if fu..

문제 https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 사용 언어 Python3 풀이 과정 이 문제는 조합(combinatoin)을 이용하는 법 / 백트래킹(DFS)을 이용하는 법 이렇게 두 가지 버전으로 풀었다. 조합은 진짜 쉽게 풀었지만, 백트래킹을 구현하는 과정에 있어서 N과 M (2)에 추가된 조건인 오름차순 수열만 출력하는 방식이 추가되었는데... 나는 처음에 for문을 수정하지 못하겠어서 출력시에 오름차순 정렬인지를 확인해 맞는 경우..

문제 https://www.acmicpc.net/problem/15989 15989번: 1, 2, 3 더하기 4 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2 www.acmicpc.net 사용 언어 Python3 풀이 과정 오랜만에 다시 DP 문제를 풀게 되었다. 그런데 이번에도 헷갈린 점화식 세우기...ㅎㅎ 처음엔 냅다 dp[i-1] + dp[i-2] + dp[i-3] 을 생각해봤는데 아무래도 중복되는 건 하나로 치는 경우 때문에 결과가 훨씬 크게 나왔다. 다시 곰곰이 생각해서 1을 더하는 경우는 항상 있기 때문..

문제 https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 사용 언어 Python3 풀이 과정 이 문제는 저번에 프로그래머스 못 풀었던 문제처럼(좀 더 쉽지만) 완전 탐색 방법이 제일 처음 떠올랐다. 그래서 그대로 풀어봤더니 python3에서는 시간초고ㅏ... 혹시 몰라 pypy3로 돌려보니까 진짜 천천히 올라가더니 맞았습니다!!가 나오긴 했다. 이후 이중 for문으로 list 선언한 부분을 l..

문제 https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 사용 언어 Python3 풀이 과정 이거야말로 저번에 풀었던 4256번. 트리 문제와 비슷하다고 생각했는데 한 번에 풀지 못했다... 그 문제는 그냥 트리이고 이건 이진 트리임을 이용한 문제인데 이진 트리의 개념은 알고 있었지만 탐색을 어떻게 해야할지...막막쓰.. 그래서 다른 블로그의 도움을 받아😥 맞았습니다!! 처음 제출 후 while True: 를 while count en..

문제 https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 사용 언어 Python3 풀이 과정 사실 이 문제는 4256번. 트리 문제를 풀기 전에 풀었어야 순서적으로 맞았을 것 같다. 그 때 더 어려운 문제를 풀면서 확실히 기억했던 건 전위순회, 중위순회, 후위순회의 구현시 차이점은 print() 하는 순서의 차이였다는 것..? 그래서 딕셔너리를 이용해 혼자 풀어보다가, 마음에 안들어서 구글링을 한 뒤 class를 이용한 풀이로 변경했다...

문제 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 사용 언어 Python3 풀이 과정 이 문제는 2차원 배열로 푸는 버전도 있는 것 같지만 우리는 바로 3차원 배열로 푸는 버전이 숙제였다. 3차원 배열을 선언하는 것도, 거기에 vector값을 이용해 bfs를 사용하는 것도 처음이어서 검색을 좀 했다. list comprehension이 참 깔끔한 파이썬! 처음에는 아래처럼 모든 토마토가 저장될 때부터 익어있을 때 0을..

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 사용 언어 Python3 풀이 과정 이 문제는 실버 I길래 그나마 쉽게 풀 수 있을 줄 알았는데 또 약간 새로운 형태의 bfs라서 당황스러웠다..! 지금까지 푼 dfs 문제들은 대부분 vector 값을 이용해서 상하좌우를 살피는 방식이었는데 이 문제는 좌, 우, *2를 살펴야 했기 때문이다. 그래서 혼자 visited가 아닌 dp처럼 여기까지 몇 초 걸리는지를 계산..

문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 사용 언어 Python3 풀이 과정 또다른 동적계획법 문제이다. 동적계획법 문제가 진짜 많은 것 같다. 계단을 한 칸 오르거나 두 칸 오를 수 있으므로 두 가지 중에 더 큰 값을 넣어주는 것은 당연했는데, max(두 칸 전과 현재 칸을 더한 것 / 세 칸 전과 이전 칸, 현재 칸을 더한 것)을 생각해내는 게 좀 어려웠다. 그리고 처음에는 런타임 에러가 떴다. 보통 런타임 에러는 간단하게 프로그램이 비정상..

문제 https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 사용 언어 Python3 풀이 과정 solved.ac의 클래스 3을 따내려고 난이도가 낮은 것부터 한 문제씩 푸는 중인데, 아직까지는 풀만 한 것 같다. 이번에는 DP와 수열이 합쳐진 문제였고 규칙성을 생각해보면 그대로 금방 풀 수 있었다. 삼각형이기 때문에 변의 개수 만큼 돌아가고, 그래서 i번째 숫자와 i+1번째 숫자를 더한 값이 i+3번째에 놓인다는 사실을 알았다. 그렇게 풀어서 제출했더니 ..

문제 https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 사용 언어 Python3 풀이 과정 실버 III이고 문제 설명이 좀 길어서 그래도 좀 난이도가 있겠거니 생각했는데 생각만 하면 코드는 정말 간단한 문제였다! 각자가 돈을 인출하는 데 걸리는 시간이 다르기 때문에 사람들이 줄을 서는 순서에 따라서, 기다리는 시간이 차이가 나게 되는데 각자가 기다린 시간을 합쳤을 때의 시간이 최소가 되게 하는 문제였다. 따라서 간단하게 돈을 인출하는 데 오래걸리는 사람이 앞에 있으면 모두가 ..

문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 사용 언어 Python3 풀이 과정 며칠 전에 공부한 다익스트라 알고리즘의 기본 문제를 풀어보았다. float('inf')를 print( )하면 inf로 잘 뜨길래 그대로 제출했는데 처음에 틀렸습니다가 떴길래 문제를 다시 읽으니 출력 형식이 inf가 아닌 INF였다. print(*distance[1:], sep='\n') 그래서 삼항 연산자로 바꿔서 출력..

문제 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 사용 언어 Python3 풀이 과정 실버 IV 지만 그래도 아이디어가 한 번에 맞아서 기분 좋은!! 팩토리얼 연산을 했을 때 맨 뒤에 붙는 0의 개수를 구하는 문제였다. 0은 곧 10을 곱한 것을 의미하니 2*5의 세트 개수를 구하면 된다고 생각했고, 따라서 처음에는 2의 개수 5의 개수를 각각 구해서 min값을 저장하려 했다. 그런데 풀다 보니 5가 한 번 나올 동안 2는 무조건 한 번 이상 나온다는 것을 깨달았고, 따라서 새로 더할 숫자가 5로 나누어 떨어지는 개수만 구해서..

문제 https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 사용 언어 Python3 풀이 과정 solved.ac의 클래스 점수를 얻고 싶어서 관련 문제를 하나씩 풀어보려고 한다. 당연히(?) 쉬운 문제부터 푸는 중이라서 고른 문제인데 입출력 관련 문제였고 왜 실버지? 싶을 정도로 아주 쉬웠다. 처음 내가 짰던 코드는 다음과 같다. from sys import stdin input = stdin.readline sites..

문제 https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net 사용 언어 Python3 풀이 과정 엘리스 강의로 다익스트라 알고리즘 개념과 우선순위 큐의 기본에 대해 공부하고 풀어보려고 했는데, 역시 바로 적용하는건 무리무리😌 심지어 적용한 코드를 보고도 잘 이해가 되지 않았다😅 나는 처음에 지름길로 언급된 위치만 정점으로 계산하려고 set을 사용해서 위치를 정의했는데, 그렇게 하면 이전 길들중 더 짧은 길을 파악하기가 어려워서 결국 0, 1..