해나의 컴공생존기

1. 알고리즘 설명 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 시작하는 칸을 큐에 넣고 방문했다는 표시를 남김 큐에서 맨 앞의 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 3번을 진행 해당칸을 이전에 방문했다면 아무것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 큐가 빌 때까지 2번을 반복 시간복잡도는 모든 칸이 큐에 한번씩 들어가므로 칸이 N개일 때 O(N)이된다. 2. 코드 BFS는 코딩테스트에서 굉장히 중요한 부분이므로 꼭 잘 숙지해야함! #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int bo..

주어진 괄호 문자열이 올바른지 판단하는 것! 어떻게 판단해야할까? 괄호쌍을 찾아야함! 연결리스트로도 구현가능하지만 스택으로도 가능! 여는 괄호면 스택에 넣고 닫는괄호는 스택의 맨 뒤에있는 괄호와 짝 짓기! 짝이 안맞거나, 여는괄호와 닫는괄호의 개수가 맞지않을때 틀린 수식이라는것을 알아 챌 수 있음

스택이란 선입후출의 자료구조이다. 원소의 추가,제거,제일상단의 원소확인이 O(1)에 가능하지만 다른 위치의 원소확인과 변경이 원칙적으로 불가능하다. 하지만 배열과 연결리스트로 스택을 구현한다면 가능하다. 1. 배열로 스택 구현하기 cosnt in MX=1000005; int dat[MX]; int pos=0 //위치 void push(int x){ dat[pos++]=x; } void pop(){ pos--; } void top(){ dat[pos-1]; } 2. STL #include using namespace std; int main(void) { stack S; S.push(10); // 10 S.push(20); // 10 20 S.push(30); // 10 20 30 cout

연결리스트 원소들을 저장할 때 그 다음 원소가 있는 위치를 저장하는 자료구조 특징 k 번째 원소를 확인하기 위해 O(k)가 필요하다 임의의 위치에 원소를 추가,제거는 O(1) 종류 단일 연결리스트 이중 연결리스트 원형 연결리스트 배열 vs 연결리스트 // 연결리스트에 원소를 넣었다가 뺏다하는 함수 #include using namespace std; const int MX = 1000005; int dat[MX], pre[MX], nxt[MX]; int unused = 1; void insert(int addr, int num) { dat[unused] = num; pre[unused] = addr; nxt[unused] = nxt[addr]; if(nxt[addr]!=-1) // 맨 끝에 삽입하는게 아..

배열 : 메모리 상에 원소를 연속하게 배치한 자료구조 특징 - k 번째 원소를 확인, 변경가능 - 추가적으로 소모되는 메모리의 양(overhead)이 거의 없음 -Cache hit rate가 높음 - 메로리 상에 연속한 구간을 잡아야해서 할당에 제약이 걸림 기능 - 배열 추가, 삭제, ghkrdls O(1) - 임의의 위치에 원소 추가, 삭제 O(N) // 배열 임의의 위치에 추가, 삭제하는 코드 #include using namespace std; void insert(int idx, int num, int arr[], int& len) { if (len != idx) { for (int i = len; i > idx;i--) { arr[i] = arr[i - 1]; } } arr[idx] = num;..

1) 시간 복잡도 시간복잡도 : 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계 빅오표기법 : 주어진 식을 가장 큰 대표항만 남겨서 나타내는 방법 ex. O(N) : 5N+3 , 2N+2 연습문제 /* 문제1 N 이하의 자연수 중에서 3의 배수이거나 5의 배수인 수를 모두 합한 값을 반환하는 함수 func1(int N)을 작성하라. N은 10만 이하의 자연수이다. */ void func1(int N) { int sum = 0; for (int i = 1; i < (N + 1); i++) { if (i % 5 == 0 || i % 3 == 0) { sum += i; } } cout