본문 바로가기

Algorithm50

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. SW 문제 해결 능력 1) SW 문제 해결 역랑 - 제약 조건과 요구사항을 이해하고 최선의 방법을 찾아내는 능력 ※ 한 문제를 풀고 3명 이상의 풀이법을 보기 - 문제 해결 역량은 추상적인 기술이다. - 문제 해결 역량을 향상하기 위해서 훈련이 필요하다. 2) 문제 해결 과정 - 문제를 읽고 이해한다. (3회독) - 어떻게 해결할지 계획을 세운다. - 계획을 검증한다. (시간 복잡도, 공간 복잡도) - 프로그램으로 구현한다. - 어떻게 풀었는지 돌아보고, 개선한 방법이 있는지 찾아본다. - 1시간이 지나면 풀었든 못 풀었든 다른 사람들의 코드를 찾아본다. (3명 이상) 3) 알고리즘 - 어떠한 문제를 해결하기 위한 절차라고 볼 수 있다. 2. 알고리즘 성능 1) 시간 복잡도 - 최선의 경우 : 빅 .. 2024. 1. 29.

티스토리툴바