본문 바로가기

분류 전체보기215

백준 9375: 패션왕 신해빈(java) 문제풀이 종류가 A인 의상이 p개, 종류가 B인 의상이 q개, 종류가 C인 의상이 r개 있을 때 가능한 조합은 ((p+1)*(q+1)*(r+1)-1)개이다. 의상이 x개 있을 때 의상을 고를 수 있는 가짓수는 아무 것도 선택하지 않는 경우를 포함하여 (x+1)가지이기 때문이다. 각 카테고리별로 가능한 가짓수를 곱하고, 모든 카테고리에서 의상을 선택하지 않아 옷을 입지 않게 되는 케이스 하나를 제외하면 전체 경우의 수를 구할 수 있다. 위 예제의 첫 번째 테스트 케이스의 경우 headgear에 hat과 turban의 2개, eyewear에 sunglasses의 1개가 있으므로 (2+1)*(1+1)-1=5개이다.  이를 바탕으로, 카테고리 별 의상의 개수를 입력받아 계산하면 끝나는 문제이다. 카테고리와 의상.. 2024. 7. 24.
이진 트리 이진 트리 정의공집합이거나루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합이진 트리의 서브 트리들은 모두 서브 트리- 모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree)라 함- 서브 트리는 공집합일 수 있음- 따라서 이진 트리의 노드에는 최대 2개까지의 자식 노드가 존재할 수 있고, 모든 노드의 차수가 2 이하- 서브 트리 간의 순서가 존재- 순환적으로 정의이진 트리의 성질 1. n개의 노드를 가진 이진 트리는 (n-1)개의 간선을 가짐- 이진 트리에서 루트를 제외한 모든 노드는 하나의 부모 노드를 가지고- 부모 노드와 자식 노드 간에 하나의 간선이 존재하므로 2. 높이가 h인 이진 트리는 최소 h개, 최대 (2ʰ-1)개의 노드를 가짐- 한 레벨에는.. 2024. 7. 23.
트리 개념 선형 자료 구조(linear data structure): 자료들이 선형으로 나열되어 있는 구조- 리스트, 스택, 큐 등- 자료가 계층적인 구조(hierarchical structure)를 가지고 있다면 선형 자료 구조로 표현 부적합- 트리: 계층적인 자료를 표현하는 데 적합한 자료구조트리 용어 트리는 노드와 간선으로 구성 - 노드(node): A~J와 같은 각 항목- 트리는 한 개 이상의 노드로 이루어진 유한 집합- 루트(root) 노드: 계층 구조에서 가장 높은 곳에 있는 노드- 서브 트리(subtree): 루트 노드에서 나누어지는 노드들({B, E, F, G}, {C, H}, {D, I, J})- 서브 트리에도 다시 루트와 서브 트리가 존재함(B - {E}, {F}, {G})- 간선(edge): 루.. 2024. 7. 23.
연결 리스트로 구현한 큐 연결된 큐- 연결 리스트를 이용하여 구현한 큐를 연결된 큐(linked queue)라 함- 배열로 구현한 큐와 달리 크기 제한 없음(pros)- 배열로 구현한 큐에 비해 코드가 복잡(cons)- 링크 필드가 추가되므로 메모리 공간 소모 多(cons) - 단순 연결 리스트에 2개의 포인터를 추가한 구조- front 포인터는 삭제, rear 포인터는 삽입과 관련- 큐가 공백 상태일 경우 front와 rear는 NULL- 큐의 요소들은 구조체로 정의되며 이 구조체는 데이터 필드와 링크 필드로 구성연결된 큐 정의typedef int element;typedef struct QueueNode { element data; struct QueueNode* link;} QueueNode;typedef struct { .. 2024. 7. 22.
연결 리스트로 구현한 스택 연결된 스택- 연결 리스트를 이용하여 구현한 스택을 연결된 스택(linked stack)이라 함- 제공되는 외부 인터페이스는 배열 스택과 연결된 스택이 동일- 스택의 내부 구현이 다름- 연결 리스트를 이용하여 스택을 구현하면 스택에 새로운 요소가 삽입될 때마다 동적 할당으로 메모리를 할당하므로 스택 크기가 제한되지 않음(pros)- 동적 메모리 할당이나 해제가 필요하므로 삽입이나 삭제 시간이 더 소요(cons)typedef int element;typedef struct StackNode { element data; struct StackNode* link;}StackNode;typedef struct { StackNode* top;}LinkedStackType;- 데이터를 저장하는 데이터 필드와 다음 .. 2024. 7. 22.
이중 연결 리스트 이중 연결 리스트: 하나의 노드가 선행 노드와 후속 노드에 대한 두 개의 링크를 가지는 리스트- 단순 연결 리스트에서는 선행 노드를 찾기 매우 어려움- 원형 연결 리스트에서도 선행 노드를 찾으려면 거의 전체 노드를 거쳐야 함 → 특정 노드에서 양방향으로 움직여야 한다면 단순 연결 리스트 구조는 부적합- 실제 응용에서는 이중 연결 리스트와 원형 연결 리스트를 혼합- 헤드 노드(head node)를 추가하는 경우 多- 헤드 노드는 데이터를 가지고 있지 않고 삽입과 삭제 알고리즘을 간편하게 하기 위해 존재하는 특별한 노드노드 구조 정의- 이중 연결 리스트에서 노드는 3개의 필드로 이루어짐- 왼쪽 링크 필드(llink), 데이터 필드, 오른쪽 링크 필드(rlink)- 링크 필드는 포인터로 이루어짐p=p->lli.. 2024. 7. 22.

티스토리툴바