티스토리

홍'story

검색하기

블로그 홈

홍'story

2t-hong.tistory.com/m

공부하자 태홍아

구독자: 10

방명록 방문하기

주요 글 목록

[Algorithm] Sort(Selection, Insertion, Bubble) 🚗 Selection Sort 선택 정렬을 데이터 중 가장 작은 값의 데이터를 선택하여 앞으로 보내는 정렬이다. Selection Sort is a sort that selects the data with the smallest value and sends it forward. Time complexity $ = N + (N-1) + (n-2) + ... + 2 + 1 $ $ = \frac{N(N+1)}{2}\ $ $ = N * N $ $ = O(N^2) $ Best : $N(O^2)$ Average : $N(O^2)$ Worst : $N(O^2)$ #include using namespace std; void selectionSort(int arr[], int n) { for (int i = 0; i .. 공감수 0 댓글수 0 2024. 3. 8.
[Algorithm] Dynamic Programming(5) - 플로이드 와샬 (Floyd-Warshall) 🤔Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 포스팅에서는 All-pairs shortest Paths에 대해 알아보도록 하겠습니다. 가장 대표적인 알고리즘인 플로이드 와샬 알고리즘을 통해 해당 알고리즘을 해결하겠습니다. 🔎 All-pairs Shortest Path 이전의 다익스트라 알고리즘 또는 벨만포드 알고리즘의 경우에는 하나의 시작 정점 source에서 다른 모든 정점 들 간에 최소 경로를 구하는 알고리즘입니다. 이와 같은 문제를 single-source 최단 경로 문제라고 합니다. 그에 반해 단일 source가 아닌 임의의 모든 두 정점 .. 공감수 0 댓글수 0 2022. 11. 20.
[Algorithm] Dynamic Programming(4) - 벨만포드(Bellman-Ford) 🤔Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 포스팅에서는 최단 경로 문제중 하나인 벨만포드 알고리즘에 대해 알아보도록 하겠습니다. 🔎 최단 경로 문제(Shortest Path Problem) ✍️ 최단 경로 문제란? 그래프 G = (V, E)의 상에서 정점 u에서 v로의 가장 짧은 경로의 길이를 구하는 문제를 최단 경로 문제라고 합니다. 우리는 edge-weighted graph의 경우만을 생각하도록 하겠습니다. ( 이때 |V| = n, |E| = m ) ✍️ Edge-weighted graph 그래프 G의 edge(a, b)에 가중치 w(a, .. 공감수 0 댓글수 0 2022. 11. 19.
[Algorithm] Dynamic Programming(3) - Edit Distance(편집거리) 🤔 Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 포스팅에서는 Edit Distance 문제를 해결하기 위해 Dynamic Programming을 사용하여 해결하는 과정을 정리했습니다. Edit Distance 문제는 어떤 단어와 비슷한 단어는 어떤 방식으로 정의할 수 있을까? 라는 의구심에서 시작되었습니다. 아래의 그림과 같이 Microsoft Word spell check 기능을 사용하면 비슷한 단어를 자동으로 추천해줍니다. 우리도 이를 Edit Distance를 통해 해결해보겠습니다. 🔎 Edit Distance 위에서 어떤 단어와 비슷한 단어.. 공감수 0 댓글수 0 2022. 11. 19.
[Algorithm] Dynamic Programming(2) - LIS(Longest Increasing Subsequence) 🤔 Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 포스팅에서는 LIS문제를 해결하기 위해 Dynamic Programming을 사용하여 해결하는 과정을 정리했습니다. 🔎 LIS(Longest Increasing Subsequence) ✍️Subsequence 길이 n 인 sequence (ordered list) $S = a_1, a_2, …, a_n$ 이 주어졌을 때, sequence $S’ = a_{i1}, a_{i2}, .., a_{ik} 가 1≤ i1 < i2 < … < ik ≤n$ 를 만족할 경우 $S’$ 을 $S$의 subsequence .. 공감수 0 댓글수 0 2022. 11. 17.
[Algorithm] Dynamic Programming(1) - Warm Up 🤔Dynamic Programming 다이나믹 프로그래밍이란 큰 문제를 작은문제로 나누어 문제를 해결하는 것을 말합니다. 다이나믹 프로그래밍 알고리즘을 이용하는 다양한 알고리즘에 대해 알아보겠습니다. 이번 시간에는 다이나믹 프로그래밍이 어떤 것인가에 대해서 알아보도록 하겠습니다. 🔎 피보나치 수열 컴퓨터를 배운 사람이라면 한 번쯤 풀어봤을 피보나치 수열 문제입니다. (피보나치 수열을 잘 모르시는 분은 해당 링크를 참고하시길 바랍니다.) 피보나치 수열은 Recursion을 이용하여 해결할 수 있습니다. 👉 피보나치 수열 수도코드 더보기 fib(n): if(n == 0) return 0 if(n == 1) return 1 return fib(n-1) + fib(n-2) 해당 알고리즘의 시간 복잡도는 subp.. 공감수 0 댓글수 0 2022. 11. 15.
[Algorithm] 분할정복(4) - Selection 🤔분할정복 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다. 이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다. 이번 시간에는 Good Pivot을 찾기 위한 Selection 알고리즘에 대해 배워보도록 하겠습니다. Good Pivot을 찾는 것은 MOM(Median Of Medians)를 찾는 것에 필수적인 정보이기 때문에 꼭 제대로 숙지해야합니다. 🔎 Selection - Quick Select 🤔 Problem 크기가 $n$인 배열 A가 주어졌을 때, A에서 $k$번째로 작은 원소를 찾아야 합니다. 특별히 $k$가 $n/2$ ($n$이 even 인.. 공감수 0 댓글수 0 2022. 10. 20.
[Algorithm] 분할정복(3) - Matrix Multiplication 🤔 분할정복 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다. 이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다. 알고리즘의 Basic Arithmetic의 연장선인 행렬곱을 알고리즘의 관점에서 알아보겠습니다. 행렬에 대한 알고리즘 공부가 하기 싫어서 미루고 있다 이제야 포스팅 하게 되었습니다. 행렬 중에서도 두 $n\times{n}$ Matrix의 경우만 알아보도록 하겠습니다. 🔎 두 $n \times n$ Matrix 곱하기 연산 먼저 행렬의 각 entry들 간의 사칙연산은 모두 $O(1)$시간이 걸린다고 하겠습니다. 예시로 아래의 행렬을 통해 두 .. 공감수 0 댓글수 0 2022. 10. 20.
[Algorithm] 그래프 알고리즘(3) - DFS(2), Biconnected Graph 🤔 그래프 알고리즘 그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다. 그래프는 정점과 간선으로 구성된 자료구조를 뜻합니다. 이번 시간은 저번 포스팅에 이어 DFS에 대해 조금 더 알아보고 Biconnected Graph에서 Articulation Point를 찾는 방법에 대해 집중적으로 알아보도록 하겠습니다. 👉 이전 포스팅 더보기 2022.10.04 - [Computer Science/Algorithm] - [Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어 [Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어 🤔 그래프 알고리즘 그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다. 그래프는.. 공감수 1 댓글수 0 2022. 10. 13.
[Algorithm] 그래프 알고리즘(2) - DFS(깊이우선탐색)(1) 🤔그래프 알고리즘 그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다. 그래프는 정점과 간선으로 구성된 자료구조를 뜻합니다. 이번 포스팅에서는 DFS에 대해 알아보도록 하겠습니다. 👉이전 포스팅 더보기 2022.10.04 - [Computer Science/Algorithm] - [Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어 [Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어 🤔 그래프 알고리즘 그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다. 그래프는 정점과 간선으로 구성된 자료구조를 뜻합니다. 이번 포스 2t-hong.tistory.com 🔎 Reachability Reachabil.. 공감수 0 댓글수 0 2022. 10. 8.
[Algorithm] 그래프 알고리즘(1) - 그래프의 기본 용어 🤔 그래프 알고리즘 그래프는 알고리즘 기법이라기 보다는 여러가지 효율적인 알고리즘을 적용하기 위한 자료구조입니다. 그래프는 정점과 간선으로 구성된 자료구조를 뜻합니다. 이번 포스팅에서는 그래프를 구성하는 단어들에 대한 기본용어를 알아보겠습니다. 🔎 그래프의 기본 용어 제가 가장 질투하면서 존경하는 친구의 블로그에 너무 잘 정리되어 있어서 해당 블로그를 살펴보는 것이 도움이 될 것입니다. 그래프의 기본 용어는 이해보다 암기가 필요한 부분이기때문에 포스팅으로 넘어가도록 하겠습니다. 🔎 참조 https://ttl-blog.tistory.com/954?category=964962 [알고리즘] 그래프 (1) - 그래프의 기본 용어 🧐 그래프 (Graph) 그래프는 정점(vertex)들과 간선(edge)들로 이루어.. 공감수 0 댓글수 0 2022. 10. 4.
[Algorithm] 분할정복(5) - Median of Medians 🤔분할정복 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다. 이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다. 이번 포스팅에서는 Median of Medians 에 대해 알아보겠습니다. 🔎 Median Of Medians 크기가 $n$인 배열 A가 주어졌을 때 A에서 k번째 작은 원소를 찾는 알고리즘을 찾아보겠습니다. 앞선 Quicksellect의 시간복잡도 분석에서 결국 Quickselect의 성능은 '좋은 pivot을 얼마나 빠르게 찾아내는가'에 달려있다는 것을 알 수 있었습니다. 좋은 pivot을 찾기 위한 효율적인 알고리즘이 있다면 성능이 좋아.. 공감수 0 댓글수 0 2022. 10. 4.
[Algorithm] 분할정복(2) - Multiplication 🤔 분할정복 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다. 이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다. 이번 포스팅에서는 분할정복의 Multiplication 예시를 알아보겠습니다. 🔎 Multiplication 두 n 비트 이진수인 $x$와 $y$를 곱하는 문제를 해결해보겠습니다. 분할정복 기법을 사용하여 이론적으로 더 빠른 알고리즘을 디자인 하는 방법에 대해 알아보겠습니다. 편의상 $n$은 2의 거듭제곱 꼴이라 가정하고, $x$의 왼쪽 $n/2$ 비트 부분과 나머지 부분을 각각 $x_L, x_R$이라고 하겠습니다. 마찬기자로 $y_L, y.. 공감수 0 댓글수 0 2022. 9. 29.
[Algorithm] 분할정복(1) - Master Theorem과 일반해 🤔 Divide And Conquer 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말합니다. 이때 분할된 문제들을 조합하여 큰 문제를 해결하는 것을 Conquer이라고 합니다. 이번 포스트에서는 분할정복을 Master Theorem의 일반해를 구하는 방법을 자세하게 알아보겠습니다. 🔎 Master Theorem Master Theorem에서 Input Size가 $n$일때 분할정복 알고리즘의 일반적인 패턴은 아래와 같습니다. 상수 $a > 0, b > 1, d ≥ 0$에 대하여 1. 문제를 size가 $\frac{n}{b}$인 $a$개의 subproblem으로 나눈다. (recursivel.. 공감수 0 댓글수 0 2022. 9. 28.
[Algorithm] 알고리즘 기본(2) - Basic Arithmetic 🤔 Basic Arithmethic 덧셈, 뺄셈, 곱셈, 나눗셈 즉 기본연산(사칙연산)을 Basic Arithmethic이라고 합니다. n-bit를 가지고 있는 기본적인 bit 연산에 대해 알아보도록 하겠습니다. 이전에 모든 계산에 있어 단일 bit에 대해 기본적인 bit 연산에 $O(1)$시간이 소모된다고 가정하겠습니다. 🔎 두 n-bit 이진수의 덧셈 $53$과 $35$의 이진수인 "1 1 0 1 0 1"과 "1 0 0 0 1 1"을 예시로 더해보겠습니다. 위와 같이 6bit 연산에서 최상위 비트에서의 Carry가 발생하여 7bit가 결과값으로 출력되었습니다. 두 개의 n-bit 짜리 이진수가 주어졌을 때 n 번의 덧셈이 반복되면서 일어나는 것을 알 수 있습니다. 즉 두 n-bit 이진수의 덧셈의 시.. 공감수 0 댓글수 0 2022. 9. 28.
[Algorithm] Master Theorem 맛보기 이번 포스팅은 Master Theorem을 처음 배우면서 맛보기(?)를 하면서 끄적인 것이기 때문에 두서가 없습니다. 분할정복에 대해 자세히 알고 싶으신 분은 아래를 참고해주시면 감사하겠습니다. 👉 분할정복 더보기 닫기 2022.09.28 - [Computer Science/Algorithm] - [Algorithm] 분할정복(1) - Master Theorem과 일반해 [Algorithm] 분할정복(1) - Master Theorem과 일반해 🤔 Divide And Conquer 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말 2t-hong.tistory.com 2022.09.29 - [.. 공감수 0 댓글수 0 2022. 9. 14.
[Algorithm] 분할정복 알고리즘 맛보기 이번 포스팅은 분할정복을 처음 배우면서 맛보기(?)를 하면서 끄적인 것이기 때문에 두서가 없습니다. 분할정복에 대해 자세히 알고 싶으신 분은 아래를 참고해주시면 감사하겠습니다. 👉 분할정복 더보기 2022.09.28 - [Computer Science/Algorithm] - [Algorithm] 분할정복(1) - Master Theorem과 일반해 [Algorithm] 분할정복(1) - Master Theorem과 일반해 🤔 Divide And Conquer 분할정복이란 일반적으로 주어진 문제를 작은 단위로 분할한 뒤 분할된 문제들을 재귀적으로 해결하여 해당 답을 적절하게 조합하여 큰 문제의 답을 제시하는 알고리즘을 말 2t-hong.tistory.com 2022.09.29 - [Computer Scie.. 공감수 0 댓글수 0 2022. 9. 13.
[Algorithm] 알고리즘 기본(1) - 알고리즘의 개념과 빅오 표기법 🤔 학습할 내용 이번 시간에는 알고리즘의 이론적 분석과 실험적 분석간의 차이점에 대해 살펴본 후에, Big-Oh notation에 대해 집중적으로 다뤄보도록 하겠습니다. 저번 학기 동안 Computer Structure에서 Big-Oh notation을 다뤘는데 조금 더 자세하게 배워보겠습니다. 🔎 Algorithm 알고리즘이란 어떤 문제를 풀기 위한 유한한 절차와 방법을 말합니다. 여기서 문제는 보통 '수학적으로 엄밀히' 정의된 문제에 한정됩니다. 조금 더 좁은 의미로는 입력값이 주어졌을 때, 수학적으로 엄밀히 정의될 수 있는 답(출력값)을 도출하는 절차와 방법입니다. 알고리즘의 성능을 분석하는 방법에는 실험적 분석과 이론적 분석이 있습니다. 실험적 분석(Experimental analysis) 주어진.. 공감수 0 댓글수 0 2022. 9. 5.

문의안내

티스토리
로그인
고객센터

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