분류 전체보기

백준 14888 풀이 (재귀함수, 백트래킹, 연산자 끼워넣기)

일단 혹시나 내 코드를 보시는 분은 내가 아직도 백트래킹을 이해를 못한 관계로 코드만 참고하면 좋겠다. 일단 한방에 성공하긴 했으나 아직도 재귀와 백트래킹이 두려운 시점이라 일단 재귀로 대충짜봤다. 1. 주어진 값들을 리스트와 연산자 맵을 재귀함수로 사용한다. 2. 리스트의 0번째와 1번째를 연산자 맵에서 하나꺼내서 사용한다. 3. 반복하다가 연산자 맵이 전부 0이면(sum이 0이면) 종료하고 전체 리스트에 넣어준다. n = int(input()) nlist = list(map(int,input().split())) Map = list(map(int,input().split())) Tmp = [] def back(nlist, miniMap): if len(nlist) == 1: Tmp.append(nli..

백준 9663 풀이 (백트래킹, 재귀함수)

사실 어제 풀다가 안풀려서 포기했다. 어제 짠 코드는 모든 경우를 다 확인하다보니 시간도 오래걸리고, 무엇보다 중복이 생겼다. 그래서 그냥 시원하게 던져버리고 오늘 다시 풀어보았다. 오늘은 접근을 달리했다. N * N개의 판에서 퀸이 4개가 들어가야한다고 하는데 이는 결국 각 행마다 퀸이 딱 하나씩 들어가야한다는 소리다. 즉, 무조건 배열이 [[0,?], [1,?], [2,?], [3,?] ......[n-1,?]] 이런 방식이면 되는거다. 따라서 이를 토대로 코드를 짰다. N = int(input()) sum = 0 def queen(tlist,n): global N global sum if len(tlist) == N: sum+=1 return for i in range(N): check = 0 fo..

백준 15650 풀이 (재귀함수)

저번에 풀었던 15649문제에서 코드를 살짝만 수정하면 쉽게 구할수 있다. 조건은 뒤에 수열이 반드시 오름차순이어야하며 중복을 포함하지 않는다. 코드의 중복이 살짝 있지만 애교로 넘어가자 n,m = map(int,input().split()) Map=[i for i in range(1,n+1)] def back(tlist, n,m): if m == 0: for i in tlist: print(Map[i],end=' ') print() return for i in range(n): if len(tlist) == 0: tlist.append(i) back(tlist,n,m-1) tlist.pop() else: if i > tlist[-1]: tlist.append(i) back(tlist,n,m-1) tli..

백준 15649 풀이 (재귀함수, 백트래킹)

음 백트래킹이 먼지 몰랐다. 그래서 여기저기 기웃거려본 결과 트리를 만들때 불필요한걸 쳐내면서 트리를 만드는거 같다. 물론 이 문제에 백트래킹을 어떻게 적용해야하는지 전혀 이해못했다. 그냥 재귀함수로 적용해서 풀어보자! 라는 마인드로 풀었는데 어찌저찌 풀리긴 풀렸다. 순서는 다음과 같다. 1. 빈 리스트, n, m을 인자로 넣어준다. 2. for 을 이용하여 사용되지 않은 숫자를 리스트에 추가하며 재귀함수를 실행시킨다. 3. m을 하나씩 줄여서 m이 0이 되면 리스트에 저장된 값을 출력해준다. n,m = map(int,input().split()) Map=[i for i in range(1,n+1)] def back(tlist, n,m): if m == 0: for i in tlist: print(Map..

백준 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이다. 이 함수를 사용하면 가장 ..

#4 알고리즘 공부 2/12 리뷰

2/6 19문제 2/7 11문제 2/8 9문제 2/10~12 12문제 총 51문제 중간에 하노이문제랑 재귀문제가 정말 나의 멘탈을 탈탈 털어갔다. 재귀가 왜이렇게 어려운지 모르겠다. 일단 현재까지 50문제를 풀었다. 앞으로 이번달이 끝나기 전에 100문제를 찍어야하다. 그래야 해쉬테이블이나 그리디나 어려운 문제에 접근 가능할거 같다. 졸라 꾸준히 하자

백준 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로 해야했다.