📌정렬 라이브러리 sorted(), sort()sorted() 함수최악의 경우에도 시간 복잡도 O(NlogN) 보장리스트, 딕셔너리 자료형 등을 입력받아서 정렬된 결과를 출력집합 자료형이나 딕셔너리 자료형을 입력받아도 반환되는 결과는 리스트 자료형array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]result = sorted(array)print(result) sort() 함수리스트 변수 하나만 있을 때 내부 원소를 바로 정렬리스트 객체의 내장 함수별도의 정렬된 리스트를 반환하지 않음array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]array.sort()print(array) 📌sorted(), sort() 사용 시 key 매개변수key값으로는 하나의 함수가 들어가야..
📌heapq다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용파이썬의 힙은 최소 힙으로 구성(최소힙: 최상단 원소가 항상 가장 작은 원소)단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료 📌heapq 메서드heapq.heappush(): 힙에 원소 삽입heapq.heappop(): 힙에서 원소 꺼냄 📌힙 정렬을 heapq로 구현하는 코드import heapqdef heapsort(iterable): h = [] # 힙 result = [] # 결과 리스트 # 모든 원소를 차례대로 힙에 삽입 for value in iterable: heapq.heappush(h,..
📌함수똑같은 코드가 반복적으로 사용되어야 할 때 함수를 사용함수를 작성할 때 함수 내부에서 사용되는 변수의 값을 전달받기 위해 매개변수 정의할 수 있음어떠한 값을 반환하고자 할 때는 return 사용매개변수나 return은 존재하지 않을 수도 있음(선택) 📌global 키워드함수 안에서 함수 밖의 변수 데이터를 변경해야 할 때 사용global 키워드로 변수를 지정하면 해당 함수에서는 지역 변수를 만들지 않고 함수 바깥에 선언된 변수를 바로 참조a = 0def func(): global a a += 1for i in range(10): func()print(a) 📌람다 표현식함수를 매우 간단하게 작성하는 방법한 줄로 작성 가능def add(a, b): return a + b# 일..
📌리스트여러 개의 데이터를 연속적으로 담아 처리하기 위해 사용파이썬의 리스트 자료형은 배열(Array)을 채택append(), remove() 등 메서드 지원 📌리스트 컴프리헨션리스트를 초기화하는 방법 중 하나대괄호 [] 안에 조건문과 반복문을 넣는 방식으로 리스트 초기화# 0부터 19까지의 수 중에서 홀수만 포함하는 리스트array = [i for i in range(20) if i % 2 == 1]print(array) 2차원 리스트를 초기화할 때 효과적으로 사용# N x M 크기의 2차원 리스트 초기화n = 3m = 4array = [[0] * m for _ in range(3)]print(array) 📌언더바의 역할반복을 수행하되 반복을 위한 변수의 값을 무시하고자 할 때 언더바 사용for ..
📌계수 정렬특정한 조건이 부합할 때만 사용할 수 있는 매우 빠른 정렬 알고리즘데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때만 사용 가능일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 효과적 계수 정렬에서는 모든 범위를 담을 수 있는 크기의 리스트(배열)를 선언해야 함 선택, 삽입, 퀵 정렬처럼 직접 데이터의 값을 비교한 뒤에 위치를 변경하며 정렬하는 방식이 아님 데이터의 크기가 제한되어 있다면 데이터 개수가 많더라도 빠르게 동작 정렬 방식1. 가장 작은 데이터부터 가장 큰 데이터까지 모두 담길 수 있도록 하나의 리스트를 생성2. 리스트의 모든 데이터가 0이 되도록 초기화3. 데이터를 하나씩 확인하며 데이터의 값과 동일한 인덱스의 데이터를 1씩 증..
📌퀵 정렬가장 많이 사용되는 정렬 알고리즘기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작 피벗: 큰 수와 작은 수를 교환할 때 교환하기 위한 기준퀵 정렬을 수행하기 전 피벗을 어떻게 설정할 것인지 미리 명시 피벗을 설정하고 리스트를 분할하는 가장 대표적인 방식: 호어 분할 방식1. 리스트에서 첫 번째 데이터를 피벗으로 정한다.2. 왼쪽에서부터 피벗보다 큰 데이터를 찾고, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.3. 큰 데이터와 작은 데이터의 위치를 서로 교환하는 것을 반복한다.4. 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈린 경우, 작은 데이터와 피벗의 위치를 교환한다.5. 분할 완료: 피벗을 기준으로 피벗 왼쪽에는 피벗보다 작은 데이..
📌삽입 정렬특정한 데이터를 적절한 위치에 삽입삽입 정렬은 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬 되어 있을 때 효율적선택 정렬은 현재 데이터의 상태와 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸어서 비효율적 삽입 정렬은 특정한 데이터가 적절한 위치에 들어가기 이전에, 그 앞까지의 데이터는 이미 정렬되어 있다고 가정 삽입 정렬은 두 번째 데이터부터 시작, 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단삽입하는 과정을 N-1번 반복하게 되면 모든 데이터가 정렬(첫 번째 데이터는 이미 정렬이므로 N번이 아닌 N-1번) 📌삽입 정렬의 특징정렬이 이루어진 원소는 항상 오름차순 유지따라서 특정한 데이터가 삽입될 위치를 정할 때(삽입될 위치를 찾기 위해 왼쪽으로 한 칸씩 이동할 때), 삽입될 데이..
📌정렬특정한 기준에 따라 데이터를 순서대로 나열하는 것 📌선택 정렬데이터가 무작위로 여러 개 있을 때, 가장 작은 데이터를 선택해서 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정 반복 매번 가장 작은 것을 선택한다 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복하면 정렬 완료마지막(N번째) 데이터는 가만히 두어도 이미 정렬된 상태 📌코드array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]for i in range(len(array)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(array)): if array[min_index] > array[..
📌문제예제 5-11 미로 탈출동빈이는 N x M 크기의 직사각형 미로에 갇혀 있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다.동빈이의 위치는 (1, 1)이고 미로의 출구는 (N, M)의 위치에 존재하며 한번에 한칸씩 이동할 수 있다.괴물이 있는 부분은 0, 괴물이 없는 부분은 1이다.이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 📌풀이(1, 1) 지점에서부터 BFS 수행시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색 📌코드from collections import dequen, m = map(int, input().split())# 2차원 리스트의 맵 정보 입력받기graph = []for i in range(n): graph.appe..
📌문제예제 5-10 음료수 얼려 먹기 문제N x M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0, 칸막이가 존재하는 부분은 1로 표시된다.구멍이 뚫려 있는 부분끼리 상, 하, 좌, 우로 붙어 있는 경우 서로 연결되어 있는 것으로 간주한다.이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오. 📌풀이얼음틀을 그래프 형태로 모델링하여 DFS로 해결1. 특정한 지점의 주변 상, 하, 좌, 우를 살펴본 뒤에 주변 지점 중에 값이 0이면서 아직 방문하지 않은 지점이 있다면 방문2. 방문한 지점에서 다시 상, 하, 좌, 우를 살펴보면서 방문을 다시 진행3. 1~2번 과정을 모든 노드에 반복하여 방문하지 않은 지점의 수를 셈 📌코드n, m = map(int, ..