본문 바로가기
Coding

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

alida 2024. 3. 8. 07:06
자료구조와 알고리즘에 대해 더 알고 싶다면 [PS] 자료구조와 알고리즘 개념 정리 (Data Structure) Part 1 , [PS] 자료구조와 알고리즘 개념 정리 (Data Structure) Part 2 포스트를 참조하면 된다.

 

NOMENCLATURE

  • $V$ : 노드(Node, Vertex)의 개수 
  • $E$ : 간선(Edge)의 개수
  • $n$ : 원소의 개수 (또는 $N$)
  • $\log n$ : 밑이 2인 $\log_2 n$을 간략하게 표기
  • 노드 = 정점
  • 간선 = 엣지

 

Basics

Tip

  • 문제는 다음 링크를 통해 확인할 수 있다.
    • 백준: boj.kr/{문제 번호}
    • 정올: jungol.co.kr/problem/{문제 번호}
    • 알고스팟: algospot.com/judge/problem/read/{코드이름}
  • 채점용 서버는 일반적으로 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 (기본적으로 파일이 존재한다)
  • 전역변수와 static 변수는 자동으로 0으로 초기화되는 반면 지역변수는 자동으로 초기화되지 않고 쓰레기 값(garbage value)으로 채워지게 된다.
int A;         // 자동으로 0으로 초기화
int B[50];     // 자동으로 0으로 초기화
static int C;  // 자동으로 0으로 초기화

int main() {
  int D;       // 쓰레기 값(garbage value)으로 채워짐
  int E[50];   // 쓰레기 값(garbage value)으로 채워짐
}

 

Time complexity

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

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

 

Snippet code

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

#include <iostream>
#define rnt register int
#define FASTIO cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
#define WATCH(x) cout << #x << " : " << x << '\n';
#define PRINT(x) cout << x << '\n';
#define X first
#define Y second
using pii = std::pair<int,int>;
using ll = long long;
using namespace std;

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

}

 

Macro

  1. C++11부터 #define 대신 constexpr을 사용할 수 있다.
    • #define LM 10005
    • constexpr int LM = 10005;
  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 MIN(x,y) ((x)<(y) ? (x) : (y))
    • #define MAX(x,y) ((x)<(y) ? (y) : (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 WATCH(x) cout << #x << " : " << x << '\n'
    • #define DEBUG(x) cout << "DB - " << x << '\n'
    • #define PRINT(x) cout <<  x << '\n'
    • #define NWATCH(x) 
    • #define NDEBUG(x) 
    • #define NPRINT(x) 
      • DEBUG, WATCH, PRINT 앞에 N만 입력해주면 출력 구문을 비활성화할 수 있다.

 

Value initialization

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("짝수"); }
    • 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);

 

Prime number

  • 현재 숫자 n이 1 이외에 다른 수로 나눠지는지 확인함으로써 소수 판별
    • 시간복잡도: $O(\sqrt{n})$
더보기 
bool isPrime(int n) {
  if(n==1) return 0;
  for(int i=2; i*i<=n; i++){    // search until sqrt(n)
    if(n % i == 0) return 0;
  }
  return 1;
}
  • 에라토스테네스의 체(Sieve of Eratosthenes)를 사용하여 소수가 아닌 값들을 마킹함으로써 소수 판별
    • 시간복잡도: $O(n \log (\log n))$
더보기 
#include<bits/stdc++.h>

constexpr int N = 1005;
bool is_prime[N];

// Pure
void sieve() {
  memset(is_prime, 1, sizeof(is_prime));
  is_prime[1] = false;
  for(int i=2; i*i<=N; i++){
    if(is_prime[i] == false) continue;
    for(int j=i*i; j<=N; j+=i) {
      is_prime[j] = false;
    }
  }
}

int main() {
  sieve();

  for(int i=2; i<=N; i++){
    if(is_prime[i]) {    // check if 'i' is prime number
      printf("%d ", i);
    }
  }puts("");
}
더보기 
#include<bits/stdc++.h>
using namespace std;

int N = 1005;
vector<int> primes;

// STL
void sieve() {
  vector<bool> state(N+1, true);
  state[1] = false;
  for(int i=2; i*i<=N; i++){
    if(!state[i]) continue;
    for(int j=i*i; j<=N; j+=i)
      state[j] = false;
  }
  for(int i=2; i<=N; i++) {
    if(state[i]) primes.push_back(i);
  }
}

int main() {
  sieve();

  for(int i=2; i<=N; i++){
    if(find(primes.begin(), primes.end(), i) != primes.end()) {  // check if 'i' is prime number
      printf("%d ", i);
    }
  } puts("");
}

 

Modulo operation

  • Mod 연산(%)은 나머지를 구하는 연산으로 다음과 같은 동치 관계가 성립한다
    • (a + b) % MOD = ((a % MOD) + (b % MOD)) % MOD
    • (a + b + c) % MOD = ((a % MOD) + (b % MOD) + (c % MOD)) % MOD

 

Base conversion

  • A진법을 10진법으로 변환하는 코드 (Horner's method 사용)
    • result = (((0*A + digit1) * A + digit2) * A + digit3) * A + ...   
    • A: base
더보기 
int main() {
    int A;
    char S[100];
    scanf("%d %s", &A, S);

    int ret = 0;
    for(int i=0; S[i]; i++) {
        if(S[i] < 'A') ret = ret * A + (S[i] - '0');
        else           ret = ret * A + (S[i] - 'A' + 10);
    }
    
    printf("%d", ret);
}
  • 10진법을 B진법으로 변환하는 코드 (재귀 함수 사용) (한 글자씩 바로 출력)
더보기 
char chr[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

void Get(int ret, int to) {
    if(ret < to) {
        printf("%c", chr[ret]);
        return;
    }
    Get(ret/to, to);
    printf("%c", chr[ret%to]);
}

int main() {
    int ret, B;
    scanf("%d %d", &ret, &B);
    
    Get(ret, B);
}

 

std::string

  • 문자열을 반복 연산할 때 흔히하는 실수 ($L$은 문자열, $|L|$은 문자열 길이)
    • for ( int i = 0; i < 1000000; i++ ) { s = s + 'a'; } : 시간복잡도 $O(|L|^2)$
    • for ( int i = 0; i < 1000000; i++ ) { s += 'a'; }     : 시간복잡도 $O(|L|)$ 
더보기 
#include <bits/stdc++.h>
using namespace std;

int main( int argc, char **argv ) {
  string s;

  // 시간복잡도: O(N^2)
  // s+'a'라는 객체를 새로 만든 후 이를 s에 대입
  for ( int i = 0; i < 1'000'000; i++ ) {
    s = s + 'a';
  }

  // 시간복잡도: O(N)
  // += 연산자를 이용하면 시간복잡도가 더해지는 길이에만 영향 받음
  for ( int i = 0; i < 1'000'000; i++ ) {
    s += 'a';
  }
}
  • 문자열을 특정 구분자(seperator, delimeter) 단위로 나눈 결과를 반환하는 split 함수
더보기 
#include <bits/stdc++.h>
using namespace std;

vector<string> split( string& s, string& sep ) {
  vector<string> ret;
  int pos = 0;
  while ( pos < s.size() ) {
    int nxt_pos = s.find( sep, pos );
    if ( nxt_pos == -1 ) nxt_pos = s.size();
    if ( nxt_pos - pos > 0 )
			ret.push_back( s.substr( pos, nxt_pos - pos ) );
    pos = nxt_pos + sep.size();
  }
  return ret;
}

int main( int argc, char **argv ) {
  string s = "aaaaa,bbbbb ccccc,ddddd.eeeee";
  string sep1 = " ";
  string sep2 = ",";
  string sep3 = ".";
  vector<string> sp = split( s, sep2 );
  
  for ( auto s : sp )
    cout << s << endl;
}

 

 

Data structure

Linked list

Level1 - 개념 문제

 

Stack

Level1 - 개념 문제

 

Queue

Level1 - 개념 문제

 

Deque

Level1 - 개념 문제

 

Priority queue

Level1 - 개념 문제

 

Tree

Level1 - 개념 문제

Level2 - 발전 문제

 

Binary search tree (set, map)

Level1 - 개념 문제

 

Hash

Level1 - 개념 문제

 

Union-find

Level1 - 개념 문제

Level2 - 발전 문제

 

Algorithm

Basic I/O & Simulation

Level1 - 개념 문제

Level2 - 발전 문제

 

String

Level1 - 개념 문제

 

Bit-wise operation

Level1 - 개념 문제

 

 

Brute force

Level1 - 개념 문제

Level2 - 발전 문제

 

Math

Level1 - 개념 문제

Level2 - 발전 문제

 

Recursion

Level1 - 개념 문제

 

Backtracking

Level1 - 개념 문제

 

Two pointers

Level1 - 개념 문제

 

DFS

Level 1 - 개념 문제

 

BFS

Level 1 - 개념 문제

Level2 - 발전 문제

 

Binary search

Level1 - 개념 문제

Level2 - 발전 문제

 

Parametric search

Level1 - 개념 문제

 

Sort

Level1 - 개념 문제

Level2 - 발전 문제

 

Topological sort

Level1 - 개념 문제

 

Dynamic programming

Level1 - 개념 문제

Level2 - 발전 문제

 

Greedy

Level1 - 개념 문제

Level2 - 발전 문제

 

 

Divide and conquer

Level1 - 개념 문제

Level2 - 발전 문제

 

Sqrt decomposition

Level1 - 개념 문제

 

Segment tree

Level1 - 개념 문제

 

Minimum spanning tree (Prim, Kruskal)

Level1 - 개념 문제

Level2 - 발전 문제

 

Floyd-Warshall

Level1 - 개념 문제

 

Dijkstra

Level1 - 개념 문제

 

KMP

Level1 - 개념 문제

 

Trie

Level1 - 개념 문제

 

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의 강좌/실전 알고리즘

[10] (Site) C++ 유용한 기능들

[11] (Book) 알고리즘 문제 해결 전략 - 구종만 저

 

저작자표시

'Coding' 카테고리의 다른 글

Modern C++ 개념 정리 (STL, Design Pattern, Concurrent, Template Programming)  (0) 2024.06.27
[PS] 자료구조와 알고리즘 개념 정리 (Algorithm) Part 2  (1) 2024.03.08
[PS] 자료구조와 알고리즘 개념 정리 (Data Structure) Part 1  (1) 2024.03.07
VPython 예제10 - 2자유도 반한정계 스프링-질량 애니메이션  (0) 2022.01.11
VPython 예제9 - 2자유도 스프링-질량계 애니메이션 (2)  (0) 2022.01.11

'Coding' Related Articles

티스토리툴바