Contents
-
파이썬 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 = ..
-
여러 iterable 객체를 묶어주는 zip 내장함수Python 2021. 7. 2. 17:21
여러 개의 iterable 객체의 요소들을 순서대로 하나씩 묶어주고 싶은 경우가 있을 수 있다. 예를 들어 다음과 같이 두 개의 리스트를 순서대로 각각 쌍으로 묶고자 하는 경우 어떻게 해야 할까? list1 = [1, 2, 3] list 2 = ['A', 'B', 'C'] --> result = [(1, 'A'), (2, 'B'), (3, 'C')] 이럴 때 사용할 수 있는 함수가 zip이다. zip을 사용하면 간단하게 여러 개의 iterable 객체의 요소들을 순차적으로 튜플 자료형으로 묶어준다. list1 = [1, 2, 3] list2 = ['A', 'B', 'C'] for elem in zip(list1, list2): print(elem) 위의 소스코드를 실행하면 zip 함수를 통해 생성된 zi..
-
for ~ else 문Python 2021. 7. 2. 16:06
for loop를 중간에 탈출하지 않고 완료한 경우에 한해 실행되는 구문이 필요할 수 있다. 다음과 같이 내부에 마지막 반복을 확인하는 구문을 두고 만족하는 경우 실행되도록 하는 방법을 생각해볼 수 있다. data = [1, 2, 3, 4, 5] for i in range(len(data)): print(data[i]) if i == len(data) - 1: print('반복문이 종료되었습니다.') 이를 for ~ else 구문을 통해 다음과 같이 보다 간단하게 표현할 수 있다. data = [1, 2, 3, 4, 5] for i in range(len(data)): print(data[i]) else: print('반복문이 종료되었습니다.') for ~ else 구문 실행 중 loop가 완료되기 전에..
-
로지텍 keys to go 사용기ETC 2021. 6. 27. 09:32
" 매우 가볍고 콤팩트 하지만, 좋지 않은 키감의 미니 무선 키보드" 기존에 본인이 사용하던 블루투스 키보드는 애플 매직키보드2였다. 그러던 중 2018년에 하남 스타필드의 가전제품 판매 매장을 기웃거리다 우연히 귀엽고 동그란 키캡의 장난감 느낌이 나는 K380을 접하게 되었다. 별 기대감 없이 키를 두드려 보았는데 이게 생각보다 키감이 상당히 좋아서 이미 사용 중인 매직키보드2가 있었음에도 바로 구매하게 되었다. 가격도 3만 원 중반대로 착한 편이었기에 부담 없이 지를 수 있었던 거 같다. 시간이 지나 로지텍에서 신형 블루투스 키보드인 key to go를 발매했지만 코로나 시기라 직접 타건 해볼 만한 곳이 없어 아쉬웠다. keys to go는 애플스토어 기준 K380의 두배가 넘는 79,000원으로 구..
-
위상정렬(topological sort)Data Structure & Algorithm 2021. 5. 31. 15:28
[위상정렬] 위상정렬에서의 위상(位相)은 사전적 의미로 어떤 사물이 다른 사물과의 관계 속에서 가지는 위치나 상태이다. 위상정렬은 영어로 topological sort인데 topological란 위상배치적인 이라는 뜻으로 구성요소간의 관계를 고려하여 배치한다는 뜻이다. 여기서 키워드는 관계이다. 노드 간의 관계(방향을 가진 간선)를 고려하여 방향성에 거스르지 않게 모든 노드를 나열하여 데이터를 정렬하는 것을 말한다. [위상정렬 알고리즘] 방향 그래프에서 각 노드로 들어오는 간선의 수를 "진입 간선 수"라 할 때 모든 노드별로 진입 간선 수를 저장한다. 진입 간선 수가 0개인 노드를 queue에 넣는다. queue가 비워진 상태일 때까지 다음을 실행한다. queue에서 dequeue하여 노드를 하나 꺼내고..
-
최소신장트리를 구하기 위한 쿠르스칼 알고리즘 (Kruskal's algorithm for Minimum Spanning Tree)Data Structure & Algorithm 2021. 5. 26. 14:26
[신장트리의 의미] 신장트리에서 신장(身長)은 사전적으로 머리 끝에서 발 끝까지라는 의미이다. 어느 정점에서 시작하더라도 트리의 모든 leaf까지 도달할 수 있기 때문에 신장트리라고 명명한 것이 아닌가 생각된다. 영어로는 spanning tree인데 spanning의 의미는 '걸쳐서 이어진'이다. 즉, 트리 구조 특성상 순환이 발생하지 않으며 모든 노드가 이어진 부분 그래프를 신장트리라고 한다. [최소신장트리 (Minimum Spanning Tree)] 신장트리 가운데 모든 간선 비용의 합이 최소인 것을 최소신장트리라고 한다. 최소신장트리는 네트워크, 도로건설, 배관, 전기회로 등의 최적화에 활용할 수 있다. [서로소 집합과 무방향 그래프의 순환 발생 여부 확인] 그래프에서 최소신장트리를 구하려면 순환을..
-
플로이드워셜(Floyd–Warshall) 알고리즘Data Structure & Algorithm 2021. 5. 12. 16:32
플로이드워셜 알고리즘은 각 정점에서 다른 모든 정점까지의 최단경로를 구할 수 있는 알고리즘이다. 기본적인 아이디어는 노드 A에서 노드 B로 이동에 필요한 비용과 노드 T를 경유하는 즉 노드 A -> 노드 T -> 노드 B 순으로 이동했을 때의 비용을 비교하여 노드 T를 경유한 경우의 비용이 작으면 A -> B 이동 비용을 작은 값으로 변경하는 것이다. 플로이드워셜 알고리즘의 점화식 cost(A, B)를 노드 A에서 노드 B로 이동하는 비용 이라 하고 T를 경유하는 노드라 할 때 cost(A, B) = min(cost(A, B), cost(A, T) + cost(T, B)) 플로이드워셜 알고리즘의 시간복잡도 노드의 개수를 N이라 할 때, 1 ~ N 노드는 모두 경유 노드가 될 수 있다. 경유 노드를 제외한..
-
다익스트라(Dijkstra) 알고리즘Data Structure & Algorithm 2021. 5. 6. 16:36
N개의 정점과 M개 간선으로 이뤄진 그래프가 있다고 하자. 이때 N개의 정점 중 하나를 시작점으로 하여 나머지 N - 1개의 정점들까지의 최단거리 경로를 구하는 알고리즘 중 하나가 다익스트라 알고리즘이다. (참고: 간선 가중치가 없는 그래프의 최단거리 경로는 BFS를 통해 구할 수 있다.) 다익스트라 알고리즘은 간선에 가중치가 있는 방향 그래프에서 최단거리 경로를 구하기 위해 사용한다. 따라서 만약 방향 그래프가 아니라면 하나의 간선에 대해 양방향으로 이어지는 방향 그래프로 변환해야 한다. 즉, 무방향 그래프로 데이터가 주어지는 경우 그래프를 인접 리스트 형태로 만들어줄 필요가 있다. 이후 가중치의 표현은 w(A, B)라 하자. 의미는 정점 A에서 정점 B로 이동하는 가중치이다. 단, 가중치가 음수인 간..