분류 전체보기 36

1759: 암호만들기

문제접근 전형적인 백트래킹 문제 유형이다. l, c 값과 알파벳을 받아오고, vowel(모음) 5개를 리스트에 넣어준 뒤, findPassword라는 재귀 함수를 만들어주었다. 이 함수의 로직을 간단히 설명하겠다. 1. 현재 만들어진 문자열(비밀번호)의 자음, 모음의 개수를 확인하고, 조건에 부합하지 않으면 return 2. 이 문자열(비밀번호)이 L과 같다면 해당 값을 arr에 담아줌 3. 제공된 문자열을 순회하며 자음, 모음 여부를 판단하고, 기존 문자열에 해당 문자를 추가해준 값과 함께 매개변수에 자,모음의 개수를 담아 재귀호출 첫번째 풀이(실패) 1. 작은 실수,, 시작하는 글자의 자음 or 모음 여부를 반영해주지 않았다..!(실제 풀이였다면 testcase에서 실수를 깨달았을 것 같아 큰 문제는..

11047: 동전 0

문제 접근 탐욕적 기법의 대표문제로 볼 수 있는 동전 문제이다. 예전에 풀었던 문제라 수월하게 풀었다. 가장 값이 비싼 동전부터 사용해서 전체 금액을 모두 차감하는 식으로 구성하면 된다. import sys n, k = map(int, sys.stdin.readline().split()) coins = [] for i in range(n): coin = int(sys.stdin.readline()) coins.append(coin) i = 0 cnt = 0 while k: big_coin = coins[-(1 + i)] cnt += k // big_coin k = k % big_coin i += 1 print(cnt)

11501: 주식(Python)

문제접근 이 문제도 회의실 배정과 마찬가지로 그리디 접근 방법으로 풀어야 하기 때문에 명쾌한 테스트 케이스 증명이 아닌 그럴듯한 가설을 세우고 코드를 돌려보며 검증하는 방식으로 접근해야 했다. 회의실 문제와 다르게 시간순으로 정렬된 배열이기에 멋대로 배열의 순서를 바꿨다가는 대참사가 일어날 것 같아 정렬은 사용하지 않았다. 시간 제한은 5초지만 테스트케이스 배열의 길이가 (2 ≤ N ≤ 1,000,000) 라 시간이 넉넉하다고도 볼 수 없었다. 우선 1) 미래의 가격을 예측할 수 있다는 가정 하에 거래하고, 2) 단순하게 가지고 있는 현재의 주식을 모두 파는 것이 아니라 원하는 만큼 팔 수 있다는 점에 주목했다. 그런데 조금 생각해보니 미래를 예측할 수 있다는 가정이 있으니 주식의 가격이 내리면 사고, ..

백준 온라인 저지 - 스택(# 10828) 파이썬

문제설명 기본적인 스택 자료구조를 구현하는 문제입니다. 스택 (# 10828) 파이썬 코드 import sys n = int(sys.stdin.readline()) stack = [] for i in range(n): inp = list(map(str, sys.stdin.readline().rstrip().split())) if inp[0] == "push": stack.append(inp[1]) elif inp[0] == "pop": if not stack: print(-1) continue print(stack.pop()) elif inp[0] == "size": print(len(stack)) elif inp[0] == "empty": if not stack: print(1) continue pri..

백준 온라인 저지 - 수 정렬하기3(# 10989) 파이썬

문제설명 아주 적은 공간의 메모리만 할당되었고, 배열에 들어갈 수 있는 최댓값이 크지 않은 경우 카운팅정렬을 통하여 문제를 해결할 수 있습니다. 수 정렬하기3(# 10989) 파이썬 코드 a, b, c = map(int, input().split()) while True: try: bep = int(a/(c-b)) + 1 #try문 밖에 쓰면 ZeroDivsionError 발생 if bep > 0: print(bep) else: print(-1) except ZeroDivisionError: print(-1) break

동적계획법(Dynamic Programming) 문제풀이

다이나믹 프로그래밍 문제에 접근하는 방법 - 주어진 문제가 다이나믹 프로그래밍 유형임을 파악하는 것이 중요 - 가장 먼저 그리디, 구현, 완전탐색 등의 아이디어로 해결할 수 있는지 검토 다른 알고리즘으로 풀이방법이 떠오르지 않으면 다이나믹 프로그래밍 고려 - 우선 재귀함수로 비효율적인 완전 탐색 프로그램을 작성한 후 Top-Down(작은 문제에서 구한 답이 큰 문제에 사용될 수 있음) 방식이 적용될 것 같으면 코드를 개선하는 식 - 점화식 떠올려보기 - 일반적인 코딩테스트 유형에서는 기본 유형의 다이나믹 프로그래밍 문제가 출제되는 경우가 많음 다이나믹 프로그래밍 문제1: 개미 전사 A(i): i번째까지의 식량창고가 존재할 때 털 수 있는 식량의 최댓값 K: 식량창고 리스트 개미전사 파이썬 코드 impor..