드롱드롱

다익스트라 알고리즘을 본격적으로 공부해보기 전에 우선순위 큐에 관련된 문제를 조금 더 풀어보고 시작해보도록 하자  * 우선순위 큐와 관련된 문제풀이 1. 29160 : 나의 FIFA 팀 가치는?https://www.acmicpc.net/problem/29160 import sysinput = sys.stdin.readlinefrom heapq import heappush, heappopN, K = map(int,input().split())hq = [[0] for _ in range(12)]for _ in range(N): p, w = map(int,input().split()) heappush(hq[p],-w)for _ in range(K): for i in range(1,12): ..

1. BFS(Breadth-First Search : 너비 우선 탐색)* 너비 우선 탐색, 그래프에서 인접한 노드를 우선적으로 탐색하는 방법 bfs는 선입선출 방식을 사용하기 때문에 queue를 이용했을 때 효과적이다. 그러나 bfs는 모든 노드를 방문해야하기 때문에 visited 배열을 사용해 방문 여부를 한 번 체크해 갔던 노드는 다시 방문하지 않도록 하는 것이 핵심이다.    [Python/코딩테스트] 코딩테스트 완전정복 ① - BFS 너비우선탐색[Python/코딩테스트] 코딩테스트 완전정복 ① - BFS 너비우선탐색velog.io 너무 잘 설명된 글이기에 가져와 보았다.  list1 = [[1]*8]print(list1) # [[1, 1, 1, 1, 1, 1, 1, 1]] list2 = [[1]..

1. 스택(Stack)후입선출 구조로써 한쪽 구멍만 있는 통 안에 물건을 집어넣고 빼는 형식이다.   * 관련 문제1. 1874 : 스택 수열https://www.acmicpc.net/problem/1874 import sysinput = sys.stdin.readlinecount = 1temp = Trueop = []stack = []for i in range(int(input())): n = int(input()) while n>=count: stack.append(count) count += 1 op.append('+') if stack[-1] == n: op.append('-') stack.pop() els..

*  이진탐색(Binary Search) 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이진 탐색은 "정렬된 리스트"에서 특정 값의 위치를 찾는다. 항상 이진 탐색을 할 때는 리스트를 정렬된 상태로 진행해야 함에 유의할 것!!  -> 반복문과 재귀 두 가지 방법을 사용할 수 있다.1. 시간복잡도 : O(logN)2. 자료를 오름차순으로 정렬한다.3. 자료의 중간값(mid)이 찾고자 하는 값(target)인지 비교한다.4. mid 값이 target과 다르다면 대소관계를 비교하여 탐색 범위를 좁히고, target과 mid 값이 같을 때까지 아래 조건에 따라 3번과 4번을 반복한다.           ⓐ target이 mid 값 보다 작으면 end를 mid 왼쪽 값으로 바꿔준다. (절반의 왼쪽..

* 시뮬레이션(구현) 시뮬레이션은 단순히 '구현'을 하는 유형이다.2차원 공간을 다루는 문제가 자주 나오기 때문에 방향(상,하,좌,우)에 대한 자신만의 처리 방식을 가지는게 좋고 특정 게임을 구현하는 문제들은 몇 가지 자체적인 테스트 케이스를 만들어주면 유용하다. 시뮬레이션 유형 같은 경우에는 많이 풀어보고 다른 사람들의 풀이를 참고하는 것이 좋은 공부법이라고 하니, 양치기로 한번 부딪혀보자.   1. 25966 : 배찬우는 배열을 좋아해https://www.acmicpc.net/problem/25966  import sysinput = sys.stdin.readlinen,m,q = map(int, input().split())list1 = []for _ in range(n): list1.appen..

본격적으로 이번주차 공부를 시작하기 전에 그 전 주의 피드백을 진행해야 될 것 같다. 일단 가장 큰 문제는 내가 알고리즘 공부를 잘못하고 있었다는 것이고, 제대하고 나서 오랜만에 코딩을 한다고 해도 저번주는 코딩에 시간을 많이 쏟지 못한 부분인 것 같다. 잘못 공부한다는 것은 많이 고민하지 않고 잘모르겠으면 일단 솔루션을 계속 외우는 식의 공부를 했는데, 그 문제만 맞추고 다른 유형의 새로운 문제를 봤을 때 창의적으로 문제를 해결하는 능력이 떨어진다는 것을 알게 되었다. 또한 재귀함수가 너무 어렵고 내가 잘 못다룬다는 것도. 따라서 이번주부터는 모르는 문제는 구글을 통해 솔루션을 보고 암기를 하되, 배우는 유형에 대해서 이런 부분에서 이런 알고리즘을 이용해야 겠다는 생각을 해야하며 그 이후에 풀이 과정들..

코알라 1주차 브루트 포스 관련 예제에서 시간 복잡도를 해결하기 위해 딕셔너리를 사용했는데 "defaultdict"라는, 내가 처음보는 자료구조를 만나게 되었다. 시간복잡도 문제를 해결하기 위해선 list보다 dictinary를 사용하는 것이 바람직한 경우가 많은데, defaultdict를 사용하면 조금 더 편리하게 dictionary 자료구조를 이용할 수 있기에 관련된 문제와 함께 개념을 이해해보았다.   1. defaultdict란?형태는 dictionary와 마찬가지로 [key:value]로 구성이 되는데 그냥 dictionary와 다른점은 이름에도 나와있듯이 디폴트 값을 미리 정해주는 dictionary를 만드는 것이다.  사용하는 법은 매우 간단한데,from collections import d..