바킹독의 실전 알고리즘 : 스택

정의와 성질스택은 LIFO이다. 큐, 덱, 스택 같은 특정 위치에서만 원소를 넣거나 뺄 수 있는 제한된 자료구조를 Restricted Structure라고 부른다. 스택의 성질원소의 추가 O(1)원소의 제거 O(1)제일 상단의 원소 확인 O(1)나머지 원소들의 확인/변경 원칙적으로 불가능 기능과 구현const int MX=1000005;int dat[MX];int pos=0;일단 여기서 원소를 담은 큰 배열과 인덱스를 저장할 변수 한 개만 있으면 구현이 가능하다. pos는 원소의 개수이자 추가할 때 삽입해야 하는 인덱스를 의미한다. #include using namespace std;const int MX=1000005;int dat[MX];int pos=0;void push(int x){ dat[..

• format_list_bulleted coding/바킹독
• · 2026. 2. 15.

바킹독의 실전 알고리즘 : 연결 리스트

정의와 성질연결 리스트의 성질 k번째 원소를 확인/변경하기 위해 O(k)이미 정한 위치에 추가 및 제거는 O(1)메모상에 연속된 데이터는 아니라서 cache hit rate는 낮고, 할당은 쉬움 연결리스트 종류단일 연결 리스트 이중 연결 리스트 : 양방향으로 연결되어 있어서 이전 이후 원소 주소를 둘 다 들고 있다. 원형 연결 리스트 : 사이클 돈다 생각하면 편하다. 기능과 구현struct NODE { struct NODE *prev, *next; int data;};손코딩 문제 1원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때 해당 List의 길이를 효율적으로 구하는 방법? 효율적으로 구하라 -> 시간복잡도와 공간복잡도를 생각해봐야 한다. 동일한 노드가 나올 때까지 계속 다음 노드로 ..

• format_list_bulleted coding/바킹독
• · 2026. 2. 15.

바킹독의 실전 알고리즘 : 배열

정의와 성질배열 : 메모리 상에 원소를 연속하게 배치한 자료구조 O(1)에 k번째 원소 확인 가능 오버헤드 거의 없음 hit rate 높음 -> CS 확실히 중요하네.. 연속된 자료구조이기 때문에 할당에 제약이 있다 -> 메모리상에도 연속적 기능과 구현#include using namespace std;void insert(int idx, int num, int arr[], int& len){ for(int i=len;i>idx;i--) // i가 길이부터 시작이니까 arr[i]=arr[i-1]; //i-1이 맞는 위치(?) 맞는 배열의 인덱스, 1번째 원소 인덱스 번호는 0 arr[idx]=num; //그리고 넣어준다. len++; //len도 하나 늘어난다. }void erase(int..

• format_list_bulleted coding/바킹독
• · 2026. 2. 15.

바킹독의 실전 알고리즘 : STL과 함수 인자, 표준 입출력

STL과 함수 인자void func(int a){ a=5;}int main(void){ int t=0; func(t); coutvoid func(int arr[]){ arr[0]=10;}int main(void){ int arr[3]={1,2,3}; func(arr); coutstruct pt{ int x,y;};void func(pt a){ a.x=10;}int main(void){ pt tmp={0,0}; func(tmp); cout3번째 구조체도 변수 넘겨주는 거랑 같게 이해하면 됨 -> 복사call 방법call by value -> 안 바뀜, 공간 하나 더 생김 call by address -> 바뀜 (배열)call by ref..

• format_list_bulleted coding/바킹독
• · 2026. 2. 14.

바킹독의 실전 알고리즘 : 시공간 복잡도, 정수 자료형, 실수 자료형

시간복잡도와 공간복잡도컴퓨터는 1초에 대략 3-5억개 정도의 연산을 처리할 수 있다. 연산이 단순 연산인지, 나눗셈, 곱셈, 함수 호출 같은 복잡한 연산인지에 따라 약간의 차이는 있을 수 있다. int func1(int arr[], int n){ int cnt =0; for(int i=0;i위와 같은 코드가 있다. 여기서의 연산 횟수를 확인해보자 int func1(int arr[], int n){ int cnt =0; //1번 for(int i=0;i1+1+5n+1= 5n+3 문제최선의 경우 1초 (바로 정답)최악의 경우 n초 (가장 나중이 정답)평균은 중간에 있을 때 n/2 문제최선의 경우 1초 최악의 경우는..n명이 있는데가운데에 질의해서 왼쪽, 오른쪽으로 방향을 나누고또 가운..

• format_list_bulleted coding/바킹독
• · 2026. 2. 13.

GURU 2 android

보호되어 있는 글입니다.

• format_list_bulleted coding/+
• · 2024. 8. 14.