전체 글108 [이코테] chapter08 다이나믹 프로그래밍 오랜만에 백준 하나 풀려고 했더니 다이나믹 프로그래밍 문제이길래..! 돌아왔답니당 아래 글은 [이것이 코딩 테스트다 wiht 파이썬] 책을 기반하여 작성한 글입니다. 다이나믹 프로그래밍 : 효큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘. (1) 다이나믹 프로그래밍 문제? 큰 문제를 작은 문제로 나눌 수 있다. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 메모이제이션(Memoization): 다이나믹 프로그래밍을 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 그대로 가져오는 기법. 시간 복잡도: O(N) (2) 다이나믹 프로그래밍 풀이 방식 ▶️ Top-Down 방식 : 큰 문제를 해결하기 위해 작은 문제를 .. 2024. 2. 5. [실전문제연구단] Siamese Network, Contrastive Loss, Triplet Loss 드디어 연구 주제를 정하고 본격 연구에 들어가게 되었습니다! 그래서 연구에 필요한 개념인 "Siamese Network"에 대해 기록해보도록 하겠습니다. Few-shot learning을 공부하다가 알게된 Siamese Network! (샴 네트워크라고 부르겠음) 샴 네트워크는 샴 쌍둥이로부터 착안된 개념. 샴 쌍둥이는 신체의 일부를 공유하는데, 샴 네트워크 역시 weight를 공유해서 그 이름을 가지게 됨. 2015년 논문 " Siamese Neural Networks for One-shot Image Recognition "에서 처음 제시됨. https://www.cs.cmu.edu/~rsalakhu/papers/oneshot1.pdf 위의 그림처럼 두 그림으로 이루어진 한 pair와 둘의 same,.. 2024. 1. 11. [자료구조] 13장 Search 1. 탐색 : 여러 개의 자료 중에서 원하는 자료를 찾는 작업 2. Map dictionary : 키-값 쌍을 테이블에 저장 3. 순차 탐색 : 정렬 안된 배열을 처음부터 마지막까지 하나씩 검사 - 시간 복잡도: O(n) - 평균 비교 횟수: (n+1)/2 4. 이진 탐색 : 정렬된 배열 탐색에 적합. 탐색의 범위를 반으로 줄여가면서 탐색 진행. - 시간 복잡도: O(logn) 5. 색인 순차 탐색 : 인덱스 테이블을 사용. 모두 정렬되어 있어야함. - 시간 복잡도: O(m+n/m), m은 인덱스 테이블 크기, n은 주자료 크기 6. 보간 탐색 : 사전이나 전화번호부를 탐색하는 방법, 탐색키가 존재할 위치를 예측하여 탐색하는 방법 이진 탐색과 유사하지만, 보간 탐색은 불균등 분할해 탐색 - 시간 복잡도:.. 2023. 12. 17. [자료구조] 12장 Sort 1. 정렬 : 데이터를크기순으로 오름, 내림 차순으로 나열하는 것 - 정렬의 대상: 레코드 - 종류 단순하지만 비효율적인 방법: 삽입,선택, 버블 정렬 복잡하지만 효율적인 방법: 퀵, 힙, 합병, 기수 정렬 2. 선택 정렬 : 가장 작은 값과 정렬 안 된 값들 중 가장 앞에 있는 값을 교환 - 시간 복잡도: O(n^2) - 특징: 매우 간단. 비효율적. 안정성 만족 안함. 3. 삽입 정렬 정렬되어 있는 부분에 새로운 레코드를 올바른 위치에 삽입하는 과정 - 시간 복잡도: O(n^2) - 특징: 많은 이동 필요. 안정됨. 대부분 정렬되어 있으면 효율적. 4. 버블 정렬 : 인접한 2개 레코드를 비교해 바꿈 - 시간 복잡도: O(n^2) - 특징: 많은 이동 필요. 5. 셸 정렬 : 삽입 정렬은 어느정도 정.. 2023. 12. 17. [자료구조] 11장 그래프 1. 그래프 - 오일러 정리: 모든 정점에 연결된 간선의 수가 짝수이면 오일러 경로가존재함. - 동일한 그래프? 배열로 정점의 집합과 간선의 집합을 나타냈을 떄 두 배열이 다른 그래프의 배열과 동일할 때. - 방향그래프, 무방향 그래프, 가중치 그래프, 부분 그래프 2. 그래프 용어 인접 정점 - 자신과 간선으로 직접 연결된 정점 차수 - 자신과 연결된 정점의 수 그래프의 경로 경로의 길이 - 경로를 구성하는데 사용된 간선의 수 단순 경로 - 경로 중에 반복 간선이 없는 경로 사이클 - 시작 정점과 종료 정점이 동일한 경로 연결 그래프 - 모든 정점쌍에 대한 경로 존재 트리 - 그래프의특수한 형태. 사이클이 없음 완전 그래 - 모든 정점이 연결되어 있는 그래프 3. 그래프 표현 방법1: 인접행렬 4. 그.. 2023. 12. 16. [자료구조] 9장 Priority Queue 1. Priority Queue : 우선순위가 높은 데이터가 먼저 나감. 배열/연결리스트/힙으로 구현 가능. 2. Heap 완전 이진 트리 최대 힙: 부모 노드의 키 값이 자식노드의 키값보다 크거나 같음 최소 힙: 부모 노드의 키 값이 자식노드의 키 값보다 작거나 같음 힙은 배열을 이용해 만들면 효율적. 완전 이진 트리 -> 각 노드에 번호를 붙임 -> 배열의 인덱스 3. Upheap(삽입) 새로운 요소가 들어오면 일단 마지막 노드에 이어서 삽입 삽입된 위치에서 루트까지의 경로에 잇는 노드들을 비교, 교환 키가 부모 노드보다 작거나 같으면 종료. O(logn) 4. Downheap(삭제) 루트 삭제. 루트에서부터 단말 노드까지의 노드들을 교환해 힙 성질 만족. O(logn) 5. 힙정렬 n개의 요소를 최.. 2023. 12. 16. [자료구조] 8장 BST 1. BST : 이진 트리 기반 효율적인 탐색 가능 2. 이진 탐색 트리 정의 : key(왼쪽 서브트리) = 루트 -> 오른쪽으로 순회하는 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있음. 3. 이진 탐색 트리의 탐색 연산 4. 이진 탐색 트리의 삽입 연산 : 탐색을 하다가 실패한 위치가 새로운 노드 삽입의 위치. 5. 이진 탐색 트리의 삭제 연산 case1) 단말 노드 삭제: 부모 노드 찾아서 연결 끊음. case2) 자식이 하나인 노드 삭제: 노드 삭제하고 서브트리를 부모 노드에 붙임. case3) 두 개의 자식을 가진 노드 삭제: 가장 비슷한 값을 가진 노드를 삭제 노드 위치로 가져옴. 6. 이진 탐색 트리의 성능 : 이진 탐색 트.. 2023. 12. 16. 이전 1 2 3 4 5 6 7 ··· 16 다음
