21/10/30에 진행된 학교 프로그래밍 경진대회에 참가했다.

알고리즘 스터디를 진행한지 대략 두달 정도 지난 시점이라 직접 대회에서 얼마나 늘었는지 체감해보고 

다시 한 번 실력을 점검해보는 좋은 기회가 될 것 같아 스터디원 모두 대회에 참가하여 문제를 풀었다.

 

코로나로 인해 비대면으로 진행됐고 백준 티어 기준 브론즈~플래티넘까지 다양한 난이도의 문제들이 출제됐다.

결과부터 말하자면 입상은 하지 못했지만 전체 학년에서 20등대에 들어 게임키 경품을 받았다!

입상을 하지 못한게 아쉽긴하지만 아직 알고리즘 공부를 시작한지 별로 안됐으니까 4학년 때 다시 입상을 노려보고싶다.

 

이번 대회를 통해 느낀 게 있다면 알고리즘 고수들의 문제푸는 속도가 생각보다 더 빠르다는 것과 문제를 처음부터 잘 읽고 푸는게 시간을 아끼는 길이란 걸 다시 한 번 느낄 수 있었다. 또한, 테스트 케이스가 통과하더라도 계속 틀렸습니다가 뜨면 히든케이스를 찾아서 오류를 예외 처리하는 것도 중요하지만 알고리즘 자체 로직에 문제가 있진 않으지 다시 점검해보는 것도 좋을 것 같다는 생각이 들었다. 

 

나중에 공개된 문제별 난이도 티어를 확인해보니 브론즈~실버 문제는 풀 수 있었고 골드 문제부터는 구현하기가 쉽지 않았다. 알고리즘 스터디를 진행하기전 티어가 실버5였고 2달이 지난 지금 실버2가 됐는데 다음 대회가 열릴 땐 골드 문제까지 잘 풀 수 있는 실력을 만들어 참가하고 싶다. 

 

 

덱(Deque)이란?

벡터의 단점을 보완하기 위해 만들어진 컨테이너

새로운 원소가 삽입될 때마다 메모리 재할당 후 이전의 값들을 복사하는 벡터와 달리

덱은 미리 일정한 크기의 메모리 블록을 할당해 둔 후 값을 저장함.

데이터의 삽입과 삭제의 위치가 정해진 큐와 달리 덱은 앞 뒤로 다 데이터를 삽입/삭제 할 수 있음

 

헤더파일 삽입

#include <deque>

using namespace std;

데이터 생성

deque <type> dq;

deque dq;

deque dq(10);

0으로 초기화된 10개 원소 가진 덱 생성

deque<int> dq = { 1, 2, 3 };

deque dq2(dq1);

dq1의 내용을 복사한 덱 dq2 생성

데이터 삽입/삭제

dq.push_front(3);

첫 번째 원소 앞에 5 삽입

dq.push_back(4);

마지막 원소 뒤에 4 추가

dq.insert(2, 5);

2번째 위치에 5 추가

dq.insert(2, 5, 4);

2번째 위치에 5개의 데이터 값 4 추가

dq.pop_front();

첫 원소 삭제

dq.pop_back();

마지막 원소 삭제

dq.clear();

데이터 다 삭제

iterator

dq.begin()

첫 번째 원소 iterator

dq.end()

마지막 원소의 다음! iterator

데이터 조회

dq.at(idx);

idx번째 데이터 참조

dq[idx];

덱 사이즈

dq.size();

데이터 개수 리턴

dq.resize(10);

덱의 크기를 10으로 변경크기가 더 증가했다면 0으로 채움

dq.resize(10,2);

덱의 크기를 10으로 변경

크기가 더 증가했다면 2로 채움

 

참고사이트

https://blockdmask.tistory.com/73

https://velog.io/@choiiis/C-STL-deque%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%A0%95%EB%A6%AC

'프로그래밍 언어 > c++' 카테고리의 다른 글

C++ sort 함수 compare 커스터마이징  (0) 2022.06.03
[Algorithm] c++ 순열 구하는 함수 next_permutation, prev_permutation  (0) 2022.05.04
[STL] 큐(Queue)  (0) 2021.10.11
[STL] vector 컨테이너  (0) 2021.09.19
STL  (0) 2021.09.19

큐에 대한 자료구조 설명

https://cofls6581.tistory.com/118

 

큐(queue)

큐(queue)? 선입선출 FIFO(first in first out)방식의 자료구조 ex)마트 계산대, 은행 창구: FIFO방식 주로 배열이나 연결리스트로 구현함 주로 순차적인 프로세스를 구현할 때 사용함 자료가 삽입되는 곳

cofls6581.tistory.com

헤더파일 삽입

#include <queue>

데이터 선언

queue<int> q;

데이터 추가/삭제

q.push(2);

q.pop(); front 데이터를 삭제

데이터 조회

q.front(); 최상위 데이터 반환

q.back(); 제일 마지막 데이터 반환

데이터 크기

q.size();

q.empty(); 비어있으면 true 아니면 false

데이터 swap

swap(queue1 , queue2); 두 큐의 내용 swap

 

참고사이트

https://life-with-coding.tistory.com/408

'프로그래밍 언어 > c++' 카테고리의 다른 글

[Algorithm] c++ 순열 구하는 함수 next_permutation, prev_permutation  (0) 2022.05.04
[STL] 덱(Deque)  (0) 2021.10.12
[STL] vector 컨테이너  (0) 2021.09.19
STL  (0) 2021.09.19
C++ break 문과 continue문  (0) 2021.09.12

다이나믹 프로그래밍

하나의 문제는 한 번만 계산하는 알고리즘으로 큰 문제를 작은 문제로 나누어 푸는 알고리즘

 

다이나믹 프로그래밍을 사용하기 위한 조건

-작은 문제로 나눌 수 있을 때

-작은 문제의 답이 그것을 포함하며 더 큰 문제에서도 답이 동일하게 나올 때

 

다이나믹 프로그래밍 원리

메모이제이션을 활용해 작은 문제에서 계산한 결과 값을 배열에 저장해두고

나중에 큰 문제에서 그 값이 다시 필요할 때 동일한 계산을 진행하지 않고 저장된 값을 반환받아서 계산

+메모이제이션

결과를 저장해 함수가 한 번만 실행되는 것을 보장하는 기술

동적계획법을 쓸 때 많이 사용한다.

 

다이나믹 프로그래밍 구현법

1. 탑-다운

재귀함수로 구현할 때 대부분 탑-다운 방식을 사용하며 큰 문제를 풀 때

작은 문제 값이 없다면 그 때 작은 문제의 값을 계산함.

2. 다운-탑

작은 문제부터 먼저 계산하여 큰 문제의 값을 계산함.

 

다이나믹 프로그래밍 점화식 찾는 법

1. 작은 문제들의 값(0,1,2,3,3)들을 직접 계산해보면 점화식이 보임

그 점화식을 활용해 다이나믹 프로그래밍을 구현하면 됨.

2. 이전 단계에서 다음 단계로 가는 가짓수가 정해져있다면 그걸 이용해도 됨

   ex. 도형을 쪼갤 때 특정한 규칙으로만 쪼개져서 n-2단계/n-1단계에서 n이 되는

        가짓수가 정해져있을 경우

 

분할 정복 vs 다이나믹 프로그래밍

분할 정복은 단순히 큰 문제를 작은 문제로 나누어 푸는 것으로 작은 문제의 답이 항상

큰 문제의 답이 되지 않아 작은 문제를 여러 번 반복적으로 계산해야 함.

반면에 다이나믹 프로그래밍은 작은 문제 계산을 중복적으로 하지 않고 작은 문제의 답이

큰 문제에서도 변하지 않음을 이용함

 

 

 

참고 사이트

https://blog.naver.com/ndb796/221233570962

https://galid1.tistory.com/507

break;은 해당 반복분 탈출

return;은 해당 함수 탈출

 

break문 예시

int func(){
	while(1){
	    if(조건)
	    	break;
	     a++;
	}	
	b++;
}

조건 참일시 a++ 실행 x 반복문 탈출 후 b++은 실행

 

return문 예시

int func(){
	while(1){
	    if(조건)
	    	return;
	     a++;
	}	
	b++;
}

a++,b++ 둘 다 실행 x

vector 컨테이너

-가변 길이 배열을 구현한 제네릭 클래스

-스스로 내부 크기를 조정하므로 개발자가 크기에 대해 고민한 필요가 없는 장점

-배열의 원소를 저장, 삭제, 검색하는 멤버 함수들을 제공

-인덱스 0부터 시작

 

vector 사용

#include<vector>

using namespace std;

vector 멤버 함수

▶vector 객체 생성

vector<int> v;

비어있는 벡터 v 생성

vector<int> v(3);

0으로 초기화된 3개 원소 벡터 v 생성

vector<int> v(3,2);

2로 초기화된 3개 원소 벡터 v 생성

vector<int> v2(v1);

v1 벡터 복사해서 v2벡터 생성

▶vector 원소 삽입

v.push_back(2);

벡터 v에 2 삽입

v.insert(3,2);

벡터 v의 위치 3에 2 삽입

v.insert(3,5,3);

3의 위치에 5개의 3 삽입

그다음 값들이 뒤로 밀림

▶vector 원소 삭제

v.clear();

모든 원소 제거, 메모리는 남아있음

v.pop_back();

벡터 v의 마지막 원소 삭제

v.erase(iter);

반복자 iter가 가리키는 원소에 접근해서 벡터 v의 원소 삭제

사이즈는 줄어들고 메모리는 남아있음

▶vector 원소 접근

v[idx];

idx번째 원소 접근

v.at(idx);

idx번째 원소 접근

v.front();

첫 번째 원소 접근

v.back();

마지막 원소 접근

v.begin();

반복자로 접근 시 제일 처음 데이터의 위치 가리킴

v.end();

반복자로 접근 시 제일 마지막 데이터의 위치 가리킴

▶vector 사이즈

v.size();

원소 갯수 리턴

v.capacity();

할당된 공간의 크기 리턴

v.empty();

비어있으면 true 리턴 아니면 false 리턴

비어있다의 기준은 사이즈 O 용량 X

v.resize(5);

벡터 v의 크기를 5로 변경

v.resize(5,10);

벡터 v의 크기를 5로 변경한 후 값 10으로 초기화

 

 

참고

서적: 명품 C++ 프로그래밍

사이트: https://blockdmask.tistory.com/70

https://life-with-coding.tistory.com/411

'프로그래밍 언어 > c++' 카테고리의 다른 글

[STL] 덱(Deque)  (0) 2021.10.12
[STL] 큐(Queue)  (0) 2021.10.11
STL  (0) 2021.09.19
C++ break 문과 continue문  (0) 2021.09.12
visual studio LINK2005 에러  (0) 2021.09.08

+ Recent posts