Algorithm/개념
[알고리즘] 그리디(Greedy) 알고리즘
그리디(Greedy) 그리디 알고리즘은 한마디로 "현재 상황에서 지금 당장 좋은 것만 고르는 방법"이라고 표현할 수 있다. 미래는 생각하지 않는 것이다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이기 때문에 문제에서 "가장 큰 순서대로", "가장 작은 순서대로"와 같은 기준을 제시하기도 한다. 이에서 볼 수 있듯이 주로 정렬 알고리즘과 함께 출제되기도 한다. 그리디 알고리즘을 풀 때에는 결정한 문제 풀이 방법이 그때 당시의 최선의 선택이 전체에 걸쳐서도 최선인지를 확인하여야 한다. 그리디 알고리즘은 이런 특성 때문에 항상 최적의 값을 보장하지는 않는다. 따라서 최적의 값에 근사한 값을 목표로 하는 근사적인 방법이다. 그리디 알고리즘의 조건 1. 탐욕스런 선택 조건 (Greedy Choic..
[알고리즘] 투 포인터(Two Pointers)
투 포인터 (Two Pointers) 리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하며 나아가는 알고리즘이다 시작점과 끝점을 그 두개의 점으로 지정한다 특정한 합을 가지는 부분 연속 수열 문제에 적용 가능하다 두 개의 점이므로 투 포인터라 한다 반복문만 사용하는 것보다 메모리와 시간 효율성을 높일 수 있다 시간 복잡도는 O(N) 이다 (반복문 사용시 O(N^2)) 앞에서 시작하는 포인터 & 끝에서 시작하는 포인터 두 포인터 중 start 포인터를 가장 앞 인덱스 0으로 설정하고, 나머지 end 포인터를 가장 마지막 인덱스 n으로 설정한다. 찾아야 하는 값 두 점의 합 → start 포인터를 인덱스 하나 늘려 ..
[알고리즘] 이진 탐색(Binary Search) + 매개변수 탐색(Parametric Search)
이진 탐색 반으로 쪼개면서 탐색하는 방법으로, 데이터가 정렬되어 있는 배열에서 사용할 수 있는 알고리즘이다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징을 가지고 있다. 따라서 위치를 나타내는 변수 3개를 사용하는데 탐색하고자 하는 범위의 시작점, 끝점, 중간점을 변수로 가진다. 이진 탐색은 찾으려는 데이터와 중간점에 있는 데이터를 반복적으로 비교하며 탐색해 나간다. 시간 복잡도는 한 단계 거칠 때마다 확인하는 원소가 평균적으로 절반씩 줄어드므로 빅오 표기법에 의해 O(logN)이다. 코딩 테스트에서 단골로 나오는 문제이므로 외우는 것을 추천하며 보통 탐색 범위가 큰 상황에서 사용된다. 탐색 범위가 2000만을 넘어가면 이진 탐색 접근을 권한다고 한다. 구현 방법 1 : 재귀 함수 def bina..
[알고리즘][파이썬] Exhaustive Search / 완전 탐색
2023.07.07... 5학기 여름방학에 다시 시작하는 혼자 하는 알고리즘 레쮸고 !!!!!!!!! 완전 탐색이란 모든 경우의 수를 다 세는 방법 Brute force 직관적이어서 이해하기 쉬운 방법 상대적으로 구현이 간단한 방법 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법 시간 복잡도가 O(N^2)인 방법 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용 완전 탐색 알고리즘 종류 Brute Force Bitmask (비트마스크) Recursive (재귀) Permutation (순열) BFS (너비우선탐색) & DFS (깊이우선탐색) Brute Force 반복문 or 조건문으로 모든 경우를 체크하여 정답 구하기 (ex) 000~999 사이의 자물쇠..
[알고리즘] 알고리즘 스터디 계획 / Algorithm Study Plan
다시 올리는 알고리즘 스터디 계획 ㅋㅋㅋㅋㅋ 5학기를 마친 여름방학에 ... 저번 겨울방학에 제대로 못한 부분을 채우려 한다 이번에는 나 혼자 !!! 진행할 것이다 목표 : 백준 Gold 달기 사용 언어 : 파이썬(Python) 커리큘럼 : 스택/큐 > 완전탐색 > .. (추후 추가) 일정 : 2023.07 ~ 2023.08 깃헙 레포지토리 : dudrhy12/Baekjoon (github.com) GitHub - dudrhy12/Baekjoon Contribute to dudrhy12/Baekjoon development by creating an account on GitHub. github.com
[알고리즘][파이썬] 그래프 / graph
그래프 (graph) 원소 간의 관계를 표현한 자료구조 그래프의 기본 구조 노드(node)=정점(vertex)와 간선(edge)으로 표현 두 노드가 인접하다 : 두 노드가 간선으로 연결되어 있다 노드1과 노드3은 인접하다 그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것 그래프의 표현 1. 인접 행렬 (Adjacency Matrix) 2차원 배열로 그래프의 연결관계를 표현하는 방식 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식 연결되어 있지 않은 노드끼리는 무한의 비용으로 작성 (999999999,987654321) 자기자신은 비용이 0 0 1 2 0 0 무한 5 1 무한 0 3 2 5 3 0 INF = 999999999 #무한 graph = [ [0, INF, 5] [INF, 0..
[알고리즘][파이썬] 재귀함수 / Recursive Function
알고리즘 공부하다가.. 한 번 정리해둬야겠다 싶은 재귀함수 레쮸고 재귀함수 (Recursive Function) 자기 자신을 호출하는 함수 프랙털(Fractal) 구조와 흡사 기본 예제 def recursive(): print("재귀 함수 호출") recursive() recursive() 위와 같이 코드 실행 시 "재귀 함수 호출" 문자열이 계속 출력되다가 오류 메세지가 출력된다. "RecursionError: maximum recursion depth exceeded while pickling an object" 재귀의 최대 깊이를 초과했다는 내용으로 파이썬 인터프리터는 호출 횟수 제한이 있기 때문에 생기는 오류이다. (프로그래밍 대회에서는 파이썬의 재귀 호출 제한을 처리하기 위해 라이브러리를 사용하..
[알고리즘][파이썬] 큐, 스택 / queue, stack
CS 자료구조 중 가장가장 기본적이고 가장가장 쉬운 것.. 고마워 올해 1학기에 자료구조 수업을 들었는데.. 내가 알던 CS 세계는 작고도 작았구나를 깨우쳐 준 과목이었다.. 아무튼 레쮸고 큐와 스택 (queue&stack) 자료구조의 한 종류 ( 자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조 ) 자료를 일렬로 보관 자료를 넣는 동작 & 자료를 빼는 동작 가능 삽입(push), 삭제(pop) 함수로 구성 오버플로와 언더플로도 같이 고민 필요 오버플로 : 특정 자료구조가 수용할 수 있는 데이터의 크기가 이미 가득 찬 상태에서 삽입 연산 수행 시 발생 언더플로 : 자료구조에 데이터가 없는 상태에서 삭제 연산 수행 시 발생 큐 (queue) 작업들이 처리되기 전에 대기 중인 선형 리스트 자료 구조..
[알고리즘] 알고리즘 스터디 계획 / Algorithm Study Plan
대망의첫 자율 스터디.. (학교 수업,동아리 이외) 대망의 첫 티스토리 글.. 진행 방법 목표 : 이것이 취업을 위한 코딩테스트다 with 파이썬 교재 완료 사용 언어 : 파이썬(Python) 커리큘럼 : 스택/큐 > 그리디 > 구현 > DFS/BFS > 정렬 > 이진탐색 > 다이나믹 > 최단경로 > 그래프 일정 : 2023.1 ~ 2023.2 깃헙 레포지토리 : https://github.com/dudrhy12/Algorithm-Study.git GitHub - dudrhy12/Algorithm-Study: [2023 Winter ~ ] Algorithm Study ✏️ [2023 Winter ~ ] Algorithm Study ✏️. Contribute to dudrhy12/Algorithm-Stud..