728x90

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

STL 연습겸 STL stack으로 풀긴 했지만 배열이 더 효율적일 듯한 문제.

1부터 n까지의 숫자가 순서대로 들어온다고 하니, 크게 답변 출력을 위한 문자 stack과 값 저장을 위한 int형 stack 두개를 선언한다.

int형 변수를 하나 선언해서 그거보다 큰 값이 들어오면 같아질때까지 stack에 push 후, 같아지면 pop하는 식으로 구현한다.

들어온 숫자가 int변수보다 작은 경우는 두가지일 것이다. top에 있어서 수열로 만들 수 있거나, 아니면 top에 없으므로 수열로 구현 불가능하거나.

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

int main() {
	// your code goes here
	stack<int> in;
	stack<char> ans, ans_;
	int a;
	cin >> a;
	
	for(int i = 0, j = 0 ; i < a ; i++){
		 int b;
		 cin >> b;
		 if(b > j){
		 	while(b != j){
		 		in.push(++j);
		 		ans.push('+');
		 	} 
		 }
		 if(b == in.top()){
		 	in.pop();
		 	ans.push('-');
		 }
		 else{
		 	cout << "NO";
		 	return 0;
		 }
	}
	
	
	while(!ans.empty()){
		ans_.push(ans.top());
		ans.pop();
	}
	while(!ans_.empty()){
		cout << ans_.top() << "\n";
		ans_.pop();
	}
	return 0;
}
728x90
728x90

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

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

Stack Data Structure and Implementation in Python, Java and C/C++ (programiz.com)

- 스택의 성질
  - 원소의 추가 / 제거에 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(); // 스택 최상단 데이터 확인
}
728x90
728x90

요세푸스 순열은 여기서 그려볼 수 있다. 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;
}
728x90
728x90

- 연결 리스트 : 각 데이터를 포인터를 이용해 다음 자료를 가리키도록 연결해둔 형태의 자료구조

  배열 연결 리스트
임의 원소 탐색 O(1) O(n)
임의 위치에 추가/제거 O(n) O(1) (위치 주소를 아는 경우)
O(n) (위치 주소를 모르는 경우)
메모리 배치 연속 불연속
Cache hit rate 높음 낮음

- 연결 리스트의 종류
  - 단일 연결 리스트 : 각 원소가 다음 원소를 가리킴
  - 이중 연결 리스트 : 각 원소가 이전/다음 원소를 가리킴 (STL의 list 자료형이 이중 연결 리스트)
  - 원형 연결 리스트 : 끝 원소가 다음 원소로 처음 원소를 가리킴

- 연결 리스트의 구현

//구조체를 이용한 구현
struct node{
	struct node *prev, *next;
    int data;
}

- 배열을 이용한 연결리스트의 구현

//배열을 이용한 연결리스트 구현
#include <algorithm>
const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX]; //dat : 데이터, pre/nxt : 이전/다음 원소 위치
int unused = 1; // 사용되지 않은 원소 인덱스
fill(pre, pre + MX, -1);
fill(nxt, nxt + MX, -1);

//모든 원소 순회
void traverse(){
	int cur = nxt[0];
    while(cur != -1){
    	cout << dat[cur] << ' ';
        cur = nxt[cur];
    }
}

void insert(int addr, int num){
	dat[unused] = num;
    
    pre[unused] = addr;
    nxt[unused] = nxt[addr];
    
    if(nxt[addr] != -1) pre[next[addr]] = unused;
    nxt[addr] = unused;
    unused++;
}

void erase(int addr){
	nxt[pre[addr]] = nxt[addr];
    pre[nxt[addr]] = pre[addr];
}

  - 메모리 문제가 있어 실제로는 쓰기 그렇고, 코테에서만 사용할 것

- STL list를 사용한 구현

#include <list>
int main(void){
  list<int> L = {1, 2};
  list<int>::iterator t = L.begin(); // list 원소를 가리키는 변수
  L.push_front(10); // 앞에 데이터 추가 O(1)
  L.push_back(10); // 뒤에 데이터 추가 O(1)
  L.insert(t, 6); // t가 가리키는 곳 앞에 6 삽입
  t = L.erase(t); // t가 가리키는 곳을 지우고, 다음 주소를 반환
  
  //연결리스트 순회
 	for(t = L.begin();t != L.end() ; t++){
		cout << *t;
	}
    
  // C++11 이상
   for(auto i : L) cout << i;
}
728x90
728x90

출처 : 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] << ' ';
}
728x90
728x90

- 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));
728x90
728x90

- 우리는 보통 연산을 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;

 

728x90
728x90

- 최대공약수(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;

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

728x90
728x90

- 소수 : 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의 배수 연산 때 이미 소수임이 판별되었으므로 연산할 필요가 없는 상태이다.

728x90
728x90

문제

피제수(분자) 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번째 자리수 소수가 된다.

728x90

+ Recent posts