본문 바로가기

전체 글199

[0x0A] DFS DFS depth first search 다차원 배열에서 각 칸을 방문할 때 깊이를 우선으로 방문하는 알고리즘 예시 모든 칸이 스택에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때 O(N) 시작하는 칸을 스택에 넣고 방문하는 표시를 남김 스택에서 원소를 꺼내서 그 칸과 상하좌우로 인접한 칸에 대해 (3)을 진행 해당 칸을 이전에 방문했다면 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 스택에 삽입 스택이 빌 때까지 (2)를 반복 #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int board[502][502] = { ... }; // 1.. 2023. 6. 26.

[0x09] BFS BFS breadth first search 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 과정 모든 칸이 큐에 1번씩 들어가므로 시간 복잡도는 칸이 N개일 때 O(N) 시작하는 칸을 큐에 넣고 방문했다는 표시 남기기 큐에서 원소를 꺼내어 그 칸에 상하좌우로 인접한 칸에 대해 (3)을 진행 해당 칸을 이전에 방문했다면, 아무 것도 하지 않고, 처음으로 방문했다면 방문했다는 표시를 남기고 해당 칸을 큐에 삽입 큐가 빌 때까지 (2)를 반복 // x가 행, y가 열 #include #include using namespace std; #define X first #define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용 int board[502.. 2023. 6. 26.

[0x08] 스택의 활용(수식의 괄호 쌍) 수식의 괄호 쌍 괄호쌍이 올바른지 체크 관찰 괄호 1종류 괄호 2종류 → 연속된 괄호 삭제는 가능 해결 방법 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다 2023. 6. 26.

[0x07] 덱 정의와 성질 정의 double-ended queue 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료 구조 성질 원소의 추가와 제거 : O(1) 제일 앞/뒤의 원소 확인 : O(1) 제일 앞/뒤이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 인덱스로 원소 접근 가능 기능과 구현 const int MAX = 1e7; int data[2*MAX + 1]; int head = MAX, tail = MAX; // 시작 지점을 배열의 중간으로 : 앞뒤로 확장 // head : 시작. tail : 다음에 들어갈 원소의 자리 void push_front(int x) data[--head] = x; void push_back(int x) data[tail++] = x; void pop_front() head++; v.. 2023. 6. 26.

[0x06] 큐 정의와 성질 정의 한쪽 끝에서 원소를 넣고 뺄 수 있는 자료구조 성질 원소의 추가와 제거 : O(1) 제일 앞/뒤의 원소 확인 : O(1) 제일 앞/뒤이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 기능과 구현 const int MAX = 1e7; int data[MAX]; int head = 0, tail = 0; void push(int x) data[tail++] = x; void pop() head++; int front() return data[head]; int back() return data[tail--]; STL queue #include 2023. 6. 20.

[0x05] 스택 정의와 성질 정의 한쪽 끝에서만 원소를 넣거나 뺼 수 있는 자료 구조 (restricted structure) 성질 원소의 추가와 제거 : O(1) 제일 상단의 원소 확인 : O(1) 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능 기능과 구현 구현 const int MAX = 1000005; int data[MAX]; int pos = 0; // 다음에 원소가 추가될 때 삽입해야 하는 곳 (스택 내 원소의 수) void push(int x) data[pos++] = x; void pop() pos--; int top() return data[pos-1]; STL stack #include 2023. 6. 20.

[0x04] 연결리스트 정의와 성질 성질 임의의 위치에 있는 원소를 확인/변경 : O(N) (불연속이기 때문에 그 원소까지 찾아가야 함) 임의의 위치에 원소를 추가/제거 : O(1) 원소들이 메모리 상에 연결되어 있지 않아 cache hit rate가 낮지만 할당이 다소 쉬움 종류 단일 연결 리스트 single linked list 이중 연결 리스트 doubly linked list 원형 연결 리스트 circular linked list 배열 vs 연결 리스트 overhead : 앞, 뒤 원소의 주소값을 가지고 있어야 한다 (2^n byte이면 n만큼 추가로 필요) 구현 struct Node { struct Node *prev, *next; int data; } 야매 연결리스트 const int MAX = 1000005; in.. 2023. 6. 20.

[0x03] 배열 배열 정의 메모리 상에 원소를 연속하게 배치한 자료구조 성질 O(1)에 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리의 양 overhead가 거의 없음 메모리가 붙어있으므로 cache hit rate가 높음 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림 연산 임의의 위치 원소 확인/변경 : O(1) 원소를 끝에 추가 / 마지막 원소 변경 : O(1) 임의의 위치에 원소 추가/제거 : O(N) → 뒤에 원소들 한 칸 뒤로 밀어야 함 초기화 전역변수로 선언할 경우 int는 0으로 초기화 지역변수는 쓰레기값 들어가기 때문에 { } 등으로 초기화해야 함 int a[21]; int b[21][21]; memset (비추천) memset(a, 0, sizeof a); memset(b, 0, .. 2023. 6. 20.

[0x02] 기초 코드 작성 요령 2 함수 인자 배열을 인자로 넘기면 주소값이 넘어간다 변수를 인자로 넘기면 복사된 값이 들어간다 & (reference)를 사용하면 참조 대상의 주소 정보만 넘어감 STL standard template library STL을 함수 인자로 넘길 때 그냥 STL을 함수 인자로 실어보내면 복사본을 넘기는 것 // 크기가 n인 vector 2개를 비교한다고 했을 때 // n만큼 복사하고 보내야 하기 때문에 O(N) 시간 복잡도 bool cmp1(vector v1, vector v2, int idx){ return v1[idx] > v2[idx] } 표준 입출력 공백 포함 문자열 입력 scanf와 cin 모두 공백 포함 문자열 입력이 까다롭다 해결 방법 scanf의 옵션 char a1[10]; scanf("%[^\.. 2023. 6. 20.

이전 1 2 3 4 5 6 ··· 23 다음

티스토리툴바