코딩 이야기/알고리즘 이야기 (8) 썸네일형 리스트형 병합정렬(merge sort) 알아보고 구현하기 Merge sort? 병합정렬, 병합의 뜻은 2개가 하나로 합쳐짐을 의미한다. 즉 정렬되지 않은 리스트를 하나로 합치며 정렬하는 정렬알고리즘이다. 그리고 당연히 2개의 배열을 합치려면, 처음에 주어진 배열을 쪼개는 과정도 필요하다. 병합정렬은 크게 두 가지의 과정이 필요하다 나누기 합치며 정렬하기 8칸의 배열이 있다고 가정을 하자 그리고 우리는 이것을 2개씩 나눈다. 그리고 또 나눠진 2개의 배열을 각각 2개로 계속 나눠서 결국 하나씩 남게 한다. 그리고 이 남은 8개의 값을 나누기 직전에 같은 배열이였던 값과 비교해서 정렬을 시켜서 합친다. 그리고 이제 남은 4개의 배열을 또 합쳐야하는데 어떻게 합칠까? 위에서 합치며 정렬한다고 했다. 그 과정을 봐보자. [3,7]과 [1,6]을 합치는 과정을 한번 보.. Union-Find(유니온 파인드)에 대해 알아보고 구현하기 Union-Find? 유니온 파인드. 그대로 해석하면 union은 조합, find는 찾다로 해석이 가능하다. 실제로 이 알고리즘은 두 연산 find와 union를 사용한다. 여러 개의 노드가 있다고 가정했을 때 2개의 노드를 union을 통해 합치는 것도 가능하고, find를 통해 해당 노드의 부모노드를 찾는 것 또한 가능하다. 전체적인 구현 방법 노드들의 부모를 나타낼 배열을 선언해줘야한다. 예를 들어 트리를 다룬다고 했을 때 직접적으로 간선을 옮겨주는 식으로 할 수 없는가? 라는 생각을 가질 수 있으나, 가능은 하나 노드들의 부모가 하나로 통일됬는 지 검사하는 등의 연산이 필요할 경우, 시간복잡도가 난해해지므로 O(n)으로 끝낼 수 있게 노드들의 부모를 나타낼 배열을 선언해줘야한다. 부모노드가 없을 .. 파이썬 투포인터 알고리즘 사용하기(Two pointer) 투포인터 알고리즘? 투포인터 알고리즘은 이름에서 알 수 있듯 2개의 포인터를 사용하는 알고리즘이다. 슬라이딩 윈도우 알고리즘과도 많이 비교가 되는데, 그 이유는 밑에서 설명하겠다. 투포인터 알고리즘은 배열의 인덱스를 가르키는 2개의 포인터를 설정하고, 이를 옮겨가면서 내가 원하는 값을 찾는 알고리즘이다. 투포인터는 간단하기도 해서 그냥 바로 예시 상황을 보고 이해하는게 빠를 것이다. 상황 1. 길이가 5인 배열이 하나 있다. 이 안에는 임의의 10미만의 정수가 할당되어있다. 2. 이 배열에서 어느 한 부분을 잘라서 그 부분의 합이 15가 되는 부분을 찾고 출력하라. 1 4 2 5 3 6 순서로 보시면 된다. (S = 보라색포인터와 파란색포인터 사이의 값의 합) 1. 보라색 포인터와 파란색 포인터가 둘다 .. 파이썬 다익스트라 알고리즘 사용하기 다익스트라 알고리즘 다익스트라 알고리즘은 탐색 알고리즘으로 최단경로를 찾는 알고리즘이다. 이름이 다익스트라인 이유는 이 다익스트라 알고리즘을 만든 사람의 이름이 '에츠허르 데이크스트라'라서 라고한다. 이 알고리즘의 핵심은 가중치가 있는 그래프에서 비용(cost)가 가장 적은 경로를 찾는데에 있다. 다익스트라 알고리즘이 네비게이션 같은 GPS 소프트웨어 많이 활용된다. 초기의 다익스트라 알고리즘은 O(V^2)의 시간복잡도를 가졌었지만, 이후 우선순위 큐로 인한 개선으로 O((V+E)LogV)를 가지게 되었다. 과정 (그래프는 인접행렬이든 인접리스트이든 상관없다. 허나 글에선 편의를 위해 인접행렬 사용) 상황은 보라색 정점에서 주황색 정점까지 가야하는데 가장 적은 비용으로 가야한다. (보라색 정점 = 0, .. 파이썬 탐욕(그리디) 알고리즘 사용하기 탐욕 알고리즘? 그리디 알고리즘? 탐욕 알고리즘은 이름하고 유사한 구조를 가진 알고리즘이다. 탐욕 알고리즘을 다른 말로 그리디 알고리즘 혹은 욕심쟁이 알고리즘이라고도 한다. 탐욕이라는 이름 그대로 지금 당장의 문제가 하나 주워졌을때, 나중은 고려하지 않고 지금의 가장 최적의 답을 도출하는 알고리즘이다. 한가지 상황을 예시로 들자면 사자성어 "조삼모사"가 떠오른다. 누군지는 기억안나는데 암튼 누군가가 원숭이들을 기르는데, 먹이가 부족해서 먹이를 줄여서 원숭이들에게 아침에 3개 저녁에 4개를 준다고 하자 원숭이들이 화를 냈다. 그러자 주인이 아침에 4개 저녁에 3개를 주겠다고 하니 원숭이들이 좋아한다는 그런 내용의 사자성어이다. 내용 그대로 당장 지금의 상황만 중요한 원숭이들이 그리디 알고리즘과 흡사하다. .. 파이썬 인접행렬과 인접리스트 사용하기 서론 요즘 소홀히 하던 알고리즘은 다시 좀 오랜만에 풀어보려한다. 알고리즘도 어찌보면 수학과 비슷한 점이 많다. 수학도 한 2주 정도만 안풀다풀면 뭔가 개념도 기억이 잘 안나고 막히는 게 좀 많다. 알고리즘도 오랜만에 풀면, 개념도 잊어먹고, 막히는게 많은 것이다. 그래서 나도 알고리즘을 소홀히 하지 않기 위해 노력중이다. 자주 풀진 않더라도 감을 잃지 않을 정도만 하려한다. 인접행렬, 인접리스트가 뭐야? 인접행렬과 인접리스트는 알고리즘에서 그래프를 표현하기 위한 방법이다. 인접행렬 인접행렬은 그래프를 표현할 수 있는 방법 중 가장 간단한 방법이다. 인접행렬은 이중리스트를 통해 표현한다. 만약 그래프의 노드의 수가 n개라고 치면 인접행렬의 크기는 n*n이 될 것이다. 그렇기에 그래프가 커지면 잡아먹는 공.. 알고리즘 백트래킹에 대해 알아보자 서론 흠.. 특별히 쓸 글이 없어서 오늘은 백트래킹에 대해 알아보려한다. 백트래킹을 알면 백준 골드 문제도 많이 풀 수 있으니, 같이 오늘 알아보도록 하자. 백트래킹이 뭘까? 그대로 번역하면 뒤를 쫓다 정도의 해석이 가능하겠다. 하지만 실제 알고리즘은 그런 내용은 아니다. 백트래킹은 완전탐색의 연장선인데, 완전탐색을 하되, 굳이 탐색할 필요 없는 구간은 배제해버리고 완전탐색을 돌리는 것이다. 그렇기 때문에 당연히 재귀함수 혹은 for문을 사용하여 구현을 한다. DFS 개념에서도 방문하는 정점이 비효율적일 경우 배제하면서 순회하는 것 또한 백트래킹이라고 할 수 있다. 원래는 N-Queen 문제가 백트래킹의 유명한 문제인데, 아직 풀지 않아서 다른 문제를 올리도록 하겠다. 이제 백준 문제를 통해 백트래킹 문.. 알고리즘 완전탐색(브루트 포스)에 대해 알아보자 서론 오늘은 금요일이다. 몸이 많이 지치고 힘들지만, 글은 써야하니까. 특히 요즘 글을 제대로 못쓰기 때문에 주말에는 좀 더욱 열심히 써야한다. 내일은 파이썬 강좌를 마저 쓰도록 하겠다. 완전탐색(브루트 포스)이 뭘까? 완전탐색은 말 그대로 모든 경우의 수를 전부 닥치는대로 해보는 것이다. 실생활에서 예를 들자면, 자물쇠를 열어야하는데, 열쇠 꾸러미 중 맞는 열쇠가 뭔지 모른다면, 열쇠 꾸러미에 있는 모든 열쇠를 다해보는 것처럼. 무식하게 전부 다 대입해보는 방법이다. 만들기 쉽고 간단하지만, 그만큼 수행시간이 상당히 긴 알고리즘이다. 완전탐색을 하는 방법은 이렇게 있다. for if 사용하기 비트마스크 재귀함수 BFS 그 중 가장 간단한 for if를 사용하는 방법을 알아보자. 예시 정렬되지 않은 배열.. 이전 1 다음
