Algorithm/Study13 LinkedList 1. 리스트 1) 리스트란? - 순서를 가지는 데이터의 집합 - 값의 중복을 허용한다. - 순차 리스트와 연결 리스트로 나뉜다. 2) 순차 리스트 - 1차원 배열에 항목들을 순서대로 저장한다. - 데이터의 종류와 구조에 따라 구조화된 자료구조를 만들어 배열에 저장할 수도 있다. - 배열의 인덱스를 이용해 원하는 위치의 데이터에 접근할 수 있다. - 삽입 삭제 연산의 최악의 시간복잡도는 O(n) - 메모리 낭비, 새로운 배열 생성등의 문제가 있다. 3) 연결 리스트 - 개별적으로 위치하고 있는 각 원소를 연결하여 하느의 전체적인 자료구조를 이룬다. - 자료구조의 크기를 동적으로 조정 가능, 메모리의 효율적인 사용이 가능 - 삽입, 삭제 연산에 유리, 조회 연산은 불리 2. 연결 리스트 1) 기본 구조 - .. 2024. 2. 5. Stack, Queue 1. 스택 1) 스택이란? - 물건을 쌓아 올리듯 자료를 쌓아 올린 형태의 자료구조 - 선형구조이다. (자료 간의 관계가 1:1 관계를 갖는다.) - 후입선출구조 (LIFO) 2) 주요 메서드 Stack st = new Stack(); 메서드 설명 boolean empty() Stack이 비어있는지 확인 Object peek() Stack의 맨 위에 저장된 객체를 반환 pop()과 달리 Stack에서 객체를 꺼내지 않음 비었을 때는 EmptyStackException 반환 Object pop() Stack의 맨 위에 저장된 객체를 꺼냄 비었을 때는 EmptyStackException 반환 Object push(Object item) Stack에 객체(item)을 저장 int search(Object o).. 2024. 2. 4. 부분집합, 비트연산, 바이너리 카운팅 1. 부분집합 1) 부분집합이란? - 집합에 포함된 원소들을 선택하는 것. - 다수의 중요 알고리즘들이 원소들의 그룹에서 최적의 부분 집합을 찾는 것 - 집합의 원소가 n개일 때, 공집합을 포함한 부분집합의 수는 2^n개 이다. 2. 부분집합의 합 구하기(재귀) public static void generateSubSet(int cnt) { // 기저 조건 if (cnt == N) { for (int i = 0; i < N; i++) { System.out.print((isSelected[i] ? input[i] : "X") + "\t"); } System.out.println(); return; } // 유도 파트 isSelected[cnt] = true; // 부분집합에 포함 generateSubSe.. 2024. 2. 1. 완전 탐색 1. 완전 탐색 1) 완전 탐색이란? - 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법 - Bruete-force 기법이라고 불린다. - 상대적으로 빠른 시간에 문제 해결을 할 수 있다. - 일반적으로 경우의 수가 상대적으로 작을 때 유용하다. - 우선 완전 탐색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다. 2. 순열, 조합 1) 순열(P) - 순열이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 있음) - nPn은 n!이다. - 10!은 약 360만 (마지노선) 2) 조합(C) - 조합이란 서로 다른 n개중에 r개를 선택하는 경우의 수를 의미합니다. (순서 상관 없음) 3) 순열, .. 2024. 1. 30. 이전 1 2 3 4 다음
