목록알고리즘 (5)
개발새발
최적의 상황을 찾는것 자체가 정렬을 한 후 인덱스 번호끼리 비교하는 것이라고 생각 짐나르기 1. 항상 나갈 수 있는 최적을 찾아야한다 — 무게를 오름차순 정렬을 한다 만약 작은거 두개끼리 나가면 의미가 없고 너무 많은 많은 상황이 생긴다 큰것만 하나씩 나간다면 한 번에 나갈 수 있는 최적이 아니다 그렇기 때문에 가장 큰 것 + 가장 작은 것이 제한을 넘지 않아서 한 번에 나가는게 가장 최적이다 가장 작은 것과 가장 큰것을 더 했을때 제한이 넘으면 가장 큰것만 혼자 나간다 가장 작은 것과 그 다음 큰것을 더해서 제한과 비교한다 그후 제한 보다 작으면 두개를 같이 내보낸다 그리고 다음 작은것과 다음 큰것을 비교해서 반복한다 Arrays.sort(stuff); int min = 0; int max = stuf..
탐욕 알고리즘 (Greedy) 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황을 선택해서 답을 찾는것 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복 두 가지의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립해야한다 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/XPZ2m/btrIUll0T2m/i65UBZTzM48etpltB4wja0/img.png)
의사코드(pseudocode) 프로그래밍 언어를 작성하기 전에 우리가 쓰는 언어를 이용해서 작동하는 논리를 먼저 작성해 보는것 장점 시간 단축 문제가 복잡하거나 코드 양이 길어진다면 시간이 지나서 로직이 기억나지 않을 수 있다 그렇기 때문에 먼저 작성해둔 수도코드를 보면서 시간을 단축한다 디버깅 용이 오류가 났을때 개발 언어로만된 코드를 본다면 어디가 오류인지 알 수 없는 경우가 많다 소통 프로그래밍 언어에 익숙하지 않은 사람도 우리가 쓰는 언어로 작성된 수도코드를 보면 이해하기 쉽고 소통할 수 있다 구체적으로 써야하는 이유 컴퓨터는 우리가 쓰는 언어를 알지 못하고 0,1로만 이루어지기 때문에 자세하게 로직을 적어주지 않으면 컴퓨터에게 명령 할 수 없다 시간복잡도 입력값의 변화에 따라 연산을 실행할 때,..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bQCGPL/btrIMBxGJNr/mO4cezOKw9jYhYOP1EuDtK/img.png)
Tree & Graph & Binary Search Tree Tree 나무 뒤집어놓은 형태를 가지고 있는 자료구조 단방향 그래프 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조 루트(root) : 가장 위 꼭지점 간선(edge) : 노드간을 연결하는 선 노드(node) : 각 데이터 리프 노드(leaf node) : 자식이 없는 노드 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드 두개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진..
![](http://i1.daumcdn.net/thumb/C150x150/?fname=https://blog.kakaocdn.net/dn/bpuagI/btrINuLQHBa/QjkD7KpNBDHKSkD0qez4l0/img.jpg)
Stack & Queue 스택 -밑이 막힌 상자 -먼저 들어간게 맨 아래 깔리고 나중에 넣은게 위에 있다 -LIFO —> 나중에 들어간게 먼저 나온다 -Last in First out -들어갈때 push 나올때 pop -배열에 적합 push(): 스택에 데이터를 추가할 수 있어야 합니다. pop(): 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴해야 합니다. size(): 스택에 추가된 데이터의 크기를 리턴해야 합니다. peek(): 가장 나중에 추가된 데이터를 리턴해야 합니다. show(): 현재 스택에 포함되어 있는 모든 데이터를 String 타입으로 변환하여 리턴합니다. clear(): 현재 스택에 포함되어 있는 모든 데이터 삭제합니다. 큐 -양 끝이 뚫린 상자 -먼저 들어간게..