알고리즘 이론

문제를 해결하기 위해 정해진 일련의 절차

P NP문제에 대해 알아보자

빅오(O, big - O)란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법이다. 이 외에도 하한을 의미하는 빅오메가, 평균을 의미하는 빅세타가 있다. 학계와 달리 업계는 빅세타(평균) 빅오(상한)을 하나로 합쳐서 빅오로 단순화해 표현하는 경향이 있다

알고리즘에 따른 시간복잡도를 계산하다보면 시간제한을 보고 어느정도 요구 시간복잡도를 유추해낼 수 있다. 이를 활용해 시간 낭비를 줄일 수 있다.알고리즘 풀이 순서1\. 지문읽고 컴퓨터적 사고하기2\. 요구사항(복잡도) 분석3\. 문제 해결을 위한 아이디어 찾기4\. 소

가능한 모든 경우의 수를 탐색하며 조건에 충족하는 결과를 찾는 알고리즘

but. 알고리즘 대회에서의 구현유형은 풀이를 떠올리기는 쉽지만 소스코드로 옮기기 어려운 문제를 지칭알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제실수 연산을 다루고, 특정 소수점자리까지 출력해야 하는 문제문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제적절

분할 정복 알고리즘이란?

탐색: 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 대표적 예시 - DFS/BFS 코테에 자주 등장함. DFS BFS

가능한 한 모든 방법을 탐색하면서 해결책을 찾는데, 목표까지 가능성이 유망하지 않은 경로를 차단하고 가능성 있는 루트를 검색하는 방법이다.Promising: 트리 구조를 기반으로 DFS로 깊이 탐색을 진행하면서 각 루트에 대해 조건에 부합하는지 체크한다.Pruning:

다이나믹 프로그래밍(동적 계획법): 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장, 다시 계산 안하도록 함메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법DP의 구현은 일반적으로 두가지 방법으로 구성 탑다운(하양식)/보텀업(상향식)자료

최단경로 문제는 노드와 간선이 있을 때 말 그대로 특정 노드간 최단경로를 구하는 것을 의미한다. (다이나믹 프로그래밍으로 분류되기도 함)다익스트라가 제안한 알고리즘 중 하나로, 특정한 노드에서 출발해 다른 모든 노드로 가는 최단 경로 계산 (그리디 알고리즘으로 분류)조

런너는 연결리스트를 순회할 때 2개의 포인터를 동시에 사용하는 기법이다.빠른 런너, 느린 런너 두개의 포인트를 사용한다.병합지점이나 중간 위치 길이등을 판별할때 유용하게 사용할 수 있다. 주로 중간을 기준으로 값을 비교하거나 뒤집기를 시도하는 등 연결리스트 문제에서 자

In computer science, the Rabin–Karp algorithm or Karp–Rabin algorithm is a string-searching algorithm created by Richard M. Karp and Michael O. Rabin

Greedy Algorithm : 각 단계에서 최적이라고 생각하는 것을 선택해나가는 방식으로 전체의 최적해를 구하는 알고리즘탐욕 선택 속성(Greedy Choice Property)최적 부분 구조(Optimal Substructure)자세한 설명은 해당 포스팅 참고그리