공부정리 아카이브

출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

- stack : 먼저 들어간 원소가 가장 나중에 나오는(First In, Last Out - FILO) 자료 구조

- 스택의 성질
  - 원소의 추가 / 제거에 O(1)
  - 제일 상단 원소 확인 시 O(1)
  - 원칙적으로는 제일 상단 외의 데이터 확인이 불가

- 스택의 구현
  - 배열을 이용한 구현

const int MAX = ...;
int data[MAX];
ins pos = 0; // 스택의 빈 공간의 인덱스를 가리킴 = 스택 원소의 수

void push(int x){
	data[pos++] = x;
} // 스택에 데이터 추가

void pop(int x){
	return data[pos--];
} // 스택의 데이터 제거 및 반환

void top(){
	return data[pos - 1];
}//최상단 데이터 반환

  - STL stack

#include <stack>

int main(void){
	stack<int> s;
    s.push(10); // 데이터 추가
    cout << s.size(); // 스택 크기 반환
    if(s.empty()) cout << "s is empty" // 스택의 비었는지 여부
    s.pop(); // 스택 최상단 데이터 제거
  	cout << s.top(); // 스택 최상단 데이터 확인
}

요세푸스 순열은 여기서 그려볼 수 있다. Josephus Problem – GeoGebra

C++의 list STL로 풀고자 했던 문제. 처음 데이터를 저장하는 list와, 요세푸스 순열을 저장하는 list를 각각 선언 후, 저장 list를 하나씩 지워가며 순열 list로 옮기도록 코드를 작성했다.

그런데 list STL의 erase의 원리가 잘 이해되지 않아 한참을 헤메야 했다.
stl erase는 원소를 지운 후 다음 원소의 주소를 반환한다.
예를 들어 원소가 1,2,3,4일때 iterator가 3을 가리키는 상태에서 erase(iterator)를 하면, 원소는 3을 없애고 4를 가리킬 것이다.

이때 k번째 원소를 없앤다고 할 때 index i를 두고 나머지가 0이 되는 시점에 원소를 제거하게 했더니, index는 그대로인 채 원소만 제거되면서 코드가 생각한 대로 돌지 않는 문제가 발생해버렸다.

이를 해결하고자, erase가 발생하는 시점에서는 iterator를 하나 이전으로 돌려주는 방식으로 코드를 작성했다.
이상한 점은, erase 후 iterator를 --해 주는 코드를 한 줄에 작성했더니 동작이 또 이상하게 나타난다. 함수 내부에서 동작하면서 원래 값을 수정하는 게 있는건지...

#include <iostream>
#include <list>
using namespace std;

int main() {
	// your code goes here
	list<int> arr, ans;
	list<int>::iterator cur_arr;
	
	int n, k;
	cin >> n >> k;
	for(int i = 0 ; i < n ; i++){
		arr.push_back(i + 1);
	}
	int i = 1;
    cur_arr = arr.begin();
	while(!arr.empty()){
		if( i % k == 0){
			ans.push_back(*cur_arr);
			cur_arr = arr.erase(cur_arr);
			cur_arr--;
		}
		
		i++;
        cur_arr++;
        if(cur_arr == arr.end()) {
            cur_arr = arr.begin();
        }
	}
	list<int>::iterator c = ans.begin();
	cout << '<' << *c;
	for(c++ ; c != ans.end() ; c++){
		cout << ", " << *c;
	}
	cout << '>';
	return 0;
}

출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

- 배열이란 : 연속된 메모리 주소 상에 데이터를 할당하는 자료 구조
- 배열의 시간 복잡도
  - 데이터의 조회 및 수정 : O(1)
  - 맨 끝 원소의 추가/제거 : O(1)
  - 임의 원소의 추가/제거 : O(n) - 해당 위치부터 배열 끝까지 1개씩 데이터 위치를 조정해주어야 하므로

- 배열의 특징
  - 원소의 조회 및 확인에 O(1)의 시간 복잡도 요구
  - overhead는 낮고, cache hit는 높다
  - 주소가 연속 할당되어야 하므로 다른 구조 대비 할당에 제약이 다소 있는 편

- 배열 임의 위치에 추가 및 제거

#include <iostream>
using namespace std;

void insert(int idx, int data, int arr[], int &len){
	// idx : 추가할 위치
    // data : 추가할 데이터
    // arr[] : 원본 배열
    // len : 배열 길이, reference로 호출하였으므로 수정시 원본 값도 수정된다.
	
	for(int i=len;i > idx;i--){
    	arr[i] = arr[i - 1];
    }
    arr[idx] = data;
    len++;
}
void delete(int idx, int arr[], int &len){
	// insert에서 data만 빠진 상태
    // 제거할 위치 뒤의 모든 데이터를 1칸씩 앞으로 옮긴다.
    for(int i = idx ; i < --len ; i++){
    	arr[i] = arr[i+1];
    }
}

- 배열의 초기화
  1. for문 순회
  2. <algorithm> 헤더 - fill함수

int a[21];
int b[21][21];

fill(a, a + 21, 0); //시작위치, 끝위치, 채울 값

for(int i = 0 ; i < 21 ; i++)
	fill(b[i], b[i] + 21, 0); // 2차원 배열 초기화

- <vector> 헤더
  - 배열과 동일한 기능
  - 크기 조정이 자유로움

#include <iostream>
#include <vector>
using namespace std;

int main(void){
	vector<int> v1(3, 5);
    // vector 선언 : vector<자료형>
    // 초기값 선언 : 배열이름(길이, 초기값);
    
    int size = v1.size(); // 벡터 길이
    int begin = v1.begin(); // 벡터 맨 앞 위치
    v1.push_back(1); // 벡터 맨 뒤에 데이터 추가
    v1.insert(begin, 3); // 임의 위치에 데이터 추가
    v1.erase(begin); //임의 위치의 데이터 제거
    
    int pop = v1.pop_back(); // 맨 뒤 데이터 제거 및 반환
    v1.clear(); // 벡터 초기화
    
    // insert, erase 시 O(n) 시간복잡도
    // push/pop_back은 O(1) - 맨 뒤 데이터이므로
    // 벡터 간 대입 시 deep copy - 한쪽이 바뀌어도 다른쪽은 유지
    
    //벡터 순회 - C++11 기준
    for(int v : v1) cout << v << ' ';
    // v1의 원소가 순서대로 v에 복사되어 들어감
    // 만약 int &v로 설정시 원본값이 들어감
    
    //for문으로 벡터 순회
    for(int i = 0 ; i < v1.size() ; i++) cout << v1[i] << ' ';
}

- C++의 <algorithm> 헤더에는 순열(permutation)을 구할 수 있는 next_permutation 함수가 있다.
완전 탐색 시의 코드를 상당히 간결하게 만들어준다.

- 코드 문제 풀이 시 입력받는 arr가 있다고 할 때, 해당 arr의 순열을 찾을 index의 배열을 별도로 선언한다.
- next_permutation(시작 주소, 끝 주소) 형태로 반환받으므로, next_permutation(배열 이름, 배열 이름 + 원소 개수) 형태로 while 반복문을 사용해주면, 다음 순열이 없을 때까지(false를 반환하다) 순열을 조합해준다.

int per[10] = {0,1,2,3,4,5,6,7,8,9};

do{
	//per에는
	//0,1,2,3,4,5,6,7,8,9 부터,
    //9,8,7,6,5,4,3,2,1,0 까지 모든 순열이 반환된다.
}while(next_permutation(per, per + 10));

- 우리는 보통 연산을 10진수 단위로(0,1,2,...)로 하지만, 컴퓨터는 이를 2진수로(0,01,0101,...) 처리한다. 이때 컴퓨터의 2진 연산을 처리하도록 하는 것이 비트 연산자이다.

- 두 bit(0 or 1)이 있을 때, and(&), or(|), xor(^), shift(>>, <<) 등의 비트연산자가 존재한다. 이러한 비트 연산자를 사용해 여러 유용한 계산 방식을 쓸 수 있다.
  - i번째 bit를 1로 만들기

bit |= (1<<i);

  - i번째 bit를 0으로 만들기

bit &= ~(1<<i);

  - i번째 bit를 toggle(0 > 1, 1 > 0)

bit ^= (1<<i);

 - 최하위 i개의 bit를 모두 1로 만들기

bit |= (1 << i) - 1;

  - 모든 bit 0으로 만들기

bit = 0;

- 최대공약수(GCD, Greatest Common Divisor)는 두 수를 공통으로 나눌 수 있는 최대의 정수를, 최소공배수는 두 수의 배수가 되는 최소의 정수이다.
- 최대공약수 계산의 경우, 유클리드 호제법과 재귀함수를 이용하여 구현할 수 있다.

int gcd(int a, int b){
	return b ? gcd(b, a % b) : a;
}

- 임의의 수 A, B의 최대공약수가 G라면, A=aG, B=bG로 표현할 수 있다고 할 때,
- (a - kb)G = c 형태로 관계식을 나타낼 수 있다. 이때 a-kb와 b의 최대공약수가 G이기 위해 두 수는 서로소여야 하고, 이 조건을 만족할 때 b와 c의 최대공약수는 G가 된다.

- 위의 재귀 코드는 다음과 같이 동작한다.
  - 먼저 a, b를 받아서, b의 값이 참인지를 (= 존재하는지) 확인한다. (약수 계산이므로 a, b는 모두 2 이상임을 가정한다.)
  - gcd는 b와 a/b의 나머지를 매개변수로 받아 gcd 함수를 다시 호출한다.
  - 이 과정을 반복할 때 두 수 사이의 공통된 약수가 있다면, gcd(a,b)함수의 b에는 언젠가 0이 전달된다.
  - b=0이 전달되는 시점에서 해당 함수에 전달된 a값이 최대공약수로 반환되게 된다.
  - 만약 두 수가 서로소라면(ex. 2, 3), 마지막에는 a%b에 1이 전달될 것이므로, 최소공배수가 1이 전달된다.

- 두 수 a, b의 최소공배수는 a * b / G로 계산 가능하다.

int g = gcd(a, b);
int lcm = a * b / g;

//오버플로우 방지
int g = gcd(a, b);
int lcm = a / g * b / g * g;

위 코드로 간편히 풀 수 있지만, 곱셈 연산은 오버플로우의 우려가 있으므로, 경우에 따라 아래 코드로 계산할 수 있다.

- 소수 : 1과 자기 자신으로만 나누어 떨어지는 수 (ex. 2, 3, 5, 7, 11, ...)
- 소수의 판별
  - 임의의 수 N이 있을 때, 2부터 N-1까지 모두 나누어 나머지가 0인 경우가 있는지 판별하면 된다. 이때 하나라도 거짓인 경우 소수가 아니다.
  - 여기서 계산을 조금 줄인다면, N의 제곱근까지만 연산해도 된다( 그 수를 제곱했을 때 나누어 떨어지면 소수가 아닐테니까 )

#include <iostream>

using namespace std;
int main(void)
{
	bool prime = true;
    int n;
    cin >> n;
    
    for(int i=2 ; i * i <= n; i++)
    {
    
    	if(num % i == 0){
        cout << "소수가 아닙니다";
        return 0;
        }
    }
    
    cout << "소수입니다";
	return 0;
}

- 위에서 1부터 루트 n까지 비교하면 된다고 했지만, 제곱근을 구하는 연산은 많은 자원을 필요하기 때문에, 반대로 제곱이 입력받은 수가 되는가를 비교하여 소수를 판별하게 한다.

- 에라토스테네스의 체는 특정 범위의 수가 소수인지 아닌지를 판별하는 방법을 말한다.

- 일단 0, 1은 고정적으로 소수가 아니고, 2부터 시작해서 2의 배수, 3의 배수를 계속해서 지워나가는 식으로 연산을 하면 된다.

#include <iostream>

using namespace std;

#define MAX 100000
int main(void)
{
	bool arr[MAX] = {1, 1}
    
    for(int i=2;i * i <= MAX;i++}
    {
    	if(arr[i]) continue; //배열 값이 1이면(true - 소수가 아니다) 패스한다.
        
        for( int j = i * i; j < MAX ; j += i ) arr[j] = 1;
    }
	return 0;
}

- 이때 이중 for문 j가 i의 제곱부터 시작하는 이유는, 그 전의 수는 계산 과정에서 이미 소수 여부가 판별이 되었기 때문이다.
- 예를 들어 i=2일 때, 이미 2의 배수는 모두 지워진 상태이다. 즉 i=3이 되었을 때, 3*1은 자명하게 소수인 상태이고, 3*2는 2의 배수 연산 때 이미 소수임이 판별되었으므로 연산할 필요가 없는 상태이다.

문제

피제수(분자) A와 제수(분모) B가 있다. 두 수를 나누었을 때, 소숫점 아래 N번째 자리수를 구하려고 한다. 예를 들어, A=3, B=4, N=1이라면, A÷B=0.75 이므로 출력 값은 7이 된다.

입력

첫 번째 줄에 A와 B(1≤A, B≤100,000), N(1≤N≤1,000,000)이 공백을 경계로 주어진다.

출력

A÷B를 했을 때, 소숫점 아래 N번째 수를 출력한다.

- 소숫점 문제라서 단순히 %연산을 썼는데 틀려버렸다.
- 생각해보니까 float/double은 부동소수점이라 아래 자리수가 커질수록 정확도가 낮아짐(1,000,000번째 자리수까지 따지고 있다...double이 지원하던가 애초에?)

- 컴퓨터 연산 대신 손으로 푸는 나눗셈 풀이로 풀어보기로 함

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int a, b, n;
	int res = 0;
	
	cin >> a >> b >> n;
	if( a % b == 0){
		cout << 0;
		return 0;
	}
	
	if( a > b ) a = a % b;
	
	for(int i=0;i<n;i++){
		a *= 10;
		res = (int)(a / b);	
		a = a % b;
	}
	cout << res;
}

만약 나눠 떨어지면(나머지가 0이면) 바로 0을 출력하고,
그렇지 않으면 a의 자리수를 하나 올린 후, 몫을 출력한다. a는 나머지로 갱신한다.
n번째 자리수까지 이를 반복한 후 마지막 연산의 몫이 n번째 자리수 소수가 된다.

import sys
input = sys.stdin.readline

l = int(input().strip())
arr = []

for iter in range(l):
    a = input().strip().split(' ')
    if(a[0] == 'push'):
        arr.append(a[1])
        
    elif(a[0] == 'pop' or a[0] == 'top'):
        if(len(arr) == 0) :
            print('-1')
            continue
        print(arr[-1])
        if(a[0] == 'pop') : del arr[-1]
        
    elif(a[0] == 'empty'):
        print('1' if len(arr) == 0 else '0')
        
    else:
        print(len(arr))

스택의 기본 동작인 push, pop 등을 구현하는 문제. python을 이용하면 쉽게 풀 수 있다.

그런데 아무리 해도 시간초과가 떠서 질문란을 살펴보니 sys.stdin.readline을 사용하라고 하는데, 흔히 입력에 쓰는 input() 함수의 경우 입력 > prompt 출력 > strip(개행 제거)의 과정을 거치므로 대량 입력 시 시간 지연이 심해질 가능성이 있다고 한다.

이것때문에 시간초과로 5번이나 실패했다 ㅜㅜ...

출처 : BaaaaaaaarkingDog | '강좌/실전 알고리즘' 카테고리의 글 목록 (encrypted.gg)

• 자료구조 : 컴퓨터가 처리할 자료를 효율적으로 처리하기 위해, 특성에 따라 분류, 구성, 저장, 처리하는 과정
• 알고리즘 : 주어진 문제를 해결하기 위한 절차, 방법, 명령어

• 알고리즘의 성능 분석
  • 시간 복잡도 = 실행 시간
  • 공간 복잡도 = 사용 공간
• 알고리즘의 복잡도 표현
  • worst case
  • average case
  • best case
• Big-O 표기법
  • 처리 시간의 최대 범위
  • 시간 복잡도 함수의 최대 차수 항만 고려
  • ex. $f(n)=2n^3+3n^2+5\to O(n^3)$
• Big-Omega 표기법
  • 처리 시간의 최선(최소) 범위
• Big-Theta 표기법
  • Big-O, Big-Omega 사이 평균 범위

• ex. 1부터 n까지 더하기

• n번 반복문을 순회하므로 $O(n)$의 시간복잡도

• 반복 없이 1회 계산으로 결과 반환하므로 $O(1)의시간복잡도$