Study/자료구조 | 알고리즘 (6) 썸네일형 리스트형 알고리즘(1) - 그리디 - 최적의 해에 가까운 값을 구하는 방법이나, 최적의 해라고 확신할 수는 없음 (근사치 추정) => 한계 - 매 순간 최적이라고 생각되는 경우 한 가지를 선택하는 방법 - 동적 계획법의 computation complexity를 극복하기 위해 나온 기법 1. 동전 문제 - 최종 지불 가격 = 4720 - 1원, 50원, 100원, 500원 동전을 가지고 최소한의 동전 개수로 지불하는 방법 => 가장 큰 동전으로 먼저 지불하고, 남은 금액이 해당 동전보다 적은 경우 다음 동전으로 지불하는 방식 => 그러면 일단 동전의 크기가 큰 순서대로 sorting def paiedCoin(coins, pay): result = list() count = 0 coins.sort(reverse = True) # 큰 순서대.. 4. 자료구조 - 트리 1. 트리 구조 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 : 이진트리의 구조로 탐색 알고리즘 구현을 위해 주로 사용 : 장점 - 배열에 비해서 탐색 시간이 크게 줄어듦 -> 시간 복잡도: O(logn) : 레벨을 거칠 때마다 탐색이 1/2씩 일어남 - 관련 basic 용어 : Node) 데이터와 다른 데이터에 연결된 branch 정보를 포함 : Root (최상위) / Parent ( 상위 레벨) / Child (다음 레벨) / Sibling (같은 부모 노드) / Leaf (마지막 노드) : Level) Root가 Level 1, 아래로 갈수록 레벨이 높아짐 : Depth) 트리에서 노드가 가질 수 있는 최대 Level 2. 이진 트리와 이진 탐색 트리 ( Bin.. 3. 자료구조 - 해쉬 테이블 1. 해쉬 테이블 : Key와 Value를 저장하는 데이터 구조 : Key값을 해시 함수에 적용한 결과를 통해 저장한 데이터(Value)에 접근할 수 있음 : 장점) 데이터 접근/검색 속도가 굉장히 빠름 -> 충돌이 없는 경우, 시간 복잡도 = O(1) , 특정 Key에 대한 데이터가 있는지/중복을 확인하기 쉬움 : 단점) 보통 배열로 미리 해쉬 테이블 사이즈만큼을 생성 후 사용 (공간과 탐색 시간의 trade-off), 여러 키에 해당하는 해쉬 주소가 동일할 경우, 충돌을 해결하기 위한 별도의 자료구조가 필요 (ex- 링크드 리스트) : 활용) 검색/저장/삭제/읽기가 빈번하게 필요한 경우, 캐시 구현 (중복 확인이 쉽기 때문) ex - 파이썬의 딕셔너리 구조 : Key값에 해싱 함수(Hashing Fu.. 2. 자료구조 - 링크드 리스트 [Python으로 진행하는 자료구조 공부] 1. 링크드 리스트 : 순차적으로 연결된 공간에 데이터를 넣는 구조인 배열과 달리, 저장공간이 떨어져 있어도 포인터로 연결해서 관리하 는 데이터 구조 : 기본 구조 - 노드 (Node) : 링크드 리스트의 한 데이터블럭 --> (데이터 값, 포인터)의 구조로 이루어짐 - 포인터 (Pointer) : 각 노드에서, 다음 또는 이전 노드의 연결 정보 (그 노드의 주소 정보)를 가지고 있는 공간 : 장점 - 미리 사용할 데이터 공간을 할당하지 않아도 됨 : 단점 - 연결 정보를 담는 공간이 따로 필요하기 때문에 공간 효율이 그리 좋지 않음 - 원하는 정보에 접근하는데 시간이 걸림 - 삽입이나 삭제가 일어날 때, 포인터들의 정보를 다시 설정해줘야하는 번거로움이 있음 *.. 1. 자료구조 - 배열, 큐, 스택 [Python으로 진행하는 자료구조 공부] 단순히 혼자 기억을 상기시키는 목적의 글입니다 틀린 부분이 있을 수도 있으니, 발견 시 댓글로 남겨주시면 감사하겠습니다 :) 1. 배열 : 동일한 타입의 데이터를 순차적으로 저장하는 구조 : 각 데이터에 접근하기 위해서 인덱스를 활용함 - 장점 : 인덱스를 활용하므로 데이터 요소에 접근이 쉬움 - 단점 : 최대 배열 크기를 초기에 설정해 둬야 함. 따라서 데이터의 삭제와 삽입이 어려울 수 있음 잔여 공간 크기보다 큰 데이터를 추가할 경우 추가가 불가능하며, 정해진 크기의 배열에서 데이터 일부를 삭제하는 경우 저장 공간의 낭비가 발생함 * 파이썬은 배열 기능을 리스트 타입이 제공함 - 1차원 배열 : 인덱스는 0부터 시작. - 2차원 배열 : 배열이 2차원이므로 .. 0. 자료구조 / 알고리즘 진로 결정을 너무 늦게 한 나머지, 컴퓨터 공학 부전공 이제야 시작했다. 그 결과, 기본 중에 기본이라는 자료구조와 알고리즘 수업조차도 이수하지 못한 상태다. 하지만, 이 관련 분야로 어떤 것을 하든 코딩테스트를 보고 코테는 알고리즘을 익히고 있느냐가 기본 베이스이므로 공부를 해야겠다 하고 마음먹게 되었다. 그냥 독학을 하는데에는 한계가 있다고 생각돼서, 친구와 함께 인터넷 강의를 듣는 스터디를 하기로 했다. 주 언어는 파이썬이므로, 파이썬을 이용하여 자료구조와 알고리즘 공부를 할 예정이며 매주 공부한 내용을 스스로 기록하고자 내용을 업로드하고자 한다. 이전 1 다음