21/02/28
3-1 학기에 알고리즘 과목을 수강하며 본격적으로 배우기 전에 프로그래밍 대회가 어떤 식으로 진행되는지 맛보면 공부할 때 방향 잡기가 수월할 것 같아서 SUAPC 2021 Winter에 참가했다.
ICPC 대회처럼 3인1팀으로 진행되는 대회라 동기 2명을 섭외해서 참가했다.
(대회를 위해 자취방을 제공해준 동기에게 무한한 감사를ㅎㅎ)
c++로 대회에 참가하려고 하는데 2-1에 객체지향 프로그래밍을 배운 이후로 c++을 안쓴지 반 년이 넘어서
대회 일주일 전쯤부터 c++을 복기하고 알고리즘 내용을 간단하게라도 공부해서 정리했다.
그리고 종만북에서 대회 정보에 관련된 부분을 보며 어떤 식으로 대회에 접근해야되는지 공부했다.
입상은 하지못했지만 아직 시작하는 단계이기 때문에 앞으로 이 경험을 바탕으로 더 성장해 나가고 싶다.
아래는 간단하게 알고리즘들을 정리한 내용이다.
선택정렬 n^2
가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘
버블정렬 n^2
바로 가까이에 있는 두 숫자끼리 비교를 해서 더 작은 숫자를 앞으로 보내줌
삽입정렬 n^2
각 숫자를 필요할 때만 적잘한 위치에 삽입하는 방식
데이터가 이미 정렬됐을 경우 최적
퀵정렬 n*logn n^2
분할 정복 알고리즘
하나의 큰 문제를 두 개의 작은 문제로 분할 하는 방식
특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤 배열을 반으로 가름
병합정렬 n*logn
분할 정복 알고리즘
일단 정확히 반으로 나누고 나중에 합치는 순간에 정렬을 수행
c++ STL sort함수
#include ＜algorithm＞
sort(시작점 주소, 마지막 주소+1);
기본적으로 오름차순 정렬
bool 함수를 추가하여 sort 마지막에 인자로 넣어주면 오름차순이 아닌 다른 순으로도
정렬 가능함
대회용으로는 pair함수와 같이 사용하는 것이 좋음
힙정렬
힙트리 구조를 이용하는 정렬 방식
이진트리
모든 노드의 자식 노드가 2개 이하인 트리 구조
완전이진트리
데이터가 루트노드부터 시작해서 자식 노드가 왼쪽 자식 노드, 오른쪽 자식 노드로 차근차 근 들어가는 구조
힙
최솟값이나 최댓값을 빨리 찾아내기 위해 완전 이진 트리 기반
최대힙
부모 노드가 자식 노드보다 큰 힙
힙 생성 알고리즘
특정한 노드의 두 자식 중에서 더 큰 자식과 자신의 위치를 바꾸는 알고리즘
계수정렬
크기를 기준으로 개수를 세는 알고리즘
스택
후입 선출
택배 상하차
큐
선입선출
은행 창구
너비우선탐색
큐 사용
탐색을 할 때 너비를 우선으로 하여 탐색을 수행
최단 길이를 보장할 때 많이 사용
깊이우선탐색
스택사용
스택의 최상단 노드를 확인한 후 방문하지 않은 인접 노드가 있으면
그 노드를 스택에 넣고 방문처리함
방문하지 않은 인접 노드가 없으면 최상단 노드를 뺌
유니온 파인드(합집합 찾기)/서로소 집합
여러 개의 노드가 존재할 때 두 개의 노드를 선택해서
현재 이 노드가 같은 그래프에 속하는지 판별
부모를 합칠 때는 일반적으로 더 작은 값 쪽으로 합침
재귀함수를 사용해서 타고타고 올라가서 같은 그래프인지 확인
크루스칼 알고리즘
가장 적은 비용으로 모든 노드를 연결
1. 비용을 기준으로 오름차순 정렬
2. 정렬된 순서에 맞게 그래프에 포함
3. 포함시키기 전에 사이클 테이블 확인
4. 사이클을 형성하는 경우 간선에 포함안함
전위 순회
자기 자신, 왼쪽 자식, 오른쪽 자식
중위 순회
왼쪽 자신, 자기 자신, 오른쪽 자식
후위 순회
왼쪽 자신, 오른쪽 자신, 자기 자신
다이나믹 프로그래밍
하나의 문제는 단 한 번만 풀도록 하는 알고리즘
메모이제이션을 활용해 이미 계산한 결과는 배열에
저장한 후 재사용
에라토스테네스의 체
가장 대표적인 소수 판별 알고리즘
소수를 대량으로 빠르고 정확하게 구하는 방법
다익스트라 알고리즘
다이나믹 프로그램 활용 최단경로 탐색 알고리즘
특정한 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 알려줌
하나의 최단 거리를 구할 때 그 이전까지 구했던 최단 거리 정보를 재사용
현재까지 알고 있던 최단 경로를 계속해서 갱신
이차원 배열 형태로 처리해야 함
플로이드 와샬 알고리즘
다이나믹 프로그래밍 활용 거쳐가는 정점을 기준으로 최단거리를 구함
위상 정렬
순서가 정해져있는 작업을 차례로 수행해야 할 때
그 순서를 결정해 주기 위해 사용하는 알고리즘
DAG(사이클이 발생하지 않는 경우)에만 적용 가능
SCC 알고리즘, 강한 결합 요소
그래프 안에서 강하게 결합된 정점 집합
같은 scc에 속하는 두 정점은 서로 도달이 가능함
사이클이 발생하는 경우 무조건 scc에 해당
타잔 알고리즘
모든 정점에 대해 dfs를 수행하여 scc를 찾는 알고리즘
네트워크 플로우
특정한 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는지 측정 알고리즘
최대 유량 문제
각 간선에 정해진 용량이 있을 때 최대로 보낼 수 있는 유랑의 크기를 구하는 문제
bfs이용이 일반적
==에드몬드 카프 알고리즘
순서가 상관없으므로 음의 유량도 계산 가능함
이분 매칭
a집단이 b집단을 선택하는 방법에 대한 알고리즘
두 개의 집단이 있음
그래프 형태로 표현
kmp 알고리즘
대표적인 문자열 매칭 알고리즘
모든 경우를 다 비교하지 않아도 부분 문자열을 찾을 수 있음
접두사와 접미사가 일치하는 최대길이를 활용해 모든 경우를 다 비교하지
않고도 부분 문자열을 찾을 수 있는 알고리즘
문자열 매칭 알고리즘
특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘
단순 비교 문자열 매칭 알고리즘
하나씩 일일이 확인하는 가장 간단한 형태의 알고리즘
문자열의 위치를 세트로 하나씩 밀어가며 맞을 때까지 찾는 알고리즘
라빈 카프 알고리즘
항상 빠르지는 않지만 일반적인 경우 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘
문자열의 해시 값을 비교하여 그 일치 여부를 검사하는 알고리즘
해시 값이 일치할 경우 하나씩 비교해보며 실제로 맞는지 확인
긴 글의 해시 값을 빨리 계산하기 위해서 제일 앞에 문자의 수를 빼고
들어올 문자의 해시값을 더해도 됨
해시
긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸어 주는 기법
완전 탐색
가능한 경우를 일일이 다 탐색
탐욕적 기법(그리드 알고리즘)
항상 눈앞의 가장 큰 이익만을 좇는 방법