🏴󠁩󠁤󠁪󠁷󠁿Facts(한 것) & Findings(배운 것) 알고리즘 문제를 몇개 풀었다. 힙, DP 문제 몇개를 두고 한 두시간 씨름을 하니 3시였다. 힙 문제는 최소힙 문제다. 1927번: 최소 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 예전에 C++로 풀었을 때는 라이브러리에 priority_queue가 정의되어 있었기 때문에 푸는데 10분도 안 걸렸었다. 문제는 파이썬인데, 나는 Heapq를 써서 풀고 싶지 않았다. 적절한 알고리즘을 찾아서 문제를 풀었는데, 계속 시간초과가 발생해서 어쩔 수 없..

백준 2108 통계학 문제.(실버3) 이 문제를 소개하는 이유는 파이썬의 라이브러리인 statistics를 소개하기 위함이고, 이와 동시에 '어떻게 문제를 풀 것인가' 에 나오는 문제를 풀이하는 방법을 적용해보기 위함이다. '어떻게 문제를 풀 것인가' 에서는 사고의 4가지 단계를 다음과 같이 소개하고 있다. 문제가 무엇인지 파악한다.(문제를 이해한다.) -> 미지인 것은 무엇인가? 자료는 무엇인가? 조건은 무엇인가? 연관 관계를 파악하고 계획을 수립한다. 계획을 실행한다. 회고한다. 그럼 위의 단계에 따라 문제를 해결해보자. 1. 문제파악 미지인 것은 산술 평균, 중앙값, 최빈값, 범위이다. 자료로 주어진 것은, n개의 수와, 주어질 수를 결정하는 n, 그리고 범위의 정의이다. 2. 계획 수립 산술 평균..

백준 알고리즘 문제 3474번 교수가 된 현우 문제이다. 실버 4의 문제로 머리만 잘 굴리면 풀 수 있는 문제이다.(사실 모든 문제가 그렇긴 한데, 머릿속으로는 돼도, 구현이 쉽지 않지) 이 문제에서는 팩토리얼을 했을 때 나오는 0의 갯수를 구하라고 나와있다. 그러니까 5!을 하면 120이 나오니까 0이 한 개 인 것이다. 당연히 처음에는 모르니까 하나씩 적어보는게 편하다. 6! 은 720, 7! 은 5040(오른쪽 0갯수만 셈) 8!은 40320.... 자세히 살펴보면 2와 5의 제곱의 짝의 갯수에 의해서 0의 갯수가 정해지는 것을 알 수 있다. 그럼 당연히 소인수 분해를 하면 2의 갯수는 5의 갯수보다 많기 때문에, 결국 5의 제곱의 갯수만 구하면 되는 쉬운 형태로 결론이 난다. 그렇기 때문에 이를 ..

백준 10709 기상캐스터 문제이다. 실버 5의 문제이기 때문에 간단하게 풀 수 있다. 문제를 요약하면 원래 C가 있던 자리에는 0을, 구름이 나타나지 않으면 -1을 그게 아니면 몇 분 후에 구름이 나타나는지 표시하면 된다. 구름이 나타나지 않는다는 말은 그 행에 C가 없다는 의미이다. 방법은 여러가지가 있지만, 모두 배열에 추가해서 마지막에 한꺼번에 출력할 수 있고, 한 줄 한 줄 출력할 수 있다. 나는 한 줄 한 줄 출력하는 방법을 선택했다. h, w = map(int, input().split()) for _ in range(h): t = -1 cloud = input() temp = [] for i in range(len(cloud)): if cloud[i] == 'c': t = 0 temp.ap..

백준 2870 수학숙제 문제이다. 상근이가 숫자만 찾으면 돼서 별로 어려운 문제는 아니다. 다만 문자열을 처리할 때, 파이썬이 아닌 다른 언어들은 살짝 까다로울 수 있다. 이 문제 해결의 핵심은 문자열에서 숫자를 어떻게 뽑아내는가이다. 나는 이것을 큐(queue)로 해결했는데, 문자일 경우 버리고, 숫자일 경우 임시 문자열에 더해서 배열에 추가하는 방식을 사용했다. 이후 map 을 사용해서 문자열을 숫자로 바꿔주면 자연스럽게 앞자리가 0인 숫자(문자열) 들은 10진수로 변환될 것이다. (012 -> 12 , 0014 -> 14) 이렇게 해서 비내림차순(오름차순이라고 하면되는데 굳이...)으로 정렬해서 출력하면 끝. n = int(input()) a = [] temp = '' for i in range(n..

백준 4659 비밀번호 발음하기 문제이다. 알고리즘 분류는 구현과 문자열. ('그냥 닥치고 풀어라'라는 뜻) 위의 문제를 읽어보면 3가지 조건이 주어져있다. 모음은 하나를 반드시 포함해라, 모음이 3개 혹은 자음이 3개 연속으로 오면 안 된다, 같은 글자가 연속적으로 두 번 오면 안 되나, ee와 oo는 허용한다. 언뜻 보면은 이거 일일이 해야하나 싶지만, 실제로 그렇다. (말이 다르잖아!!) 하지만 겁먹을 필요는 없다. 구현은 뭐다? 주먹구구식. while 1: word = input() if word == "end": break flag = True temp = word for x in "aeiou": temp = temp.replace(x, "a") for x in "qwrtypsdfghjklzxv..