알고리즘에 대해서 공부한 내용을 정리한 블로그 입니다.
이번에는 이전에 multiplex PCR의 primer 디자인을 하던 중 공부했던 휴리스틱 접근법에 대해 정리해보겠습니다. 우리는 문제를 해결할 때 종종 동적 계획법(DP)이나 분할 정복과 같은 완전 탐색 기반의 알고리즘을 사용합니다. 하지만 이러한 방법들은 실생활에서 적용하기엔 한계가 있습니다. 특히, 입력 크기가 크거나 최적의 분할 전략을 찾기 어려운 경우, 기존의 완전 탐색 방법은 비효율적일 수밖에 없습니다. 이럴 때 접근할 … Read more
여러 알고리즘을 공부하게 되면서 “재귀 함수”가 프로그래밍의 기초 개념을 위해 초반에만 살짝 지나가는 개념이 아니라는 것을 깨닫게 되었습니다. “재귀 함수”는 문제를 해결하기 위해 문제를 더 작은 형태로 나누어 직접 또는 간접적으로 정의 내에서 자신을 호출하는 함수입니다.
브루트 포스의 단점이 방대한 input에서는 성능이 떨어진다는 점이였습니다. 이를 해결할 수 있는 게 “이분 탐색” 입니다. 말 그대로 반으로 나누어 탐색하는 거죠. 어떻게 반으로 나누어서 탐색하는 데 답을 찾을 수 있을까요?
BFS 란? BFS(Breadth First Search)는 그래프에서 발생하는 사건들을 검사 혹은 처리하기 위해 탐색하는 방법 중 하나 입니다. BFS는 그래프를 수준별로 탐색하여 다음 수준으로 이동하기 전에 주어진 노드의 모든 인접 노드를 방문하는 그래프 순회 알고리즘입니다. BFS vs DFS BFS와 같은 탐색 알고리즘에서 가장 먼저 비교되는 게 DFS인데요 BFS는 레벨별로 그래프를 탐색하여 다음 레벨로 이동하기 전에 주어진 … Read more
“브루트 포스” 알고리즘 이름을 처음 들었을 때는 이름부터 포스가 느껴졌습니다… ㅎ 하지만 한글로는 “완전 탐색” 말 그대로 for 문으로 순회하면서 확인, 연산하는 프로세스를 의미합니다. “브루트 포스 알고리즘”이라는 개념을 몰라도 코딩 기초 과정에서 자연스레 사용했던 알고리즘이였던 것….! 그럼 이런 간단한 알고리즘은 사용하면 안되는 알고리즘일까요? 그리고 그리디 알고리즘은 무엇일까요? 브루트 포스랑 비슷한 알고리즘 일까요? 브루트 포스 (완전 … Read more
시간 복잡도와 공간 복잡도에 대한 공부한 내용을 정리해 보았습니다. 시간 복잡도 시간 복잡도는 입력 크기가 증가함에 따라 알고리즘의 실행 시간이 어떻게 증가하는지를 측정한 것입니다. Big-O 표기법은 최악의 시나리오에서 알고리즘의 시간 복잡도의 상한을 표현하는 방법입니다. 이는 특정 하드웨어, 상수 요소 또는 하위 항의 세부 사항에 얽매이지 않고 알고리즘의 효율성을 분석하는 데 도움이 됩니다. Big-O는 다음과 같이 … Read more
이번 포스트에서는 “스택 자료구조”를 정리했습니다. 자료구조란 “구조+연산” 이기 때문에 이러한 특징을 살펴보고, 이를 이용한 알고리즘 문제를 풀어보았습니다. 스택 구조 스택은 데이터를 한쪽으로만 넣을 수 있으며, 중간에 있는 데이터를 삭제할 수 없습니다. 가장 큰 특징은 후입선출 (LIFO: Last-In-First-Out) 형식의 선형 자료구조입니다. 후입선출 (LIFO): 스택 vs. 큐 vs. 리스트: 스택 자료구조 연산 스택(stack) 데이터 구조에 필요한 기본 연산들 스택 … Read more
프로그래머스 문제를 풀다가 백준 문제를 보게되면 “???? 뭐지? 반환 값으로 값 받는건가?”, “input은 인자로 받는 건가?” 헷갈립니다. “백준에서 요구하는 input” 을 한 번 검색하고 나서야 어느 정도 힌트를 얻을 수 있었습니다. 이번 포스트에서는 백준에서 요구하는 input을 어떻게 코드로 작성하는지 정리해보았습니다. 백준에서 요구하는 input을 작성하기 위한 기본 개념 map 함수 map 함수는 주어진 함수를 iterable의 각 … Read more
“알고리즘”을 딱히 공부한 적이 없어서 알고리즘 공부를 시작하면서 글을 정리해보았습니다. 알고리즘을 따로 공부하지 않았지만 백준이나 프로그래머스 문제가 낮은 난이도의 문제지만 풀리는 걸 보면서 새삼 신기하기도 했습니다. Bioinformatics로 일하면서 문제를 해결했던 게 곧 “브루트 포스” 였고 “그리디 알고리즘” 이였다는 걸 이제 와서 깨달은 거였죠…ㅎㅎ 여러 알고리즘 기법들이 있기에 이에 대해서 앞으로 공부하면서 정리할 예정입니다. 오늘은 알고리즘이란 … Read more