백준

백준 11651 풀이 (sort, 여러 인자 정렬하기)

sort를 이용해서 풀면 코드가 상당히 간단해진다. 예를 들어 tmp에는 리스트가 삽입되기 때문에 2차배열이 생성된다. tmp = [[1,2],[1,3],[-2,3]] 과 같은 방식으로 저장된다. 그러면 리스트에서 사용가능한 sort 내장함수를 이용해서 간단하게 정렬할 수있다. 주로 sort만 쓰는경우말고 key로 람다식을 사용해주면 정렬의 우선순위를 정할 수 있다. tmp.sort(key=lambda x: (x[0],x[1])) 를 사용하게 되면 x[0]을 먼저 정렬하고 x[1]을 다음 우선순위로 정렬한다. 따라서 [-2,3] [1,2] [1,3] 으로 정렬되는 것이다. case = int(input()) tmp = [] for _ in range(case): tmp.append(list(map(int..

백준 2108 풀이 (python, collections, Counter)

이번꺼 어떻게 해야하는지 알면서도 헤맸던 문제였던거 같다. 계속 시간초과가 나와서 좀더 빠르게 할수 있는 방법이 있는지 찾아보기도 하다가. collection을 알게 되었다. 예전에 악성코드 분석할때 전처리 과정에서 사용해보라는 추천을 받았던 기억이 난다. 물론 난 이전 방법이 다루기가 편해서 굳이 사용해보지 않았지만 이번에 사용해 볼 수 있었다. collections모듈을 데이터 처리를 할때 자주 사용된다고 한다. 합을 구하거나 중복수를 찾거나 하는경우 Counter객체를 사용한다고 한다. 따라서 이 객체를 사용해보았다. Counter는 딕셔너리 형태처럼 사용된다. 따라서 딕셔너리에서 사용가능한 함수들을 사용가능하다. Counter에서 중요한 함수는 most_common이다. 이 함수를 사용하면 가장 ..

백준 2751 풀이 (힙정렬)

힙정렬이 배웠는지 안배웠는지도 기억이 안나고 먼지 모르겠었다. 그래서 강의를 짧게 듣고 python에는 heapq라는 모듈이 있다는 것을 알게되었다. 그래서 heapq 모듈을 사용해서 풀었다. c++로 구조를 내가 짜면 더 공부가 되었겠지만 아직까지는 그정도 수준에 오르지 못했기에 모듈을 사용해서 간단히 풀수 있었다. import heapq as hq case = int(input()) a =[] for _ in range(case): hq.heappush(a,int(input())) for _ in range(case): print(hq.heappop(a)) 단, 제출은 pypy3로 해야했다.

백준 11729 풀이 (하노이탑)

오우 아주 쒯같지만 좋다고 느낀 문제였다. 계속 재귀에 대해서 벽을 느끼고 있었는데 재귀의 동작방식을 너무나 잘 공부할 수 있었다. 하노이탑 알고리즘을 보다 보니 너무 좋은 글을 써주신 블로거분이 있어서 참고하면 좋을거 같다. (shoark7.github.io/programming/algorithm/tower-of-hanoi) 규칙은 쉬우나 문제는 법칙을 찾는게 어렵다는 것이다. 그래서 3을 기준으로 어떻게 옮기는지 보면 몇가지 방식으로 규칙을 찾을수 있다. 완벽히 이해한게 아니라 설명이 어려운데..... 1. 3을 A->C로 옮기는 경우 2. 1,2를 A->B로 옮겨야한다.(2를 A->B로 옮기는 재귀함수) 3. 3을 A->C로 옮겨야한다.(1개만 옮겨도 되기 때문에 재귀가 필요없다.) 4. 1,2를 ..

백준 9020 풀이 (골드바흐의 추측 )

이번에는 "골드바흐의 추측"이라고 한다. 솔직히 난 문과출신이라 이런거 정의 보면 살짝 불편하다ㅋㅋㅋㅋ 그래도 정의가 어렵지는 않다. 큰 짝수는 반드시 두 소수로 나타낼 수 있다는 소리다. 그래서 N값에 대해서 두 소수를 구하면된다. 단, 두 소수의 차이가 가장 작아야한다. 그래서 시나리오를 짜봤다. 1. 소수리스트를 먼저 구한다.("에라토스테네스의 체"를 활용한다. 저번 포스팅에 이런방식으로 푸는 고수들이 있길래 따라했다.) 2. 짝수는 나누었을때 소수를 바로 가질수도 있고 하나씩 줄여가며 구해야할수도 있다. 3. 빼고자 하는 수가 소수인지, 뺀후에도 소수인지 판별한다. 4. 둘다 소수이면 출력 여기서 포인트는 빼고자 하는 수를 N/2부터 비교해서 빼기 시작한다는 것이다. line 13 def isPr..

백준 1929 풀이 (에라토스테네스의 체)

음 처음에 알고리즘 이름이 너무 길어서 쫄았다. 그래서 검색을 통해 알아보니 소수를 구하기 위한 방식이었다. 1. N 을 나눌경우 몇까지 나눌수 있는지 구한다. => Max_division = N ** 0.5 2. N을 2~Max_division까지 나누면서 떨어지는지 판별한다. 3. 만약 N과 값이 같거나 나누어 떨어지지 않으면 소수로 판별한다. 문제는 어떻게 풀어도 시간초과로 뜬다. 그래서 다른 사람들 풀이를 보니 함수로 만들어서 식을 더 최소화 시키는 방법을 적용하는 것을 알게되었다. a,b = map(int,input().split()) for val in range(a,b+1): flag = 1 for i in range(2,int(val ** 0.5)+1): if val == 1: flag =..

백준 2775 풀이

나한테 만큼은 어려웠다. 대강 규칙은 알았지만 이걸 어떻게 코드로 나타내야 하는지 상당히 고민을 많이 했다. 이미 식은 어떻게 짜야하는지 나와있었지만 이게 연산을 통해 뚝딱나오는지 아니면 차례대로 하나씩 계산해서 뽑아야하는지 고민하는 시간이 길었다. 결론적으로 구하는 방법은 그대로 하나씩 다 구하는 방법밖에 없었다. 그래서 한 층마다 값을 구하여 원하는 호의 값을 뽑는 방법으로 진행했다. n = int(input()) for _ in range(n): floor = int(input()) room = int(input()) pl = [i for i in range(1,room+1)] # 0층을 구함. for _ in range(floor): for i in range(1,room): pl[i] += pl..

백준 1193 풀이

기존에 코드를 작성했지만 [1,1]부터 차례로 하나씩 증가시키며 동작하도록 만들었다. 문제가 없다고 판단했지만 제출시에 시간초과가 떴다. 그래서 좀더 빠르게 타겟의 값을 가져오는 방법을 고민했다. 그래서 생각한것이 타겟에 가까운 인덱스를 빠르게 찾고, 해당 블럭안에서 값을 찾는 방법이다. 즉, 1/1 -> 1/2 -> 2/1 -> 3/1 -> 2/2 -> 1/3 -> 1/4 -> 2/3 -> 3/2 -> 4/1을 블록단위로 나눌수 있다. 즉, (1/1) -> (1/2 -> 2/1) -> (3/1 -> 2/2 -> 1/3) -> (1/4 -> 2/3 -> 3/2 -> 4/1) 따라서 해당 블록이 몇 번째인지 파악하는 식을 구해야한다. 솔직히 문과라서 동작과정은 이해했는데 식으로 짜기가 오래걸렸다........