개발새발

최적의 상황을 찾는것 자체가 정렬을 한 후 인덱스 번호끼리 비교하는 것이라고 생각 짐나르기 1. 항상 나갈 수 있는 최적을 찾아야한다 — 무게를 오름차순 정렬을 한다 만약 작은거 두개끼리 나가면 의미가 없고 너무 많은 많은 상황이 생긴다 큰것만 하나씩 나간다면 한 번에 나갈 수 있는 최적이 아니다 그렇기 때문에 가장 큰 것 + 가장 작은 것이 제한을 넘지 않아서 한 번에 나가는게 가장 최적이다 가장 작은 것과 가장 큰것을 더 했을때 제한이 넘으면 가장 큰것만 혼자 나간다 가장 작은 것과 그 다음 큰것을 더해서 제한과 비교한다 그후 제한 보다 작으면 두개를 같이 내보낸다 그리고 다음 작은것과 다음 큰것을 비교해서 반복한다 Arrays.sort(stuff); int min = 0; int max = stuf..

탐욕 알고리즘 (Greedy) 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황을 선택해서 답을 찾는것 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택합 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복 두 가지의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립해야한다 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영..

의사코드(pseudocode) 프로그래밍 언어를 작성하기 전에 우리가 쓰는 언어를 이용해서 작동하는 논리를 먼저 작성해 보는것 장점 시간 단축 문제가 복잡하거나 코드 양이 길어진다면 시간이 지나서 로직이 기억나지 않을 수 있다 그렇기 때문에 먼저 작성해둔 수도코드를 보면서 시간을 단축한다 디버깅 용이 오류가 났을때 개발 언어로만된 코드를 본다면 어디가 오류인지 알 수 없는 경우가 많다 소통 프로그래밍 언어에 익숙하지 않은 사람도 우리가 쓰는 언어로 작성된 수도코드를 보면 이해하기 쉽고 소통할 수 있다 구체적으로 써야하는 이유 컴퓨터는 우리가 쓰는 언어를 알지 못하고 0,1로만 이루어지기 때문에 자세하게 로직을 적어주지 않으면 컴퓨터에게 명령 할 수 없다 시간복잡도 입력값의 변화에 따라 연산을 실행할 때,..

Tree & Graph & Binary Search Tree Tree 나무 뒤집어놓은 형태를 가지고 있는 자료구조 단방향 그래프 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조 루트(root) : 가장 위 꼭지점 간선(edge) : 노드간을 연결하는 선 노드(node) : 각 데이터 리프 노드(leaf node) : 자식이 없는 노드 부모 노드(Parent node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드 자식 노드(Child node) : 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드 두개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진..

Stack & Queue 스택 -밑이 막힌 상자 -먼저 들어간게 맨 아래 깔리고 나중에 넣은게 위에 있다 -LIFO —> 나중에 들어간게 먼저 나온다 -Last in First out -들어갈때 push 나올때 pop -배열에 적합 push(): 스택에 데이터를 추가할 수 있어야 합니다. pop(): 가장 나중에 추가된 데이터를 스택에서 삭제하고 삭제한 데이터를 리턴해야 합니다. size(): 스택에 추가된 데이터의 크기를 리턴해야 합니다. peek(): 가장 나중에 추가된 데이터를 리턴해야 합니다. show(): 현재 스택에 포함되어 있는 모든 데이터를 String 타입으로 변환하여 리턴합니다. clear(): 현재 스택에 포함되어 있는 모든 데이터 삭제합니다. 큐 -양 끝이 뚫린 상자 -먼저 들어간게..