HOME (207) 썸네일형 리스트형 2024 상반기 회고록 + 취준 이야기 보호되어 있는 글입니다. [백준/Python] 3687번 성냥개비 풀이 문제 해석 문제 풀이 문제 알고리즘 선택 각 숫자별 필요한 성냥개비의 갯수는 아래와 같다 1 2 3 4 5 6 7 8 9 0 2 5 5 4 5 6 3 7 6 6 최대값 2개(1)와 3개(7)이 최소 갯수이며 모든 성냥을 1과 7을 통해 소진 시킬 수 있으며 가장 많은 자리수를 가질 수 있도록 유도할 수 있다. 따라서 최대값은 1과 7을 이용해 단순한 탐욕법 (그리디)로 풀어낼 수 있다. 최소값 브루트 포스로 3,5,9와 같은 숫자를 제외한 모든 숫자로 만들어낸 성냥의 갯수를 이용하려고 했으나 최대값을 고려했을 때 시간 초과가 난다 다시 한 번 17까지 모든 숫자를 계산해보았더니 이전 값에 새로운 자리수(0~9)를 추가하는 형태임을 발견했다. (그러나 6개일 때와 13개일 때와 같이 앞자리에 0이 올 수 .. [백준/Python] 16639번 괄호 추가하기3 풀이 문제 해석 문제 풀이 문제 알고리즘 선택 중복된 괄호가 가능하며 괄호의 갯수 제한이 없다 모든 경우의 수를 계산하여도 수식의 길이가 19라 충분할 것처럼 보인다. 브루트포스로 풀이 풀이 과정 숫자와 연산자를 분리하여 저장한다. 연산자의 index를 기준으로 각각의 연산자가 먼저 계산되는 permutation을 구한다 구한 값과 기존 식을 결합시킨다 (연산자의 경우 사용한 연산자를 제외시킨다) 숫자 배열이 1개만 남았을 때 값을 정답배열에 추가시킨다 정답 배열에서 값을 도출한다 코 드 import re import sys import operator from itertools import permutations length = int(sys.stdin.readline()) expression = sys.s.. [백준/Python] 16637번 괄호 추가하기 풀이 문제 해석 문제 풀이 문제 알고리즘 선택 중첩된 괄호는 사용할 수 없고, 괄호의 갯수는 제한이 없다 괄호는 (a+b)+c 형식이거나 a+(b+c)의 형태로 3개의 숫자 중 12번을 묶거나 23번을 묶는 경우의 수만 존재한다. 재귀함수를 이용해 두 형태로 가지 뻗어 브루트포스로 풀어내기 풀이 과정 식에서 숫자와 연산자를 분리하여 저장한다. 숫자의 맨 앞 값을 빼내 연산자와 갯수를 맞춰준다. index 숫자를 기준으로 재귀함수를 작성한다. 괄호를 12번을 묶는 경우와 13번을 묶는 경우로 하여 계산한다. index가 끝에 도달하면 정답 배열에 값을 추가한다. 정답 배열의 최대값을 도출한다. 코 드 import sys import operator import re s_length = int(sys.stdin... [백준/Python] 1446번 지름길 풀이 1. 문제해석 2. 풀이 과정 문제 알고리즘 선택 지름길을 타지 않았을 때 이전 값과 지름길을 탄 경우의 값을 비교하는 형태로 이전 값에서 다음 값을 쌓아올리기 가능 최대 거리가 1만이며 최대 지름길의 경우의 수가 12개로 모든 경우의 수를 dp로 제한 시간 내에 해결 할 수 있다. dp로 풀이 풀이 과정 현재 값에서 지름길을 탈 수 있다면 현재 거리에서 지름길을 탄 값과 지름길을 타고 난 후 값을 비교하여 최소값을 넣는다 현재 값과 바로 직전 값에 + 1을 한 값의 최소값을 비교한다. 3. 코드 import sys route, distance = map(int, sys.stdin.readline().split()) shortPath = [list(map(int, sys.stdin.readline().s.. [백준/Python] 1238번 파티 풀이 문제 해석 문제 풀이 이 문제는 벨만포드 풀이와 다익스트라 풀이가 있으며 다익스트라 2번 만으로도 풀어낼 수 있다. 벨만포드의 경우 C++에서는 통과하였으나 pypy, python 모두 불통과를 받았다... 모든 순서쌍의 거리를 계산하는 방식이니 아래 코드에서만 설명하고 생략하자 다익스트라 2회로 문제를 풀어낼 수 있다는 것이 너무나도 흥미로웠는데 이유는 아래와 같다. 모든 마을(노드)에서 특정 마을로 가는 길(간선)이 존재한다고 하면 간선을 뒤집어서 특정 마을에서 출발하면 모든 마을로 가는 최소 거리를 알 수 있다. (너무나도 충격적인 발상이다..... 대체 뭘 해야 이런 발상이 가능하지) 그리고 기존 순서쌍을 이용해 특정 마을에서 모든 간선으로 돌아가는 거리를 계산하면 총 2번만에 계산할 수 있다. .. [pypy/python] 같은 코드상에서 pypy가 python보다 메모리를 많이 먹는 이유 백준에서 문제를 풀다가 recursion error가 발생했고 메모리 제한을 풀다 문제를 발견하였다. sys.setrcursionlimit(10**5) 위와 같은 코드로 recursion limit을 풀어주고 다시 제출하였더니 pypy에서는 메모리 초과를 받고 python에서는 통과했다. 내가 알고 있던 지식으로는 pypy가 JIT(just in time) 방식을 사용하기 때문에 필요한 부분을 즉석해서 컴파일하고 캐싱하며 인터프리터의 속도적 단점을 개선한 모델로 알고 있었는데 python에서만 합격을 받아 놀랬다. 이유를 찾아보니 PyPy는 Generational Garbage Collector를 사용하는 반면 CPython은 Reference Counting과 간단한 세대별 가비지 컬렉션을 사용 PyP.. [백준/Python] 2579번 계단 오르기 풀이 문제 설명 문제 풀이 dfs를 통해 하나 또는 두 계단을 밟으며 세 개의 계단을 연속해서 밟는 경우를 가지치면 어떨까? 라는 생각을 하였지만 생각보다 조건처리가 번거롭고 2300 은 생각보다 너무 큰 숫자가 될 것 같아 포기하고 dp를 생각했다. 점화식을 세우려고 패턴을 찾다가 그냥 규칙을 이용하기로 했다. 최대 2번 연속된 계단을 이용할 수 있으니 ONE,TWO를 통해 state로 구별해 연속된 계단을 몇칸 밟았는지 확인한다. (ONE에는 1칸 연속된 계단을 이용한 값, TWO에는 2칸 연속된 계단을 이용한 값) ONE의 경우 2칸 이전 계단에서 값을 받아오고 TWO의 경우 바로 이전과 두칸 이전 계단 중 ONE state에 있는 값만 가져와 비교한다. N까지 쌓아 N번째 계단에 도달한 경우의 최고 값.. 이전 1 2 3 4 5 ··· 26 다음
