[실전 알고리즘] 0x14강 - 투 포인터안녕하세요, 이게 강의 목차를 16진수로 붙이니까 혼동을 주는데 이번 강의가 0x14강이니까 오리엔테이션은 빼고 20번째입니다. 아직 갈길이 좀 멀긴 하지만 꽤 많이 온 것 같습니다. 여러분들도blog.encrypted.gg바킹독님의 블로그를 참고하여 공부한 내용을 기록한 글입니다.투포인터 알고리즘은 배열에서 원래 이중 for문으로 O(N^2)으로 처리되는 작업을 2개의 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. 어떻게 N이나 줄일 수 있냐면, 일반적인 이중 for문에서 i = 0일 때 j가 0부터 n-1까지 돌고, i = 1일 때 j가 0부터 n-1까지 도는 방식, 즉 각 i에 대해서 j가 0부터 n-1까지 도는 상황을 생각해보면, i = 0일 때 계..

[실전 알고리즘] 0x13강 - 이분탐색안녕하세요, 이번 시간에는 이분탐색을 배워보도록 하겠습니다. 사실 이분탐색의 개념 자체는 그렇게 어렵지는 않습니다. 초등학생 정도만 되어도 업다운게임같은걸 아주 재밌게 즐길 수 있고,blog.encrypted.gg바킹독님의 블로그를 바탕으로 정리한 글입니다.이분탐색은 업다운 게임을 생각하면 이해가 편하다. 1에서 50 사이의 숫자를 찾으려면 25를 부르는게 가장 합리적인 것이다. 가장 기본적인 형태의 이분탐색은 이 업다운 게임의 기조를 띄고 있다. 특정 범위를 줄여가면서 특정 조건을 만족하는 데이터를 찾는 것이다. 구현적으로는 이미 STL에 잘 구현되어있기에 어려운 부분이 전혀 없다. 하지만 이분탐색은 응용이 들어가게 되면 굉장히 어렵고 특히 코딩테스트에서 가장 어..

[실전 알고리즘] 0x11강 - 그리디안녕하세요, 그리디를 공부해봅시다. 그리디 알고리즘을 한국어로 번역하면 욕심쟁이 알고리즘입니다. 그리디라고 부를 때랑 다르게 욕심쟁이 알고리즘이라고 하면 떼쓰는 어린 아이가 생각나blog.encrypted.gg바킹독님의 블로그를 바탕으로 정리한 글입니다.그리디 알고리즘은 탐욕적으로 지금 상태에서 가장 최적인 답을 선택하는 알고리즘이다.이를 다르게 말하면 관찰을 통해 탐색 범위를 줄이는 알고리즘이다.조금 더 쉽게 풀어보자면 현재 상태를 관찰해서 원래라면 O(N^2) 만큼 탐색해야 하는걸 O(N) 정도로 줄이는 것이다.예를 들어 merge sort를 생각해보자. 병합 과정의 한 step을 생각해보면, 정렬된 결과 배열에 들어갈 하나의 원소를 선택해야 한다.이 과정에서 현..

[알고리즘] 최소 신장 트리 - 크루스칼 알고리즘과 Union Find, 백준 1197번 C++ 풀이[실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MST라고 많이들 부릅니다. 그런데 Sjun-n.tistory.com  [알고리즘] 최소 스패닝 트리 - 프림 알고리즘이전 글에 이어지는 글입니다. [알고리즘] 최소 신장 트리 - 크루스칼 알고리즘과 Union Find, 백준 1197번 C++ 풀이[실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트jun-n.tistory.com크루스칼과 프림이 뭔지 모른다면 위의 두 글을 읽고오자...

이전 글에 이어지는 글입니다. [알고리즘] 최소 신장 트리 - 크루스칼 알고리즘과 Union Find, 백준 1197번 C++ 풀이[실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MST라고 많이들 부릅니다. 그런데 Sjun-n.tistory.com크루스칼 알고리즘에 이어서 프림 알고리즘을 알아보자. 임의의 정점을 선택해 최소 신장 트리에 추가최소 신장 트리에 포함된 정점과 최소 신장 트리에 포함되지 않은 정점을 연결하는 간선 중 비용이 가장 작은 것을 최소 신장 트리에 추가최소 신장 트리에 V-1 개의 간선이 추가될 때까지 2번 과정을 반복방법 자체는 크루스칼과 유사..

[실전 알고리즘] 0x1B강 - 최소 신장 트리안녕하세요, 오늘 다룰 주제는 최소 신장 트리(Minimum Spanning Tree)라는 개념입니다. 보통 코딩 좀 치는 사람들 사이에서는 MST라고 많이들 부릅니다. 그런데 Spanning이나 신장 이 단어가 너무 낯설지blog.encrypted.gg바킹독님 블로그를 참조하여 쓴 글입니다. 신장 트리란?신장 트리는 무방향 그래프의 부분 그래프들 중에서 모든 정점을 포함하는 트리이다. 사진의 왼쪽 그래프에서 오른쪽 그래프는 모두 신장 트리이다. 신장 트리라 하면 당연히 연결 그래프가 되겠고, 트리이므로 당연히 사이클이 존재해선 안된다. 최소 신장 트리는 신장 트리 중에서 간선의 합이 최소인 트리를 말한다. 최소 신장 트리는 동일한 그래프에서 여러 개 존재할..