xxheexx

연결 리스트 원소들을 저장할 때 그 다음 원소가 있는 위치를 포함시키는 방식으로 저장하는 자료구조, 원소들은 이곳 저곳에 흩어져 있음 성질 k번째 원소를 확인/변경하기 위해 O(k) 필요 임의의 위치에 원소를 추가/제거는 O(1) 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당 다소 쉬움 연결 리스트의 종류 단일 - 각 원소가 자신의 다음 원소의 주소 이중 - 각 원소가 자신의 이전 원소와 다음 원소의 주소 list 원형 - 끝과 처음 연결 배열 vs 연결리스트 list #include using namespace std; int main(void) { list L = {1,2}; // 1 2 list::iterator t = L.begin(); // t는 1을 가리키는 중..

정의와 성질 배열 - 메모리 상에 원소를 연속하게 배치한 자료구조 성질 O(1)에 k번째 원소를 확인/변경 가능 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음 Cache hit rate가 높음 메모리 상에 연속한 구간을 잡아야해서 할당에 제약 임의의 위치에 원소 추가, 제거 - O(N) 사용팁 fill(arr, arr+arr.size(), 0); //0으로 채워줌 STL vector 배열과 거의 동일한 기능, 배열과 달리 크기를 자유자재로 늘이거나 줄일 수 있음 #include using namespace std; int main(void) { vector v1(3, 5); // {5,5,5}; cout

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

시간복잡도, 공간복잡도 시간복잡도 - 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계 제한 시간 1초 -> 프로그램이 3-5억번의 연산 안에 답을 내고 종료 빅오표기법 - 주어진 식을 값이 가장 큰 대표항만 남겨서 나타내는 방법 공간복잡도 - 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계 512MB = 1.2억개의 int 실수 자료형 1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다. 2. double에 long long 범위의 정수를 함부로 담으면 안된다. 3. 실수를 비교할 때는 등호를 사용하면 안된다. (둘의 차이가 아주 작다는 의미로 1e-12 사용 권장) int main(void){ double a = 0.1+0.1+0.1; double b = 0.3; if(a..

재귀 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘 재귀 함수의 조건 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함 (Base condition) 모든 입력은 base condition으로 수렴해야 함 재귀에서는 함수를 명확하게 정의해야한다! - 함수의 인자로 어떤 것을 받을지 - 어디까지 계산한 후 자기 자신에게 넘겨줄지 모든 재귀 함수는 반복문만으로 동일한 동작하는 함수 만들 수 있음 재귀는 반복문 구현보다 코드가 간결하지만 메모리/시간에서는 손해 -> 적절한 때에 재귀 구현 한 함수가 자기 자신을 여러 번 호출 -> 매우 비효율적!! 재귀함수가 자기 자신을 부를 때 스택 영역에 계속 누적이 됨 -> 스택 제한이 있는 경우 메모리 초과 날 수 있음 백준 11729번..

BFS (Breadth First Search) 다차원 배열에서 각 칸을 방문할 때 너비를 우선으로 방문하는 알고리즘 그래프에서 모든 노드를 방문하기 위한 알고리즘 예시 - (0,0)과 상하좌우로 이어진 모든 파란색 칸 BFS로 확인 (0,0) 방문했다는 표시 남기고 해당 칸 큐에 삽입 초기 세팅 끝난 후에는 큐가 빌 때까지 계속 큐의 front를 빼고 해당 좌효의 상하좌우를 살펴보면서 큐에 넣어주는 작업 반복 큐의 front는 (0,0)이고 pop (0,0)의 상하좌우 칸 확인 -> 파란색 칸이면서 아직 방문하지 않은 칸 큐 삽입 ...큐가 빌때까지 반복 큐가 비었을 때 확인해보면 (0,0)과 연결된 파란색 칸 모두 방문 완료 시간복잡도 : 모든 칸이 큐에 1번씩 들어가므로 칸이 N개일 때 O(N) 좌..

자바를 오랜만에 써서 기본 자료구조를 선언하는 방법이 헷갈리는 본인을 위한 정리 map Map map = new HashMap(); SortedMap sortedMap = new TreeMap(); queue Queue q = new LinkedList(); Queue 변수명 = new LinkedList(); //다른 자료형 넣기 가능 // 기본형: 우선순위가 낮은 숫자가 먼저 나옴 (작은 숫자) PriorityQueue pQ = new PriorityQueue(); // 우선순위가 높은 숫자가 먼저 나옴 (큰 숫자) PriorityQueue pQ = new PriorityQueue(Collections.reverseOrder()); stack Stack stackInt = new Stack(); de..

Greedy = 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘 이상적인 풀이 흐름 1. 관찰을 통해 탐색 범위를 줄이는 방법 고안 2. 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명 3. 구현해서 문제 통과 관련 문제 풀이 https://ssohee-coding.tistory.com/36

다이나믹 프로그래밍 여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘 문제를 해결하기 위한 점화식을 찾아낸 후 점화식의 항을 밑에서부터 차례로 구해나가서 답을 알아내는 형태 1. 테이블 정의하기 2. 점화식 찾기 3. 초기값 정하기 예제 - 백준 2 X n 타일링 (11726) #include using namespace std; int d[10005]; int mod = 10007; int main(void){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; d[1] = 1; d[2] = 2; for(int i = 3; i

상한 : 찾고자 하는 특정 값을 초과하는 '첫 위치' 반환 하한 : 찾고자 하는 특정 값 이상인 '첫 위치' 반환 -> 중복 값이 있을 때의 활용 arr1{1, 2, 2, 2, 3} 일 때 Key 값이 2이고, Upper Bound로 찾는다면 2를 초과되는 처음 위치인 arr[4] = 3인 index 4 반환 Lower Bound로 찾게 된다면 2 이상 위치 중 처음 위치인 arr[1] = 2인 index 1 반환 중복 원소에서 가장 끝 값(가장 오른쪽 값)을 찾고자 한다면 Upper Bound - 1 중복 원소 중 가장 왼쪽 끝 값(가장 왼쪽 값)을 찾고자 한다면 Lower Bound 그대로 private static int lowerBound(int[] arr, int key) { int lo = 0..