[PS] 알고리즘 문제 풀이 - 유용한 팁 및 문제 리스트 정리

Basic

Base knowledge

• 문제는 다음 링크를 통해 확인할 수 있다.
  • 백준: boj.kr/{문제 번호}
  • 정올: jungol.co.kr/problem/{문제 번호}
• 채점용 서버는 일반적으로 1초에 1~5억번의 연산을 수행한다. 
  • 따라서 데이터가 $n=10000\sim20000$개 일 때 $O(n^2)$ 알고리즘은 제한시간 1초 내 통과하기 어렵다.
• #include <bits/stdc++.h> 를 사용한다. Mac이나 Windows는 기본적으로 해당 파일이 존재하지 않으므로 해당 링크에서 다운로드 받은 후 아래 경로에 넣어준다.
  • Mac:  /Library/Developer/CommandLineTools/usr/bits/stdc++.h 
  • Windows: C:\Program Files (x86)\Microsoft Visual Studio\{Version}\Community\VC\Tools\MSVC\{Version}\include\bits\stdc++.h
  • Ubuntu: /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h 기본적으로 파일이 존재한다.

Macro

1. C++11부터 #define 대신 constexpr을 사용할 수 있다.
2. register int는 int 자료형보다 미세하게 실행 속도가 빠르다. 이는 constexpr 로는 선언이 안되므로 항상 #define 으로 선언해줘야 한다.
   • #define rnt register int
3. #define POWER(x) x*x 과 같이 선언하면 안된다. POWER(2+3) = 2+3*2+3 = 11이 되므로 #define POWER(x) ((x)*(x))와 같이 항상 괄호로 감싸줘야 한다.
   • #define POWER(x) ((x)*(x))
   • #define ABS(x) ((x)>0 ? (x):-(x)) 
   • #define ALL(x) begin(x), end(x)
   • #define SIZE(x) int(size(x))
   • #define REP(i,a,b) for(int i=(a); i<=(b); i++)
4. 디버깅용 매크로
   • #define debug(x) cout << #x << " is " << x << '\n'

memset & for & std::fill

memset()  함수는 배열을 $0$ 또는 $-1$ 값으로 초기화할 때만 사용한다. 이외의 값은 memset 함수로 세팅할 수 없다. 배열을 특정 값으로 세팅하고 싶다면 단순하게 for 문을 돌리거나 algorithm 헤더의 std::fill() 함수를 사용하면 된다.

• memset(A, 0, sizeof(A));
• for(int i=0; i<N; i++) A[i] = k;   : k는 임의의 수
• std::fill(A, A+N, k);  

I/O stream

1. cin/cout을 사용할 경우 다음 명령을 실행시켜야 시간 초과가 발생하지 않는다

• ios_base::sync_with_stdio(0); : C stream과 C++ stream의 동기화를 비활성화하여 C++ stream만 사용. 속도 측면에서 이득이지만 이후부터는 printf와 cout을 섞어쓰면 안된다.
• cin.tie(0), cout.tie(0) : cin, cout 명령 수행 전 flush 버퍼를 비우는 과정을 비활성화함으로써 속도 측면에서 이득을 봄 (하지만 입출력의 순서를 보장받을 수 없기 때문에 PS 이외에는 권장하는 방법은 아님)
• cin.tie(0)->sync_with_stdio(0); :  둘을 한 줄로 작성 가능

2. std::endl은 개행 문자 '\n'를 입력 후 버퍼를 비우는 과정을 자동으로 수행하기 때문에 느리므로 사용하지 않는다. endl 대신 '\n'을 사용한다.

3. getline(cin, s) : 공백까지 통째로 한 줄 입력을 받을 때 사용

4. cout << fixed << setprecision(n) : 소수점 아래 n자리까지 반올림하여 출력할 때 사용

Range-based for loop

1. C++11부터 추가된 기능

• for(int v : V) : 벡터 V의 모든 원소의 복사본 v대해 루프를 돈다
• for(int &v : V) : 벡터 V의 모든 원소의 원본 v에 대해 루프를 돈다

Bit-wise operation

유용하게 사용되는 비트연산자

• a를 k로 나눈 나머지 값
  • result = a & (k-1); // same as 'a % k'
• a가 홀수인지 판단하는 법                  
  • if(a & 1) { printf("홀수"); }
• a가 짝수인지 판단하는 법                  
  • if(~a & 1) { printf("짝수"); }
• a와 $2^k$을 곱한 결과                      
  • result = a << k;
• a를 $2^k$로 나눈 몫 p와 나머지 q     
  • p = a >> k;
  • q = a & ((1 << k) - 1);
• a와 b의 값을 서로 바꾸는 코드          
  • a = a^b, b = a^b, a = a^b;
• a의 k번째 비트가 0인지 1인지 판단  
  • result = (a >> k) & 1;
• a의 k번째 비트만 0으로 변경            
  • a = a & (~(1 << k));
• a의 k번째 비트만 0이면 1, 1이면 0으로 변경  
  • a = a ^ (1 << k);
• a가 2의 제곱수인지 판별              
  • result = a & (a-1); // a!=0 이면서 result==0이면 2의 제곱수
• a의 Least Significant 1 Bit ($2^0$부터 시작하여 처음 만나는 1인 비트의 가중치 값)을 구하는 법
  • lsb = a & -a;
  • printf("%d's LSB is %d\n", a, lsb);

 

Time complexity

시간 복잡도는 알고리즘이 문제를 해결하는 데 걸리는 시간의 양을 나타내는 척도이다. 이는 주로 입력 크기의 함수로 표현되며, 알고리즘이 실행될 때 필요한 기본 연산의 횟수로 측정된다. 시간 복잡도를 평가할 때는 최악의 경우, 평균 경우, 최선의 경우를 고려할 수 있으나, 대부분의 경우 최악의 시간 복잡도가 중요한 지표로 사용된다. 시간 복잡도는 Big O 표기법을 사용하여 표현한다. 

• $O(1)$: 상수 시간. 입력 크기와 상관없이 알고리즘의 실행 시간이 일정하다.
• $O(\log n)$: 로그 시간. 데이터 양이 증가해도 실행 시간이 비교적 적게 증가한다. e.g., 이진 탐색
• $O(n)$: 선형 시간. 알고리즘의 실행 시간이 입력 크기에 직접 비례한다. 예를 들어, e.g., 배열 순회
• $O(n \log n)$: 선형 로그 시간. 많은 효율적인 정렬 알고리즘들이 이 시간 복잡도를 갖는다.
• $O(n^2)$: 제곱 시간. 입력 크기의 제곱에 비례하는 실행 시간을 가지며, 이중 반복문을 사용하는 알고리즘에서 흔히 발생한다.
• $O(2^n)$: 지수 시간. 알고리즘의 실행 시간이 입력 크기의 지수 함수로 증가한다. 일부 재귀 알고리즘에서 발생할 수 있다.
• $O(n!)$: 팩토리얼 시간. 알고리즘의 실행 시간이 입력 크기의 팩토리얼에 비례하여 증가한다. 순열을 생성하는 알고리즘 등에서 나타날 수 있다.

 

Space complexity

공간 복잡도는 알고리즘의 실행 과정에서 필요한 저장 공간의 양을 나타내는 척도이다. 이는 알고리즘이 작동하기 위해 필요한 메모리 양을 의미하며, 입력 크기와 알고리즘의 구현 방식에 따라 달라진다. 공간 복잡도 역시 Big O 표기법을 사용하여 표현되며, 주로 입력 데이터, 추가적으로 필요한 변수, 재귀 호출 시 스택 공간 등을 고려하여 계산한다.

 

알고리즘 설계 시, 시간 복잡도와 공간 복잡도 사이에는 종종 trade-off 관계가 있다. 예를 들어, 더 많은 메모리를 사용하여 실행 시간을 단축시키는 경우(공간을 시간으로 바꾸는 경우)가 있을 수 있다. 효율적인 알고리즘을 설계하기 위해서는 문제의 요구 사항에 따라 시간과 공간 복잡도 사이의 최적의 균형을 찾는 것이 중요하다.

 

Scratch code

아래 코드는 필자가 PS를 시작할 때 사용하는 C++ 스니펫 코드이다. 항상 사용하는 것은 아니며 필요한 경우 수정하여 사용한다.

 

#include <bits/stdc++.h>
#define rnt register int
#define fasti cin.tie(0)->sync_with_stdio(0);
#define fastio cin.tie(0)->sync_with_stdio(0); cout.tie(0);
using namespace std;
using pii = pair<int,int>;
using ll = long long;

int main(int argc, char **argv){

}

 

Basic I/O & Simulation

Level1 - 개념 문제

• [ BOJ 2557 Hello World, Solution ], [ BOJ 11718 그대로 출력하기, Solution1, Solution2 ], [ BOJ 1000 A+B, Solution ], [ BOJ 11720 숫자의 합, Solution ], [  BOJ 10953 A+B-6, Solution ], [ BOJ 2741 N찍기, Solution ], [ BOJ 2739 구구단, Solution ], [  BOJ 1924 2007년, Solution ], [ BOJ 10818 최소, 최대, Solution ], [  BOJ 4101 크냐?, Solution ], [ BOJ 10871 X보다 작은 수, Solution ], [ BOJ 10808 알파벳 개수, Solution ], [ BOJ 11723 집합, Solution1, Solution2 ]

Level2 - 발전 문제

• [ BOJ 2658 직각이등변삼각형찾기, Solution ]

 

Data structure

Stack

Level1 - 개념 문제

• [ BOJ 10828 스택, Solution ], [ BOJ 9093 단어 뒤집기, Solution ]

Queue

Level1 - 개념 문제

• [ BOJ 10845 큐, Solution ]

 

Bit-wise operation

Level1 - 개념 문제

• [ JUNGOL_1419_엔디안, Solution ], [ BOJ 14391 종이조각, Solution ], [ JUNGOL_3293 비트연산 1, Solution ]

 

Brute force

Level1 - 개념 문제

• [ BOJ 18111 마인크래프트, Solution ]

Level2 - 발전 문제

• [ BOJ 2642 전개도, Solution ]

 

Math

Level1 - 개념 문제

• [ BOJ 7571 점 모으기, Solution ], [ JUNGOL_3106 진법변환, Solution ], [ BOJ 10158 개미, Solution ], [ BOJ 2477 참외밭, Solution ], [ BOJ 2527 직사각형, Solution ], [ BOJ 2503 숫자야구, Solution ], [ JUNGOL 3135 const 구간의 합 구하기 1D, Solution ], [ JUNGOL 3136 const 구간의 합 구하기 2D, Solution ], [ BOJ 10430 나머지, Solution ], [ BOJ 10972 다음순열, Solution1, Solution2 ], [ BOJ 10973 이전순열, Solution ], [ BOJ 10974 모든순열, Solution ], [ BOJ 10819 차이를최대로, Solution ], [ BOJ 10971 외판원순회2, Solution ]
  

Level2 - 발전 문제

• [ JUNGOL 4692 눈 내리는 겨울밤, Solution ]
  

 

Backtracking

• [BOJ 1182 부분수열의 합, Solution ], [ BOJ 13023 ABCDE, Solution ]

 

Dynamic programming

 

Two pointers

Level1 - 개념 문제

• [ BOJ 2467 용액, Solution ]

 

DFS

 

BFS

Level 1 - 개념 문제

• [ BOJ 2178 미로탐색, Solution1, Solution2 ], [ JUNGOL_1078_저글링방사능오염, Solution ], [ BOJ 4963 섬의개수, Solution ], [ JUNGOL 1462 보물섬, Solution ], [ BOJ 1260 DFS와 BFS, Solution ], [ BOJ 14501 퇴사, Solution1, Solution2]

Level2 - 발전 문제

• [ BOJ 2452 그리드 게임, Solution ]

 

Binary search

Sort

Level1 - 개념 문제

• [ JUNGOL 3339 계수정렬(Counting Sort), Solution ]

Level2 - 발전 문제

• [ BOJ 7452 합이 0인 네 정수, Solution ], [ JUNGOL 3120 기수정렬(Radix Sort), Solution ]
  

 

Union find

Level1 - 개념 문제

• [ JUNGOL 1863 종교, Solution ]

Level2 - 발전 문제

• [ BOJ_13306_트리, Solution ], [ BOJ_2463_비용,  Solution ]

Greedy

Divide and conquer

 

References

[1] (Blog) 알고리즘 문제풀이(PS) 시작하기 - plzrun

[2] (Blog) 내가 문제풀이를 연습하는 방법 - koosaga

[3] (Blog) 코드포스 블루, 퍼플 달성 후기 및 일지 & 공부법 - Rebro

[4] (Blog) PS를 공부하는 방법 (How to study Problem Solving?) - subinium

[5] (Site) Baejoon Online Judge

[6] (Site) JungOl

[7] (Site) SW Expert Academy

[8] (Blog) BaaaaaaaarkingDog의 강좌/실전 알고리즘

[9] (Youtube) BaaaaaaaarkingDog의 강좌/실전 알고리즘