티스토리

programming record

검색하기

블로그 홈

programming record

sungkshon.tistory.com/m

sungkshon 님의 블로그입니다.

구독자: 0

방명록 방문하기

반응형

주요 글 목록

정렬 알고리즘(Sorting Algorithms) |Brute Force | 브루트 포스 알고리즘 | 완전탐색 알고리즘 Sorting 이란 뭔가를 정리하는 것이다 A부터 Z까지 정렬하든가, 큰 수에서 작은 수 기준으로 정렬할 수 도 있다. 일단 먼저 배열을 정리해야 한다. Bubble Sort(버블 정렬), Selection Sort(선택 정렬), Insertion Sort(삽입 정렬)이 있다. 👉 Brute Force | 브루트 포스 알고리즘 | 완전탐색 알고리즘 : 모든것을 다 해보겠다는 의미이다. 주로 비밀번호를 해킹할 때 사용되는 용어인데, 비밀번호가 될 수 있는 모든 조합을 다 시도해보는 기법을 프루트 포스 어택이라고 한다. 구현 방법1. for / while loop 사용금고를 열기 위해 0000부터 9999까지 모든 숫자를 대입해보려면 for( int i = 0; i try(i);2.. 공감수 0 댓글수 0 2024. 8. 5.
DP(Dynamic Programming) 동적 계획법 | 파이썬 1. DPDP는 완전탐색, DFS, BFS와 같이 수많은 경우의 수를 전부 따져봐야 하는데 그 경우의 수가 너무 많아서 속도가 느려지는 문제를 개선하고자 그래서 수행 시간을 단축하고자 만들어진 알고리즘이다.복잡한 문제를 여러 개의 문제로 나누어 푸는 방법이다. DP의 목적: 메모리를 사용해서 중복 연산을 줄이고 중복 연산을 줄여서 수행 속도를 개선한다.메모리를 사용한다 → 배열 혹은 자료구조를 만든다.중복 연산을 줄인다 → 연산한 결과를 배열에 담는다. 2. DP 문제를 알아보고 구분하는 방법DP는 특정 유형에만 국한되지 않고 다양한 유형의 문제를 최적화 할 때 고려될 수 있는 알고리즘이다.DFS / BFS 로 풀 수는 있지만 경우의 수가 너무 많은 문제경우의 수들에 중복적인 연산이 많은 경우문제 .. 공감수 0 댓글수 0 2024. 5. 27.
그리디(Greedy) / 탐욕 알고리즘 1. 그리디 알고리즘의 정의그리디란 말 그대로 탐욕이라는 뜻이다.그리디는 미래를 고려하지 않고 오직 현재 시점에 가장 좋은 선택을 하는 알고리즘이다.2. 그리디 알고리즘의 특징이 방식은 최적의 해를 항상 보상하진 않는다. (그럴 때는 다이나믹 프로그래밍(Dynamic Programming)등의 기타 알고리즘 기법을 적용해야 하기도 한다.)그래서 근사 알고리즘이라고도 한다. DP보다 빠르다.3. 그리디 알고리즘 대표적 예제1260원을 거슬러 주어야 할 때 가장 적은 숫자의 화페를 이용해 거슬러 주는 경우는?500원, 100원, 50원, 10원 짜리가 있다.1. 500원 짜리 총 2개를 거슬러 줄 수 있다. (260원 남음)2. 100원 짜리 총 2개를 거슬러 줄 수 있다. (60원 남음)3. 50원 짜리.. 공감수 0 댓글수 0 2024. 5. 20.
시간복잡도(time complexity) | Big O표기법 빠른 알고리즘은 느린 알고리즘보다 우수하다는것은 당연한 사실이다.알고리즘 스피드는 완료까지 걸리는 절차의 수로 결정된다. Big O 표기법 특징상수항 무시 O(N+3) → O(N) 계수 무시 O(3N) → O(N)최고차항만 표기 O(3N^3 +2N^2 +N +6) → O(N^3)실행 시간(running time): 함수/알고리즘 수행에 필요한 스텝 수점근적 분석(Asymptotic analysis): 임의의 함수가 N → ∞ 일때 어떤 함수 형태에 근접해지는 분석 시간복잡도(time complexity): 함수의 실행 시간을 표현하는 것, 주로 점근적 분석을 통해 실행시간을 단순하게 표현하며 이 때 점근적 표기법으로 표현함 시간복잡도 빠른 순서1. O(1) (constant tim.. 공감수 0 댓글수 0 2024. 5. 20.
BFS (Breadth First Search, 너비 우선 탐색) | 파이썬 드라마에 먼저 비유하자면, 드라마가 끝나길 기다리고 몰아보는 유형과 그때 그때 본방을 사수하며 드라마 여러 개를 다 챙겨보는 유형이 있다.끝나길 기다리고 몰아본다. 👉 DFS (Depth First Search)드라마 여러 개를 다 챙겨본다. 👉 BFS (Breadth First Search)DFS와 BFS를 그래프 탐색 알고리즘이라고 한다.그래프: 여러 개체들이 연결되어 있는 자료구조탐색: 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 대표 문제 유형경로탐색 유형(최단거리, 시간)네트워크 유형(연결)조합 만들기BFS시작점에서 가까운 정점부터 순서대로 방문하는 탐색 알고리즘큐를 이용하여 구현한다.출발점을 먼저 큐에 넣고, 다음 로직을 반복한다.큐에 저장된 정점을 하나 Dequeue한다... 공감수 0 댓글수 0 2024. 5. 11.
DFS( Depth Fisrt Search, 깊이 우선 탐색) | 파이썬 드라마에 먼저 비유하자면, 드라마가 끝나길 기다리고 몰아보는 유형과 그때 그때 본방을 사수하며 드라마 여러 개를 다 챙겨보는 유형이 있다.끝나길 기다리고 몰아본다. 👉 DFS (Depth First Search)드라마 여러 개를 다 챙겨본다. 👉 BFS (Breadth First Search)DFS와 BFS를 그래프 탐색 알고리즘이라고 한다.그래프: 여러 개체들이 연결되어 있는 자료구조탐색: 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 대표 문제 유형경로탐색 유형(최단거리, 시간)네트워크 유형(연결)조합 만들기DFS가장 직관적이고 구현하기 쉬운 탐색 방법현재 정점과 연결된 정점들을 하나씩 갈 수 있는지 검사하고, 특정 정점으로 갈 수 있다면 그 정점에 가서 같은 행위를 반복한다.같은 .. 공감수 0 댓글수 0 2024. 5. 11.
Binary Search (이진 탐색) 이진탐색은 1차원 리스트에 데이터가 정렬되어 있을 때 주어진 데이터를 효율적으로 찾는 알고리즘이다.만약에 데이터가 정렬되어 있지 않다면, 주어진 데이터를 찾기 위해 리스트의 모든 원소들을 차례로 검색하는 순차 탐색 (Sequential Search)를 수행해야 한다. 탐색 연산은 최악의 경우 O(N) 시간이 소요된다. 이진탐색은 데이터를 미리 정렬하여 최악의 경우에도 logN번의 항목 비교만 하는 매우 효율적인 탐색 방법이다.여기서 N은 리스트에 저장된 항목의 수다.binary_search(left, right, t):if left > right: return None # 탐색 실패mid = (left + right) // 2 # 리스트에서 탐색할 부분의 중간 항목의 인덱스 계산if a[mi.. 공감수 0 댓글수 0 2024. 5. 6.
Stack (스택) / Queue (큐) 스택과 큐는 '추상적 자료구조(Abstract Data Type)'라고 불린다.추상적 자료구조란 자료구조의 방법이 코드로 정의된 것이 아니라, 그 구조의 행동 양식만 정의 된것을 뜻한다. 스택(Stack)요소를 추가하거나 삭제할 때, 맨 위에 부터 차례대로 할 수 있다. Last In First Out(LIFO) (가장 마지막에 들어온 데이터가 가장 먼저 삭제된다) 자료구조 이다. 웹 브라우저에서 '뒤로가기'를 누르면 스택 자료구조를 사용하게 되는 것이다. 왜냐하면 뒤로가기를 누르게 되면 웹페이지 히스토리 스택의 맨 위에서 한 페이지를 가져가는 것과 같기 때문이다.데.. 공감수 1 댓글수 1 2024. 5. 6.

반응형

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.