백투더코딩

내일 비대면 알고리즘 대회에 스터디를 같이 하고 있는 동기들과 참가한다.

뒤에 일정이 있어 대회 시간 절반 정도만 참여를 하기 때문에 입상을 노리고 있진 않지만 이 기회에 한 번 정리해보면 좋을 것 같아 포스팅을 하게 됐다.

다양한 언어로 코테를 풀면서 느낀게 문제를 읽고 어떤 걸 이용해 어떻게 풀지 로직만 잘 잡혀 있다면 언어는 그 다음 문제라는 것이다. 

알고리즘 유형 별로 문제가 어떤 식으로 많이 나오는 지 정리해봤다.

유형 별로 이해대신 외우는 용도가 아니라 저런 문제에 왜 저 알고리즘을 쓰는지 접근하는 방식으로 활용하면 좋을 것 같다.

항상 백프로 일치하진않고 경향성의 문제이며 아직 배워가는 입장이라 잘못된 정보가 있다면 댓글에 적어주세요!

완전탐색

입력 값이 100이하로 작은 문제

백트래킹

입력 값이 100이하로 작은 문제

순열, 중복 순열, 조합, 중복 조합

BFS

출발 값 존재

도착 값 까지 최소/최단 시간/거리/횟수

무가중 그래프

DFS

사이클 찾기 문제

한 가지 정점에서 연결된 모든 정점 탐색

그래프 완전 탐색

무가증 그래프

최단 거리는 절대 x

DFS+다이나믹 프로그래밍

갈 수 있는 방향이 목표지점까지로만 갈 수 있도록 제한 

사이클 x

경로 수 구하기

유향 그래프

BFS+다이나믹 프로그래밍

가중 그래프

메모이제이션을 통해 재방문이 가능한 경우를 정의할 때

이분 탐색

최소/최대 값 구하는 문제

결과 값들이 정렬 되어 있는 경우

X라는 조건 만족하는 최대/최소값

해시 맵

배열 내 빈도수 구하기

배열 내 중복된 요소 구하기

크루스칼

최소 신장 트리(가장 저렴한 방법으로 모두 연결 등)

프림 알고리즘

최소 신장 트리(가장 저렴한 방법으로 모두 연결 등)

다익스트라

최단 경로 (특정 노드->모든 노드까지)

가중 그래프

간선마다 가중치가 다른지 파악, 같다면 BFS 사용 가능

위상 정렬

주어진 수 정렬 할 때 순서가 정해져 있는 요소가 존재

우선 순위 큐/힙

실시간으로 정렬이 이루어져야하는 경우

N번째 요소 구하기

중앙 값 구하기

그리디

가장 많은 선택을 할 수 있는, 가장 작은/큰 등의 키워드가 있는 문제

플로이드-와샬

모든 노드->모든 노드까지 가는데의 최소 비용

참고 사이트

https://hh-bigdata-career.tistory.com/24

https://skytitan.tistory.com/217

https://mangkyu.tistory.com/181

재귀 함수

함수 안에서 자기 자신을 다시 호출하는 함수

재귀 함수 장점

복잡한 알고리즘을 가독성있게 표현할 수 있다.

재귀 함수 단점

함수 호출 오버헤드가 크다

재귀 함수 주의점

무한 루프에 빠지지 않기 위해 종료 조건을 잘 처리해야한다.

재귀 vs 반복문

모든 재귀 호출은 반복문으로 표현 가능하고

모든 반복문은 재귀 호출로 표현 가능하다.

재귀 코드

long long recursive(int n) {
	if (n < 1) 
		return 1;
	else 
		return n * recursiveFactorial(n - 1);
}

반복문 코드

long long nonRecursive(int n) {
	long long f = 1;
	while (n) 
		f = f * n--;
	return f;
}

참고 사이트

https://ansohxxn.github.io/algorithm%20lesson%201/chapter1-1/

비트란?

컴퓨터에서 사용하는 데이터의 최소 단위

0과 1

비트마스크란?

정수의 이진수 표현을 자료 구조로 쓰는 기법

집합을 메모리/시간 효율적으로 표현 가능하게 해줌

ex) 집합의 i번째 요소가 존재한다면 1, 존재안하면 0으로 표시 (비트마스킹)

비트 연산자 종류

-and 연산 &

-or 연산 |

-xor 연산 ^

 둘 중 하나만 1일 때 1

-not 연산 ~

-shift 연산 <<, >>

 왼쪽, 오른쪽으로 비트 이동, 빈자리는 0으로

비트마스크 연산 활용

-부분집합 i번째에 요소 삽입(i번째 비트 1로)

bit=bit | 1<<i

-부분집합 i번째 요소 삭제(i번째 비트 0으로)

bit=bit & ~(1<<i)

-부분집합 i번째 요소 조회

if ( bit& (1<<i)==1 ) i는 1

else i는 0

-부분집합 i번째 요소 토글(0->1,1->0)

bit=bit ^ ( 1<<i )

비트 마스크 사용시 주의할 점

-비교 연산자보다 비트 연산자의 우선 순위가 낮음

-오버플로우 문제

비트마스크의 장점

1. 빠른 수행속도

   O(1)

2. 코드가 짧음

   집합 연산들을 비트연산자를 활용해 한 줄로 표현 가능

3. 적은 메모리 사용량

4. 집합을 배열의 인덱스로 활용할 수 있음

참고사이트

https://rebro.kr/63

https://jooncco.com/algorithms/bitmask/

https://kim6394.tistory.com/246

https://velog.io/@cchloe2311/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%B9%84%ED%8A%B8%EB%A7%88%EC%8A%A4%ED%82%B9Bit-Masking

다이나믹 프로그래밍

하나의 문제는 한 번만 계산하는 알고리즘으로 큰 문제를 작은 문제로 나누어 푸는 알고리즘

다이나믹 프로그래밍을 사용하기 위한 조건

-작은 문제로 나눌 수 있을 때

-작은 문제의 답이 그것을 포함하며 더 큰 문제에서도 답이 동일하게 나올 때

다이나믹 프로그래밍 원리

메모이제이션을 활용해 작은 문제에서 계산한 결과 값을 배열에 저장해두고

나중에 큰 문제에서 그 값이 다시 필요할 때 동일한 계산을 진행하지 않고 저장된 값을 반환받아서 계산

+메모이제이션

결과를 저장해 함수가 한 번만 실행되는 것을 보장하는 기술

동적계획법을 쓸 때 많이 사용한다.

다이나믹 프로그래밍 구현법

1. 탑-다운

재귀함수로 구현할 때 대부분 탑-다운 방식을 사용하며 큰 문제를 풀 때

작은 문제 값이 없다면 그 때 작은 문제의 값을 계산함.

2. 다운-탑

작은 문제부터 먼저 계산하여 큰 문제의 값을 계산함.

다이나믹 프로그래밍 점화식 찾는 법

1. 작은 문제들의 값(0,1,2,3,3)들을 직접 계산해보면 점화식이 보임

그 점화식을 활용해 다이나믹 프로그래밍을 구현하면 됨.

2. 이전 단계에서 다음 단계로 가는 가짓수가 정해져있다면 그걸 이용해도 됨

   ex. 도형을 쪼갤 때 특정한 규칙으로만 쪼개져서 n-2단계/n-1단계에서 n이 되는

        가짓수가 정해져있을 경우

분할 정복 vs 다이나믹 프로그래밍

분할 정복은 단순히 큰 문제를 작은 문제로 나누어 푸는 것으로 작은 문제의 답이 항상

큰 문제의 답이 되지 않아 작은 문제를 여러 번 반복적으로 계산해야 함.

반면에 다이나믹 프로그래밍은 작은 문제 계산을 중복적으로 하지 않고 작은 문제의 답이

큰 문제에서도 변하지 않음을 이용함

참고 사이트

https://blog.naver.com/ndb796/221233570962

https://galid1.tistory.com/507

ios_base::sync_with_stdio(false);

c++ 컴파일러는 c와 c++ 입출력을 다 허용하는데, 이를 위해 동기화 되어있다.

위 코드는 C 표준 스트림과 C ++ 표준 스트림 간의 동기화를 비활성화

iostream과 stdio 버퍼를 모두 사용하지 않고 C++만의 독립적인 버퍼 사용

사용하는 버퍼 수 감소 -> 실행 속도 향상

cin.tie(NULL);

cin과 cout은 버퍼를 공유(tie)하고 있다.

cin에 cout이 묶여 있으면 프로그램이 사용자에게 입력을 요청하기 전에 버퍼를 확인하고 플러시과정 거침

위 코드는 cin에 cout을 untie

플러쉬 과정 사라짐 - > 실행 속도 향상

참고 사이트

https://jaimemin.tistory.com/1521

https://leeeegun.tistory.com/4

브루트 포스(Brute Force) / 완전탐색

brute: 짐승 force:힘

->무식하게 풀기, 모든 경우의 수를 다 계산해보기

->시간면에서 매우 비효율적

->하지만 그만큼 만들기 단순함

주의할 점) 모든 경우의 수를 다 계산해보기 때문에 문제의 데이터값 범위를 잘 확인하여

범위를 넘지않는지 잘 확인해야 함.