백투더코딩

구글링을 하다가 우연히 endl을 통해 개행을 할 경우 출력과 함께 버퍼를 지워 속도가 

더 느리다는 게시글을 봤다.

endl 대신 C언어에서 사용했듯이 '\n'을 통해 개행을 진행하면 실행 속도를 향상 시킬 수 있다.

참고사이트 

https://jaimemin.tistory.com/1521

한 프로젝트 내 main 함수가 여러 소스들에 중복으로 있을 경우 오류가 발생한다.

->프로그램 실행 시 main 함수를 제일 처음 찾아가 코드 실행 하게 되는데 main 함수가 여러 개일 경우 오류가 발생

이때 main 함수를 수정할 수 없을 경우 중복되는 main 함수가 있는 소스 파일들을 무력화시키면 디버깅시 오류가 발생하지 않는다.

<특정 소스파일 디버깅에 포함되지 않도록 무력화 시키는 방법>

1.소스파일 우클릭

2.속성 클릭

3.일반-빌드에서 제외 '예'로 변경

참고사이트

https://komas.tistory.com/30

최대공약수: 공통된 약수 중 가장 큰 수

유클리드 호제법 이용

R이 0이 될 때까지

A % B = R

A = B

B = R 

반복하고 마지막 A가 최대 공약수가 된다.

최소공배수: 공배수 중에서 가장 작은 수

A*B/최대공약수 이용  (최소공배수 * 최대공약수 = A * B이기 때문에)

=>A*B/gcd(A, B)

참고 사이트

https://twpower.github.io/69-how-to-get-gcd-and-lcm

mod 연산을 사용하여 나머지 연산을 구한다.

a mod b : a를 b로 나눈 나머지

• (A + B) % M = ((A%M) + (B%M)) % M
• (A X B) % M = ((A%M) X (B%M)) % M
• (A - B) % M = ((A % M) - (B % M) + M) % M

뺄셈 연산의 경우만 mod 연산을 수행한 값이 음수가 나올 수 있으므로 굵은 글씨 부분을 추가해야 한다.

ex) -5 mod 3 은 값이 1이 나와야 한다. (-2+3=1)

참고사이트

https://velog.io/@gidskql6671/%EB%82%98%EB%A8%B8%EC%A7%80Modulo-%EC%97%B0%EC%82%B0-%EB%B6%84%EB%B0%B0%EB%B2%95%EC%B9%99

https://codingram.tistory.com/26

https://teus.me/736

빅오 표기법 사용

ex) O(N)

Big O

g(n)<=c*f(n):asymptotic upper bound

(c:some positive real constant N:some nonnegative integer s.t. for all n>=N)

g(n) is big O of f(n)

시간 복잡도를 계산할 때 상수는 버리며 가장 차수가 큰 변수를 기준으로 한다.

ex) n^2 와 n이 있을 경우 n^2이 빅오 표기법에 사용됨.

시간복잡도와 달리 공간 복잡도는 알고리즘 문제에서 크게 상관이 없는 경우가 많지만

필요없는 공간을 사용하고 있진않은지 신경을 쓸 필요는 있다.

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 알고리즘

대표적인 문자열 매칭 알고리즘

모든 경우를 다 비교하지 않아도 부분 문자열을 찾을 수 있음

접두사와 접미사가 일치하는 최대길이를 활용해 모든 경우를 다 비교하지

않고도 부분 문자열을 찾을 수 있는 알고리즘

문자열 매칭 알고리즘

특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘

단순 비교 문자열 매칭 알고리즘

하나씩 일일이 확인하는 가장 간단한 형태의 알고리즘

문자열의 위치를 세트로 하나씩 밀어가며 맞을 때까지 찾는 알고리즘

라빈 카프 알고리즘

항상 빠르지는 않지만 일반적인 경우 빠르게 작동하는 간단한 구조의 문자열 매칭 알고리즘

문자열의 해시 값을 비교하여 그 일치 여부를 검사하는 알고리즘

해시 값이 일치할 경우 하나씩 비교해보며 실제로 맞는지 확인

긴 글의 해시 값을 빨리 계산하기 위해서 제일 앞에 문자의 수를 빼고

들어올 문자의 해시값을 더해도 됨

해시

긴 데이터를 그것을 상징하는 짧은 데이터로 바꾸어 주는 기법

완전 탐색

가능한 경우를 일일이 다 탐색

탐욕적 기법(그리드 알고리즘)

항상 눈앞의 가장 큰 이익만을 좇는 방법