낙타선생 놀이터 낙타선생 놀이터

Data Structure & Algorithm

• [프로그래머스] 프린터

  Data Structure & Algorithm 2021. 9. 5. 16:38

  [문제] 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr [풀이] 처음 문제를 접하고 우선순위라는 키워드 때문에 priority queue를 사용하는 문제일 것으로 생각했으나, 요구사항을 확인한 결과 항상 최선의 priority를 찾아 pop 하는 priority queue와는 다른 동작이 필요했다. 문제의 요구사항을 정리해보면 다음과 같다. while queue가 비어있지 않을 동안 if queue[0]가 가장 우선순위가 높은 출력물이면 then queue[0]를 popleft한다. 카운터를 1 증가 시킨다. ..

  Read More

• Circular Buffer with Python

  Data Structure & Algorithm 2021. 9. 4. 11:10

  circular buffer의 데이터를 저장할 공간을 list를 사용하여 확보한다. 데이터의 시작점(front)와 끝점(rear)을 각각 0으로 설정한다. 데이터가 삽입될 때는 rear에 1을 더해주고 rear % 저장공간의_길이에 해당하는 인덱스에 저장한다. 데이터를 삭제할 때는 front에 1을 더해주고 front % 저장공간의_길이 에 해당하는 인덱스의 값을 되돌려준다. front == rear 이면 circular buffer가 비어있는 것이다. front == (rear + 1) % 저장공간의_길이 이면 circular buffer가 가득 찬 것이다. class CircularBuffer: def __init__(self, k: int): self.q_len = k + 1 self.front =..

  Read More

• 2차원 리스트 테두리만 회전 시키기

  Data Structure & Algorithm 2021. 8. 30. 13:20

  2차원 리스트에서 두 점을 기준으로 만들 수 있는 사각형이 있다고 할 때 사각형 테두리에 해당하는 원소들만 시계방향 또는 반시계 방향으로 한 칸씩 밀어낸 후 반환하는 함수를 작성해본다. tgt_list: 원본 list pt_a: 사각형 꼭지점 1에 해당하는 튜플 (y, x) pt_b: 사각형 꼭지점 2에 해당하는 튜플 (y, x) 0

  Read More

• 소수판별 알고리즘

  Data Structure & Algorithm 2021. 8. 16. 14:09

  [자연수 n이 소수인지 판별하는 알고리즘]소수의 정의는 2 이상의 자연 수 중 1과 자신만을 약수로 가지는 수이다.따라서 자연수 n이 소수인지 확인하기 위해서는 n을 2부터 n - 1까지의 수로 나눠서 떨어지는 경우가 있는지를 확인하면 된다. 이렇게 할 경우 알고리즘의 시간복잡도가 O(n²)이 된다.자연수의 약수에 대한 규칙을 살펴보면 연산 횟수를 줄일 수 있음을알 수 있다. 16의 약수를 오름차순으로 정리해보면 다음과 같다.16의 약수 = {1, 2, 4, 8, 16}이 약수들을 곱연산 한 결과가 16이 되는 경우는 아래와 같다.1 * 16 = 162 * 8 = 164 * 4 = 168 * 2 = 1616 * 1 = 16 1 * 16 과 16 * 1 그리고 2 * 8과 8 * 2 은 순서만 뒤바뀐 채 ..

  Read More

• 1부터 순서대로 값을 채운 N * N 2차원 리스트

  Data Structure & Algorithm 2021. 8. 15. 14:09

  1 ~ N * N 값을 순차적으로 넣어준 N * N 크기의 2차원 리스트를 작성하는 방법은 다음과 같다. N = 1000 my_list = [] for i in range(1, N * (N - 1) + 2, N): my_list.append([j for j in range(i, i + N)])

  Read More

• 파이썬 2차원 리스트 회전 (How to rotate 2D list on Python)

  Data Structure & Algorithm 2021. 7. 20. 09:31

  1. 회전 각도(90도, 180도, 270도)를 파라메터로 받아 회전된 2차원 리스트를 반환하는 함수 2. zip을 활용한 90도 회전된 2차원 리스트 반환 함수 (very simple ans faster than 1) [회전 각이 추가된 2차원 리스트 회전 함수] 나동빈 님의 이코테로 알고리즘을 공부하던 중 2차원 리스트를 회전시키는 코드를 보고 원하는 각도를 지정하여 회전시키면 더 효율적일 수 있을 것 같다는 생각이 들어 다음과 같이 각도에 해당하는 매개 값을 지정하여 2차원 list를 회전시키는 코드를 작성해 보았다. 첫 번째 매개 값 tgt_list에는 회전시킬 2차원 list를 지정한다. 두 번째 매개 값 angle은 회전할 각도를 지정한다. angle = 1 --> 90도 회전 angle = ..

  Read More

• 위상정렬(topological sort)

  Data Structure & Algorithm 2021. 5. 31. 15:28

  [위상정렬] 위상정렬에서의 위상(位相)은 사전적 의미로 어떤 사물이 다른 사물과의 관계 속에서 가지는 위치나 상태이다. 위상정렬은 영어로 topological sort인데 topological란 위상배치적인 이라는 뜻으로 구성요소간의 관계를 고려하여 배치한다는 뜻이다. 여기서 키워드는 관계이다. 노드 간의 관계(방향을 가진 간선)를 고려하여 방향성에 거스르지 않게 모든 노드를 나열하여 데이터를 정렬하는 것을 말한다. [위상정렬 알고리즘] 방향 그래프에서 각 노드로 들어오는 간선의 수를 "진입 간선 수"라 할 때 모든 노드별로 진입 간선 수를 저장한다. 진입 간선 수가 0개인 노드를 queue에 넣는다. queue가 비워진 상태일 때까지 다음을 실행한다. queue에서 dequeue하여 노드를 하나 꺼내고..

  Read More

• 최소신장트리를 구하기 위한 쿠르스칼 알고리즘 (Kruskal's algorithm for Minimum Spanning Tree)

  Data Structure & Algorithm 2021. 5. 26. 14:26

  [신장트리의 의미] 신장트리에서 신장(身長)은 사전적으로 머리 끝에서 발 끝까지라는 의미이다. 어느 정점에서 시작하더라도 트리의 모든 leaf까지 도달할 수 있기 때문에 신장트리라고 명명한 것이 아닌가 생각된다. 영어로는 spanning tree인데 spanning의 의미는 '걸쳐서 이어진'이다. 즉, 트리 구조 특성상 순환이 발생하지 않으며 모든 노드가 이어진 부분 그래프를 신장트리라고 한다. [최소신장트리 (Minimum Spanning Tree)] 신장트리 가운데 모든 간선 비용의 합이 최소인 것을 최소신장트리라고 한다. 최소신장트리는 네트워크, 도로건설, 배관, 전기회로 등의 최적화에 활용할 수 있다. [서로소 집합과 무방향 그래프의 순환 발생 여부 확인] 그래프에서 최소신장트리를 구하려면 순환을..

  Read More