Skip to content

min-ki/PS

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

75 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Algoritm

알고리즘 개념을 정리하고 구현한 파일을 모아놓는 폴더

  • Graph

    • Depth first search (깊이우선탐색)

      void DFS(int v) {
          
          visited[v] = true; 
          cout << "vertex: " << v << '\n';
          
          for(auto next : adj[v]) {
              if (!visited[next])
                  DFS(next);
          }
      }
  • Recursion

    • Memoization
      • Dynamic Programming 에서 주로 사용
      /* 이항계수를 구하는  알고리즘 */
      long long memo[1001][1001]; // Memoization을 위한 메모리 공간
      
      long long int bino(long long n, long long k) {
          long long sum = 0;
          
          if(k==0 || n == k) return 1;
          if(memo[n][k] != -1) return memo[n][k];
          
          sum = (bino(n-1, k-1)  + bino(n-1,k))% 10007;
          memo[n][k] = sum; // Memoization 사용
          
          return memo[n][k];
      }
  • Sort

    • BubbleSort

    • void BubbleSort(int testcase[], int len) {
      	int i, j, temp;
      
      	for (i = 1; i <= len - 1; i++) {
      		for (j = 1; j <= len - i; j++) {
      			if (testcase[j - 1] > testcase[j]) {
      				temp = testcase[j];
      				testcase[j] = testcase[j - 1];
      				testcase[j - 1] = temp;
      			}
      		}
      	}
      }
    • SelectionSort

      int* SelectionSort(int A[], int length) {
      	int i, j, temp;
      	int min;
      	for (i = 0; i <= length - 2; i++) {
      		min = i;
      		for (j = i + 1; j <= length - 1; j++) {
      			if (A[j] < A[min]) {
      				min = j;
      			}
      		}
      		temp = A[i];
      		A[i] = A[min];
      		A[min] = temp;
      	}
      	return A;
      }
    • MergeSort

    • ShellSort

      int* ShellSort(int A[], int length) {
      	int gap[] = { 5,3,1 };
      	int i, j, k, currentElement;
      	for (i = 0; i < sizeof(gap) / sizeof(int); i++) {
      		for (j = gap[i]; j <= length - 1; j++) {
      			currentElement = A[j];
      			k = j;
      			while (k >= i && A[k - i] > currentElement) {
      				A[k] = A[k - i];
      				k = k - i;
      			}
      			A[k] = currentElement;
      		}
      	}
      	return A;
       }
    • CountingSort

      memset(count, 0, sizeof(count));
      
      // count 배열에 입력받은 값의 count를 1씩 증가
      // 입력되는 순서는 상관이 없다.
      while(n--) {
          int num;
          cin >> num;
          count[num]++;
      }
      
      // count 배열에 들어있는 숫자만큼 index를 출력시켜주면 된다.
      for(int i=1; i<=10000; ++i) {
          if(count[i]) {
              for(int j=1; j<= count[i]; ++j) 
                  cout << i << '\n';
          }
      }
    • QuickSort

  • Search

    • BinarySearch
  • 소수

    • 에라토스테네스의 체
  • 최단경로

    • 플로이드 와샬 알고리즘

      // 경유지 -> 시작점 -> 도착점 순
      for(int k=0; k<n; ++k) {
          for(int i=0; i<n; ++i) {
              for(int j=0; j<n; ++j) {
                  dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
              }
          }
      }

BOJ

알고리즘 문제 프로그래밍 사이트인 백준 온라인 져지의 문제들을 풀어서 모아놓는 폴더

  • Language: c++, python3
  • 문제 종류
    • 구현
    • 수학
    • 시뮬레이션
    • 브루트 포스
    • 다이나믹 프로그래밍
    • 백트래킹
    • 문자열 처리
    • 그리디 알고리즘
    • 정렬
    • 탐색
    • 그래프 : DFS, BFS

STL

c++에서 제공하는 자료구조와 알고리즘 표준 라이브러리

  • Container
    • Stack
    • Queue, Deque, Priority_queue
    • Vector
    • List
    • Map, Multi map
    • Set, Multi set