백준

백준 4949 풀이 (균형잡힌 세상, 스택)

이런 소괄호 중괄호 맞게 찾기는 스택으로 풀어야한다. 옛날에 자료구조 공부할때 교수님이 스택으로 문제를 푸셨었다. 만약에 괄호 하나만 확인하는 거면 굳이 스택으로 풀 필요가 없지만 이번 문제는 소괄호와 대괄호로 2개이기 때문에 스택으로 풀어봤다. 1. 만약 (, [ 이라면 스택에 쌓는다. 2. ), ] 가 나오면 스택에 top에 쌓인게 소괄호인지 중괄호인지 비교하여 같으면 스택에서 제거한다. 3. 만약 ), ] 가 먼저 나오면 잘못 입력된 것이기 때문에 바로 종료시킨다. 대강 이러한 느낌으로 코딩을 짜면 코드는 아래와 같다. 좀더 효율적으로 짤 수 있었을거 같은데 내가 좀 무식하게 코딩하다 보니 저렇게 돼버렸다.ㅎㅎ while True: tmp = input() if tmp == ".": break st..

백준 10773 풀이 (sys.stdin.readline())

이번에는 그냥 복습용이다. 문제는 하나도 안어렵다. 그냥 0을 만나면 이전꺼 제거하고 아니면 리스트에 넣어놓았다가. 마지막에 총합을 구하면 된다. 그러나! 이렇게 쉬운 문제를 리뷰하는 이유는 sys.stdin.readline()의 중요성 때문이다. 위는 sys.stdin.readline()을 적용한 코드이고 아래는 input()을 적용한 코드이다. 시간을 보면 거의 40배 차이가 난다. 즉, 입력받는 경우가 상당히 많아질 경우에는 sys.stdin.readline()을 쓰는게 얼마나 속도 절감에 도움이 되는지 절실히 느낄 수 있었다. 결론은 아래와 같이 k값이 100,000이나 되는 경우에는 반드시 sys.stdin.readline()을 사용하여 속도를 높이자!!! import sys n = int(in..

백준 10828 풀이 (스택, sys.stdin.readline, 입력속도 높이기)

문제는 쏘쏘하다 스택을 구현하면 된다. 나는 리스트를 스택처럼 사용하기로 했다. 리스트에는 append(), pop(), len()등 쉽게 활용할수 있는 메소드가 존재하기 때문에 쉽게쉽게 가기로 했다. 처음에 제출을 했을때는 시간초과가 나왔다. 왜 그런건가? 하고 고민을 3초 하다가 sys.stdin.readline으로 바꿔서 풀어보기로 했다. sys.stdin.readline은 한줄을 그대로 입력을 받는다. 따라서 \n(개행문자)가 같이 들어오는 단점이 있으나 굉장히 빠르게 입력을 받기 때문에 많은 입력을 받아야하는경우 쉽게 사용할수있다. 무식하게 코딩을 한 결과 정답을 맞출 수 있었다. import sys n = int(input()) stack = [] for _ in range(n): tmp = ..

백준 2004 풀이 (조합 0의 개수)

진짜 개어려웠다. 처음에는 저번에 DP로 조합 푼거 생각나서 그러한 방식으로 풀면 되나 싶었는데 조건으로 나오는 값이 너무 컸다. DP로 풀어도 분명히 시간 초과날게 뻔했다. 그래서 이것저것 뒤져봐도 안되서 DP로 풀었더니 아니나 다를까 시간초과가 났다. 그래서 고수들이 푼 방식을 슬쩍 훔쳐봤다. 슬쩍 봤더니 0이 나오기 위해서는 조합의 결과안에서 2와 5가 한쌍으로 나와야 끝자리에 0이 생성된다. 따라서 해당 값의 결과에 2와 5의 개수가 몇개나 나오는지 확인해야한다. 처음에는 고수의 코드를 보고도 이해가 안갔다. 5!에 2와 5가 몇개 있는지 보려면 5!을 구하고서 2나 5로 나누면 되는거 아닌가? 라는 생각도 했다. 그런데 고수들은 5를 2로 나눠서 구하거나 5를 5로 나눠서 구하고 있었다.......

백준 9375 풀이 (패션왕 신혜빈, Counter)

크게 어려운 점은 없었다. 다만 코드를 짤때 예외나 조건을 잘 봐줘야한다. 문제는 단순하게 경우의 수를 구해주면 된다. 옷을 돌려입는 경우의 수만 구하면 되는거 같지만 안입는 경우도 고려하여 계산 해야하기 때문에 각 옷마다 +1을 해주어 경우의 수로 곱해주면된다. 예를 들어 안경 2개, 모자 2개라면 3 x 3 = 9이므로 여기에 둘다 착용하지 않는 경우 -1을 해주면 8이 된다. (단, 이때 옷을 입지 않는 testcase가 0인 경우도 고려해주어야 한다.) 이러한 방식을 코딩해주면 아래와 같다. n = int(input()) for _ in range(n): t = int(input()) if t == 0: print(0) continue dic = {} for _ in range(t): name,k..

백준 1010 풀이 (다리 놓기, 다이나믹 프로그래밍)

오우 진짜 나 수학적 지식이 부족한게 너무 뼈저리게 느껴졌다ㅋㅋㅋㅋㅋㅋㅋㅋ 이거 일일히 다리 그리면서 안겹치게 하려면 어떻게 해야하나 규칙찾고 있었다.....ㅋㅋㅋㅋㅋ 하...그러다가 먼가 조합스러워서 조합계산기를 돌려보니까 그냥 조합 문제였다. 그래서 11051 문제에서 사용했던 DP로 조합구하는 코드를 사용해서 미리 연산을 통해 필요한 조합값들을 구하고 필요할때 부르는 방식으로 코딩을 진행했다. 시간 제한이 0.5초라 이러한 방식이 효율적이라 판단했다. memo = [[0 for i in range(30+1)] for i in range(30+1)] memo[1][0] = 1 memo[1][1] = 1 for i in range(2,30+1): memo[i][0] = 1 for j in range(1..

백준 11051 풀이 (이항 계수 2, 다이나믹 프로그래밍)

11050에서 풀었던 방식대로 대강 풀어봤으나 재귀함수의 recursion 제한때문에 연산에 어려움이 있었다. 그래서 연산을 줄이기 위해 DP를 생각해보았다. 메모제이제이션을 어떻게 사용해야하나 고민을 하다가 팩토리얼 자체를 for구문으로 구해서 연산할 생각을 했다. 문제는 그렇게 하는 경우 메모리에서 뻗는걸 확인했다. 그래서 도대체 어떻게 DP를 쓰라는 건지 모르겠어서 고수의 방식을 살짝 엿보러 구글링을 해보았다. 알고보니 조합에도 규칙이 있었다. 이걸 도대체 어떻게 생각해 낸건지 나의 머리로는 아마 일주일이 걸려도 못찾았을 것 같다. 그래서 저 규칙을 토대로 DP 코딩을 하면 아주 간단하게 큰 값의 조합을 구할 수 있다. a,b = map(int, input().split()) memo = [[0 f..

백준 11050 풀이 (이항 계수 1, 팩토리얼)

문제의 난이도는 상당히 쉬운 문제이나 이항계수가 무엇인지 몰라서 구글링을 좀 했다. 이항 계수는 주어진 크기에서 원하는 개수만큼 순서없이 뽑히는 가짓수를 의미한다. 조합이라고 해야하나? 문과라서 그런가 배웠는데도 용어가 하나도 익숙하지가 않다. 여튼 생긴건 5C2 이런식으로 생겼다. 그래서 5개중에서 2개를 뽑는 가짓수를 구하라.... 요런 느낌이다. 찾아보니 팩토리얼을 사용해야하고 식은 아래와 같다. 요런 느낌이다. 그래서 오랜만에 재귀를 써야한다고 생각이 들어서 팩토리얼 함수를 만들어서 사용해 보았다. def fac(n): if n