반응형 알고리즘16 [알고리즘] DFS & BFS (1) * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 탐색 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적인 탐색 알고리즘 : DFS(깊이 우선 탐색), BFS(너비 우선 탐색) ■ DFS와 BFS를 하기 전에 알아야 할 자료구조 스택, 큐 ● 스택 자료구조 - 먼저 들어온 데이터가 나중에 나가는 선입후출의 자료구조 - 입구와 출구가 동일한 형태로 시각화할 수 있다. ■ 스택 구현 예제(Python) stack = [] # 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제() stack.append(5) stack.append(2) stack.append(3) stack.appen.. 2023. 2. 7. [알고리즘] 구현 * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 구현(Implementation) 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정 ■ 알고리즘 대회에서 구현 유형의 문제란? 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭 ● 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 ● 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 ● 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 ● 적잘한 라이브러리를 찾아서 사용해야 하는 문제 ■ 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용 ■ 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향벡터가 자주 활용 [문제] 상하.. 2023. 2. 3. [알고리즘] 그리디 * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 그리디 알고리즘(greedy algorithm) 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미 그리디 해법은 그 정당성 분석이 중요 ● 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토 [문제] 거스름 돈 카운터에서 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하라. (단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.) ■ 문제 해결 아이디어 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 거슬러 준다. ■.. 2023. 2. 2. [알고리즘] 알고리즘 성능 평가 * 본 포스팅은 나동빈 - 이코테 2021 강의 몰아보기 에서 학습한 내용을 포스팅합니다. 출처 동빈나 이코테 ■ 복잡도(Complexity) 복잡도는 알고리즘의 성능을 나타내는 척도 ● 시간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석 ● 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석 동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. ■ 빅오 표기법(Complexity) 가장 빠르게 증가하는 항만을 고려하는 표기법 ● 함수의 상한만을 나타내게 된다. 3N³ + 5N² + 1,000,000 ● 빅오 표기법에서는 차수가 가장 큰 항만 남기므로 O(N³)으로 표현 ■ 시간 복잡도 계산해 보기 ① N개의 데이터의 합을 .. 2023. 2. 2. 이전 1 2 3 다음 반응형
