Taene's

스택삽입과 삭제 연산이 후입선출(LIFO)로 이뤄지는 자료구조위치top: 삽입/삭제가 일어나는 맨 위의 위치연산push: top 위치에 새 데이터 삽입pop: top 위치에 현재 있는 데이터 삭제top: top 위치에 현재 있는 데이터 확인관련 알고리즘: DFS, 백트래킹 종류 (후입선출 개념 자체가 재귀 함수 알고리즘 원리와 일맥상통함.) 스택 관련 문제들백준 1874 (실버2)#include #include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int n; cin >> n; stack num_sequence; vector answer; int num = 1; f..

배열의 특징인덱스를 사용해 값에 바로 접근할 수 있다.새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입/삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다. 리스트의 특징값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조이다.인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 한다. 다시 말해 값에 접근하는 속도가 느리다.포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠르다.선언할 때 크기를 별도로 지정하지 않아도 된다. 다시 말해 리스트의 크기는 정해져 있지 않으며, 크기가 변하기 쉬운 데이터를 다룰 때 적절하다.포인터를 ..

슬라이딩 윈도우범위를 지정하고, 범위를 유지한 채로 이동하며 문제를 해결한다.투 포인터 알고리즘과 비슷하다.슬라이딩 윈도우의 크기(탐색 범위)는 일정하다. 관련 문제들백준 12891 (실버2)#include #include #include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int s, p; cin >> s >> p; //dna문자열의 길이 s, 비밀번호로 사용할 부분 문자열의 길이 p string dnaString; cin >> dnaString; char ACGT[4] = { 'A','C','G','T' }; int ACGTNum['Z'] = {}; // A,C,G,T 각각의..

Big-O 표기법의 설명O(1) 상수 시간문제 해결을 위해 오직 한 단계만 거침입력되는 데이터 양과 상관없이 일정한 시간 동안 실행O(log n)로그 시간입력 데이터의 크기가 커질수록 처리 시간이 로그(log) 만큼 짧아지는 알고리즘입력값 n이 주어졌을때, 문제를 해결하는데 필요한 단계들이 연산마다 특정요인에 의해 줄어듬입력 데이터 10 투입되면 시간은 2배가 걸림O(n)직선적 시간문제를 해결하기 위한 단계의 수와 입력 데이터의 크가 n이 1:1 관계를 가지는 알고리즘예) 1차원 for loopO(n log n)선형 로그 시간입력 데이터의 크기가 커질수록 처리 시간이 로그(log) 만큼 늘어나는 알고리즘예) 입력 데이터 10 투입되면 시간은 20배가 걸림대표적 알고리즘: 병합 정렬 알고리즘, 퀵 정렬 알..

투 포인터2개의 포인터를 이용해 알고리즘의 시간 복잡도를 최적화한다.시간 복잡도에서 N의 최댓값이 10,000,000 처럼 매우 크게 잡혀 있는 경우, O(nlogn)의 시간 복잡도 알고리즘을 사용하면 제한 시간을 초과하므로 O(n)의 시간 복잡도 알고리즘을 사용해야 하는데, 이런 경우 투 포인터 알고리즘을 자주 사용한다. 관련 문제들백준 2018 (실버5)#include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N; cin >> N; int start_index = 1; int end_index = 1; int cnt = 1; int sum = 1; while (end_ind..

구간 합의 핵심 이론합 배열 S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] ( 배열 A의 0~i까지의 합 배열 S)합 배열을 미리 구해놓으면, 기존 배열의 일정 범위의 합을 구하는 시간 복잡도가 O(N) -> O(1)로 감소한다.합 배열 S를 만드는 공식S[i] = S[i-1] + A[i]구간 합을 구하는 공식S[j] - S[i-1] ( i~j까지의 구간 합) 관련 문제들백준 11659 (실버3)#include using namespace std;int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int N, M; int k; cin >> N >> M; int sum[100001] = {};..