코딩테스트 낙서장3

부스트캠프 웹·모바일 7기 챌린지가 내 뇌를 리셋시켰어요!!
파이썬 문법도 가물가물하네..?

이진 탐색

• 태그: 이진 탐색, 이분 탐색, Binary Search

def binarySearch(key, lst, start, end):
    if start > end:
        return -1
    
    mid = (start + end) // 2

    if lst[mid] == key:
        return mid
    
    if key < lst[mid]:
        return binarySearch(key, lst, start, mid-1)
    else:
        return binarySearch(key, lst, mid+1, end)

lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

print(binarySearch(-1, lst, 0, len(lst)-1)) # -1
print(binarySearch(3, lst, 0, len(lst)-1)) # 3
print(binarySearch(5, lst, 0, len(lst)-1)) # 5
print(binarySearch(11, lst, 0, len(lst)-1)) # -1

백트래킹

• 태그: 백트래킹, backtracking

# N과 M (1) - 실3, https://www.acmicpc.net/problem/15649

def backtracking(cnt):
    if cnt == M:
        for x in output:
            print(x, end=' ')
        print()        
        return
    
    for i in range(1, N+1):
        if checked[i] == 0:
            checked[i] = 1
            output.append(i)
            backtracking(cnt+1)
            checked[i] = 0
            output.pop()

N, M = map(int, input().split())
checked = [0] * (N+1)
output = []

backtracking(0)

DFS

• 태그: DFS, 깊이 우선 탐색, Depth First Search
• 설명: DFS로 풀게 되면 최대 100*100번의 탐색을 하게 되는데, Python의 재귀 탐색은 1000회가 최대이다.
  따라서 sys.setrecursionlimit() 함수로 재귀 제한을 풀어주었다.
  단순 탐색이면 상관없으나, 이 문제를 단순 탐색하게되면 불필요한 탐색을 할 가능성이 높다고 판단했다.
  따라서 입력을 받을 때 높이의 최소값과 최대값을 계산해 반복문을 돌렸다.
  그래프 이론, 부루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 깊이 우선 탐색

# 안전 영역 - 실1, https://www.acmicpc.net/problem/2468

import sys
sys.setrecursionlimit(10000)

# U, D, L, R
dx = [+0, +0, -1, +1]
dy = [-1, +1, +0, +0]
def in_range(x, y):
    return 0 <= x < N and 0 <= y < N

def dfs(x, y, h):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if in_range(nx, ny) and checked[nx][ny] == 0 and area[nx][ny] > h:
            checked[nx][ny] = 1
            dfs(nx, ny, h)

N = int(input())
in_min = 101
in_max = 0
area = []
for _ in range(N):
    temp = list(map(int, input().split()))
    in_min = min(min(temp), in_min)
    in_max = max(max(temp), in_max)
    area.append(temp)

safe = 1
for h in range(in_min, in_max+1):
    checked = [[0 for _ in range(N)] for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(N):
            if area[i][j] > h and checked[i][j] == 0:
                checked[i][j] = 1
                cnt += 1
                dfs(i, j, h)
    safe = max(safe, cnt)

print(safe)

BFS

• 태그: BFS, 너비 우선 탐색, Breath First Search

# 안전 영역 - 실1, https://www.acmicpc.net/problem/2468

from collections import deque

# U, D, L, R
dx = [+0, +0, -1, +1]
dy = [-1, +1, +0, +0]
def in_range(x, y):
    return 0 <= x < N and 0 <= y < N

def bfs(x, y, h):
    q = deque()
    q.append([x, y])
    checked[x][y] = 1

    while q:
        cx, cy = q.popleft()

        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]

            if in_range(nx, ny) and checked[nx][ny] == 0 and area[nx][ny] > h:
                q.append([nx, ny])
                checked[nx][ny] = 1

N = int(input())
in_min = 101
in_max = 0
area = []
for _ in range(N):
    temp = list(map(int, input().split()))
    in_min = min(min(temp), in_min)
    in_max = max(max(temp), in_max)
    area.append(temp)

safe = 1
for h in range(in_min, in_max+1):
    checked = [[0 for _ in range(N)] for _ in range(N)]
    cnt = 0
    for i in range(N):
        for j in range(N):
            if area[i][j] > h and checked[i][j] == 0:
                checked[i][j] = 1
                cnt += 1
                bfs(i, j, h)
    safe = max(safe, cnt)

print(safe)

다익스트라

• 태그: 다익스트라, dijkstra, 그래프 최단 경로, 그리드
• 특정 노드에서 다른 노드로 가는 각각의 최단 경로를 구할 때 사용, 음수를 가지는 간선이 없다.
• BFS에서는 queue(deque)를 사용하지만, 다익스트라에서는 heapq를 사용한다.
  • heapq의 정렬 기준은 오름차순(1, 2, 3, …)만을 지원한다.
  • 따라서, heapq에서 내림차순을 적용하고 싶다면 정렬의 기준이 되는 값에 -를 붙여 음수화해야 한다.

# 최단경로 - 골4, https://www.acmicpc.net/problem/1753

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

def dijkstra(k):
    q = []
    heapq.heappush(q, (0, k))

    while q:
        w, s = heapq.heappop(q)
        if dist[s] < w:
            continue

        for end_list in graph[s]:
            e, w_ = end_list

            cost = w + w_
            if cost < dist[e]:
                dist[e] = cost
                heapq.heappush(q, (cost, e))

V, E = map(int, input().split())
K = int(input())-1

graph = [[] for _ in range(V)]
for _ in range(E):
    s, e, w = map(int, input().split())
    graph[s-1].append([e-1, w])

dist = [INF for _ in range(V)]
dist[K] = 0

dijkstra(K)

for w in dist:
    print(w if w != INF else 'INF')

플로이드 워셜

• 태그: floyd warshall, 그래프 최단 경로, 다이나믹 프로그래밍, DP
• 설명: 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용

# 경로 찾기 - 실1, https://www.acmicpc.net/problem/11403

INF = int(1e9)

N = int(input())
graph = []
for _ in range(N):
    graph.append(list(map(int, input().split())))

for m in range(N):
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 1 or (graph[i][m] == 1 and graph[m][j] == 1):
                graph[i][j] = 1

for i in range(N):
    for j in range(N):
        print(graph[i][j], end=' ')
    print()

서로소 집합

• 태그: 서로소 집합, Disjoint Sets
• 설명: 서로소 집합은 공통 원소가 없는 두 집합을 의미함. union과 find 연산을 가지며, tree 자료구조를 이용하여 집합을 표현함.
  • Union(합집합) 연산을 통해 서로 연결된 두 노드 A, B를 확인한 뒤, A를 B의 부모 노드로 설정함
  • 만약 cycle이 발생하는 지 확인하려면, union_parent(parent, a) == union_parent(parent, b)가 발생하는 지 확인하면 됩니다.

# 팀 결성: 서로소 집합 알고리즘

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

N, M = map(int, input().split())
team = [i for i in range(N+1)]
answer = []
for _ in range(M):
    cmd, a, b = map(int, input().split())

    if cmd == 0:
        union_parent(team, a, b)
    else:
        if find_parent(team, a) == find_parent(team, b):
            answer.append("YES")
        else:
            answer.append("NO")

for a in answer:
    print(a)

'''
input
7 8
0 1 3
1 1 7
0 7 6
1 7 1
0 3 7
0 4 2
0 1 1
1 1 1

output
NO
NO
YES
'''

크루스칼 알고리즘

• 태그: 크루스칼 알고리즘, Kruskal Algorithm, 최소 신장 트리

# 백준: 도시 분할 계획(골드 IV), https://www.acmicpc.net/problem/1647

import sys
input = sys.stdin.readline

def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a < b:
        parent[b] = a
    else:
        parent[a] = b

N, M = map(int, input().split())
cities = [i for i in range(N)]
edges = []
for _ in range(M):
    A, B, C = map(int, input().split())
    edges.append((C, A-1, B-1))

edges.sort()

answer = 0
max_edge = 0 # 마을을 최소 유지비를 가지는 길들을 통해 2개로 분리해야 하므로, 크루스칼 알고리즘을 적용한 후 최대 유지비를 가지는 길을 없앤다.
for edge in edges:
    w, s, e = edge

    if find_parent(cities, s) != find_parent(cities, e):
        union_parent(cities, s, e)
        answer += w
        max_edge = w

print(answer - max_edge)

위상 정렬

• 태그: 위상 정렬, Topology Sort
• 설명: 대학교의 선수과목과 같은 구조를 구하는데 사용할 수 있음. 순서가 정해져있는 일련의 작업을 차례대로 수행해야 할 때 사용하며, 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않게 순서대로 나열함

import sys
from collections import deque
input = sys.stdin.readline

def topology_sort():
    result = []
    dq = deque()

    # 진입 차수가 0인 것을 큐에 넣음
    for i in range(V):
        if indegree[i] == 0:
            dq.append(i)
    
    while dq:
        cur = dq.popleft()
        result.append(cur) # 결과에 저장

        for g in graph[cur]: # 시작 노드에서 각 도착 노드들을 확인
            indegree[g] -= 1 # 진입 차수 1 감소
            if indegree[g] == 0: # 진입 차수가 0인 것을 큐에 넣음(2)
                dq.append(g)

V, E = map(int, input().split())
indegree = [0 for _ in range(V)] # 각 노드의 진입차수
graph = [[] for _ in range(V)]
for _ in range(E):
    start, end = map(int, input().split())
    graph[start-1].append(end-1)
    indegree[end-1] += 1 # 진입 차수를 1 증가시킴

topology_sort()

# 출력
for v in result:
    print(v, end=' ')
print()

가을 프로그래밍 경시대회 대비 C++ 문법

• 태그: deque, heap queue, pair, map, sort, 정렬

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
  

• deque

    #include <deque>
  
    deque<int> dq;
    for(int i=0; i<5; i++){
        dq.push_back(i+1);
    }
  
    //iterator 선언
    deque<int>::iterator iter;
    //[default 출력]
    cout << "[Default] : " ;
    for(iter = dq.begin(); iter != dq.end(); iter++){
        cout << *iter << " ";
    }
    cout << '\n';
  
  

• queue

    #include <queue>
  
    queue<int> q;
    q.push(1);
    queue.pop(); 
  

• map

    #include <map>
  
    map<string, int> m;
    m.insert({"muk", 26});
    if(m.find("muk") != m.end()){
        cout << "find" << '\n';
    }
    else{
        cout << "not find" << '\n';
    }
    m.erase("muk");
  

• pair

    #include <utility>
  
    pair<string, int> p;
    p = make_pair("naver", 2022);
    cout << p.first << p.second << '\n'; // muk2022
      
  

    struct user{
        string name;
        int age;
    }User;
  
    int main(){
        pair<pair<string, int>, string> p1;
        pair<vector<int, string> p2;
  
        vector<pair<int, pair<int, int>>> v;
        v.push_back(make_pair(5, make_pair(0, 3)));
    }
  

• 정렬

    #include <algorithm>
  
    int N = 10;
    int arr[N] = {};
    vector<int> v(N);
    // 배열
    sort(arr, arr+N);
    // 벡터
    sort(v.begin(), v.end()); // 오름차순
    sort(v.rbegin(), v.rend()); // 내림차순
  
    // Custom Sort
    bool cmp(int a, int b){
        return a > b;
    }
    sort(arr, arr+N, cmp);
    sort(v.begin(), v.end(), cmp);
  

파이썬 정규표현식

• 태그: 정규표현식, 정규식
• 설명: 라인.. 문자열…
• 링크1
• 링크2

• 링크3

    import re
    k = 3
    p = re.compile('.?[a-z]?.?[a-z]?.?')
  
    a = p.search('abc')
    print(a)
    b = p.search('a.c')
    print(b)
    c = p.search('.ac')
    print(c)
    d = p.search('...')
    print(d)
    # 재귀? 정규식?
  
  

• 코딩테스트
• muk