코테 정리 및 공부

기본 문법

- 진수 & 알파벳과 정수

# 16진수 변환
int(a, 16)

# 알파벳의 정수값
ord(x)

# 정수의 알파벳 값
chr(x)

 

- 반올림 값

print( format(x, ".2f") )

 

- 최대공약수와 최소공배수

import math

# 최대공약수
math.gcd(a,b)

# 최소공배수
(a * b) // math.gcd(a,b)

 

- i 부터 j 까지의 원소를 역순으로 변경

my_list[i:j+1] = reversed(my_list[i:j+1])

 

- exception 처리

try:
	# ...
except:
	# ...

 

- 삼항

(true logic) if (조건문) else (false logic)

 

- replace 키워드 ( 재저장해야한다 )

# 공백제거
replaced_a = a.replace(' ', '')

 

- 최소값과 최대값

min_value = 1e9
max_value = -1e9

...
min_value = min(min_value, now)
max_value = max(max_value, now)

 

- 람다 표현식

lambda arguments: expression

words = ["apple", "banana", "cherry", "date"]
words.sort(key=lambda word: len(word))
print(words)  # 출력: ['date', 'apple', 'banana', 'cherry']

 

- sort의 key 속성

'''
[정렬 기준]
1) 두 번째 원소를 기준으로 내림차순 정렬
2) 두 번째 원소가 같은 경우, 세 번째 원소를 기준으로 오름차순 정렬
3) 세 번째 원소가 같은 경우, 네 번째 원소를 기준으로 내림차순 정렬
4) 네 번째 원소가 같은 경우, 첫 번째 원소를 기준으로 오름차순 정렬
'''
students.sort(key=lambda x: (-int(x[1]), int(x[2]), -int(x[3]), x[0]))

    ㆍsort() 함수의 key 속성에 값을 대입하여 내가 원하는 '조건'에 맞게 튜플을 정렬시킬 수 있다는 점.

 

* 내가 생각하는 2차원 xy 좌표계가 아니라 xy가 바꼈다고 생각하자!!

# 2차원 리스트 선언
result = [[0] * 열수 for _ in range(행수)]

- N X M 크기의 2차원 리스트 초기화

array = [[0] * m for _ in range(n)]

 

- deque.rotate(x)

queue = deque(_list)

# x가 음수 일때는 맨앞값을 맨뒤로
# x가 양수 일때는 맨뒤값을 맨앞으로
queue.rotate(x)

 

- math.sqrt 는 float로 나온다! 주의할 것!

- 원 문제는 큐(queue)로 풀기

- 리스트보다는 딕셔너리가 더 빠르다.

 

---

이진탐색(이분탐색)

- 파이썬 이진 탐색 라이브러리

    ㆍbisect_left(a, x) : 정렬된 순서를 유지하면 배열 a에 x를 삽입할 가장 왼쪽 인덱스를 반환

    ㆍbisect_right(a, x) : 정렬된 순서를 유지하면서 배열 a에 x를 삽입할 가장 오른쪽에 인덱스를 반환

from bisect import bisect_left, bisect_right

a = [1,2,4,4,8]
x = 4

print(bisect_left(a, x))	# 2
print(bisect_right(a, x))	# 4

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    
    return right_index - left_index

- 이진탐색 소스 코드 (재귀)

def binary_search(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    
    # 찾은 경우 중간점 인덱스 반환
    if array[mid] == target:
        return mid
        
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)
        
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return binary_search(array, target, mid + 1, end)

- 이진탐색 소스 코드 (반복문)

def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        # 찾은 경우 중간점 인덱스 반환
        if array[mid] == target:
            return mid

        # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
        elif array[mid] > target:
            end = mid - 1

        # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
        else:
            start = mid + 1
    return None

 

---

DFS & BFS

- dfs (깊이 우선 탐색)

def dfs(graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

- bfs (너비 우선 탐색)

from collections import deque

# bfs 메서드 정의
def bfs(graph, start, visited):
    # 큐(Queue) 구현을 위해 deque 라이브러리 사용
    queue = deque([start])
    
    # 현재 노드를 방문 처리
    visited[start] = True
    
    # 큐가 빌 때까지 반복
    while queue:
        # 큐에서 하나의 원소를 뽑아 출력하기
        v = queue.popleft()
        print(v, end=' ')
        
        # 아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

* 모든 부분이 탐색될 시 DFS보단 BFS 추천!

* 그래프에서 모든 간선의 비용이 동일할 때는 너비 우선 탐색(BFS)을 이용해서 최단 거리를 찾을 수 있다.

 

---

순열과 조합

- r개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열)를 계산

from itertools import permutations

data = ['A', 'B', 'C']
result = list(permutations(data, 3))	# 모든 순열 구하기

print(result)
# [('A','B','C'),
#  ('A','C','B'),
#  ('B','A','C'),
#  ('B','C','A'),
#  ('C','A','B'),
#  ('C','B','A')]

- r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우(조합)을 계산

from itertools import combinations

data = ['A', 'B', 'C']
result = list(combinations(data,2)) # 2개를 뽑는 모든 조합 구하기

print(result)	# [('A','B'), ('A','C'), ('B','C')]

- r 개의 데이터를 뽑아 일렬로 나열하는 모든 경우(순열)를 계산한다. 다만 원소를 중복하여 뽑는다.

from itertools import product

data = ['A', 'B', 'C']
result = list(product(data, repeat=2))	# 2개를 뽑는 모든 순열 구하기(중복허용)

 

---

최단 경로

- 다익스트라 알고리즘 ( 우선순위 큐 사용 X )

import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
visited = [False] * (n + 1)
distance = [INF] * (n + 1)

for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a].append((b,c))

def get_smallest_node():
    min_value = INF
    index = 0
    for i in range(1, n+1):
        if distance[i] < min_value and not visited[i]:
            min_value = distance[i]
            index = i
    return index

def dijkstra(start):
    distance[start] = 0
    visited[start] = True
    for j in graph[start]:
        distance[j[0]] = j[1]
    for i in range(n-1):
        now = get_smallest_node()
        visited[now] = True
        
        for j in graph[now]:
            cost = distance[now] + j[1]
            if cost < distance[j[0]]:
                distance[j[0]] = cost

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

- 다익스트라 알고리즘 ( 우선순위 큐 사용 O )

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

n, m = map(int, input().split())
start = int(input())
graph = [[] for i in range(n+1)]
distance = [INF] * (n+1)

for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a].append((b,c))

def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))

dijkstra(start)

for i in range(1, n+1):
    if distance[i] == INF:
        print("INFINITY")
    else:
        print(distance[i])

- 플로이드 워셜 알고리즘

    ㆍO(N^3)

    ㆍ노드 수의 500개 이하될 때 사용

INF = int(1e9)

n = int(input())
m = int(input())
graph = [[INF] * (n + 1) for _ in range(n + 1)]

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0

for _ in range(m):
    a,b,c = map(int, input().split())
    graph[a][b] = c

for k in range(1, n + 1):
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if graph[a][b] == INF:
            print("INFINITY", end=" ")
        else:
            print(graph[a][b], end=" ")
    print()

---