최씨네 블로그

https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 다익스트라 다익스트라 알고리즘은 그래프에서 간선 비용이 0 또는 양수일 때 그리고 시작 지점이 주어졌을 때 최소 비용 거리를 찾기에 유용한 알고리즘입니다. 원리는 간단합니다. (하지만 까먹습니다.) 1. 현재 노드에서 이동할 수 있는 후보 노드들을 조건을 따져 등록합니다. 2. 후보 노드들 중 비용이 가장 적은 노드로 이동합니다. (따라서 heap queue가 유용합니다) 3..

Union-Find Union - find(합집합 찾기) 알고리즘은 여러 개의 node들이 존재하고 노드들을 서로 이어 집합을 만들 때 서로 다른 노드가 같은 집합인지 확인할 때 사용하는 알고리즘입니다. union - find 말 그대로 union과 find 과정을 통해 알고리즘을 수행합니다. 예를 들어 다음과 같이 5개의 노드들이 있다고 가정해봅시다. 1 2 3 4 5 1 2 3 4 5 1 행은 각 노드 번호 2행은 각 노드의 부모 노드 번호입니다. 우선 시작 시 노드들은 각자 자신을 부모로 가리키고 있고 서로 연결되어 있지 않습니다. union 과정을 통해 노드 1, 4를 2, 5 를 연결해봅시다. 1 2 3 4 5 1 2 3 1 2 다음과 같이 숫자가 더 높은 노드가 아래 노드를 부모로 가지도록 했..

Counting Sort 계수 정렬은 말 그대로 데이터를 counting 하여 정렬되는 것과 마찬가지인 효과를 나타내는 정렬입니다. 앞서 보았던 정렬방식은 시간복잡도 O(N*N) 또는 O(N*logN)을 가졌습니다. 하지만 계수 정렬은 데이터를 한번씩만 접근하여 O(N)의 시간복잡도를 가질 수 있습니다. 어떻게 O(N)의 시간 복잡도를 가질 수 있을까요? 이유는 다른 정렬들은 데이터를 비교하고 위치를 바꾸지만 계수정렬은 데이터를 순차적으로 읽으면서 해당 데이터의 개수를 counting 하여 나중에 한번에 나타내는 방식이기 때문인데요. 이와 같은 이유 때문에 언제나 사용하기보다는 특정한 범위가 있고 중복이 많을 시 정렬이 효과적이라고 볼 수 있습니다. 계수정렬의 작동과정을 보면 다음과 같은 상황에 효과적입..

Quick sort 퀵 소트는 분할정복을 이용한 정렬방식 중 하나로 이름처럼 빠른 정렬입니다. 퀵 소트의 방식은 이렇습니다. 1. 무작위로 기준이 되는 수(pivot)를 고릅니다. 2. 이 때 피벗보다 작은 수를 왼쪽으로 놓습니다. 3. 피벗보다 큰 수를 오른쪽에 놓습니다. 4. 왼쪽과 오른쪽에 놓인 각각의 배열을 다시 1번 과정부터 반복합니다. 다음 아래와 같은 그림으로 보면 이처럼 pivot은 정렬된 것으로 보고 피벗을 기준으로 나머지를 분할하여 다시 피벗을 구해 마지막 피벗하나를 구할때까지 반복하는 구조입니다. 그렇다면 시간 복잡도 어떠할까요? 일반적인 경우의 시간복잡도는 NlogN을 가집니다. 왜냐하면 실제 N개의 수가 있다고 합시다. 만약 피벗이 정말 잘 골라져서 N이 딱 절반씩 계속해서 나눠진..

Insertion Sort Insertion sort란 필요한 경우에만 위치를 바꿔 적절한 위치에 원소를 삽입하여 정렬하는 알고리즘입니다. 그런데 이 필요한 경우를 알아내기 위해서는 조건이 필요합니다. 위치를 바꿀 요소의 앞 쪽 요소들이 모두 정렬되어있어야 하는 조건인데요. 그림을 통해 확인하면 다음과 같습니다. 4 3 5 1 2 4 3 5 1 2 3 4 5 1 2 3 4 5 1 2 1 3 4 5 2 1 2 3 4 5 1. 처음 위치해있는 4부터 확인합니다. 앞 쪽 요소가 없으니 건너뜁니다. 2. 다음 수 3을 확인합니다. 그 앞 요소인 4와 비교해 3보다 크니 위치를 바꿉니다. 3. 5를 확인합니다. 이미 1,2 과정에서 정렬이 되어있으므로 4하고만 비교를 합니다. 5가 더 크니 위치를 바꾸지않습니다...

Bubble Sort bubble sort란 배열 정렬 시 바로 옆의 수와 비교하여 자신이 옆의 수 보다 클 경우 위치를 바꾸는 정렬입니다. 선택 정렬과 마찬가지로 비효율적인 정렬 방식인데요. 실제 어떻게 작동하는지 한 사이클만 그림으로 확인해보면 다음과 같습니다. 3 2 5 7 1 2 3 5 7 1 2 3 5 7 1 2 3 5 7 1 2 3 5 1 7 1. 우선 첫 번째 인덱스부터 시작합니다. 첫 번째 인덱스에 있는 숫자 3이 2보다 크므로 서로 위치를 바꿉니다. 2. 그리고 두 번째 인덱스와 세 번째 인덱스를 비교합니다. 두 번째 인덱스에는 1번에서 위치가 바뀌었으므로 3을 5와 비교합니다. 3이 5보다 작으므로 바꾸지 않습니다. 3. 위치 변화와 상관없이 세번째 인덱스와 네 번째 인덱스를 비교합니다..

selection sort란 수를 정렬하는 방식 중 가장 원시적인 정렬 알고리즘으로 가장 작은 수를 찾아낸 다음 앞으로 보내는 방식의 정렬 방법입니다. 정렬방식 중 가장 기본적인 정렬방식입니다. 위 그림에서 보다시피 정렬되지 않은 부분에서 최소값을 찾아 앞으로 보내 차례대로 정렬하는 것입니다. (귀찮아서 손으로 그린건 안비밀) 그렇다면 선택정렬을 하기위해선 몇 번의 연산이 필요할까요? N개의 수가 있다면 처음 최솟값을 구해 정렬하는데 N번, 두번째는 N-1번 세번짼 N-2번 ... 마지막 한번까지 N! 번 연산이 필요합니다 이는 공차가 -1인 등차수열로 n(n+1)/2의 공식을 가집니다. 따라서 시간복잡도는 O(N^2)을 가지게 되고 N의 개수가 많아질수록 효율이 굉장히 떨어지게됩니다 ㅠㅠ 따라서 처리해..

프로그래머스 문제풀러가기 프로그래밍 강의 | 프로그래머스 기초부터 차근차근, 직접 코드를 작성해 보세요. programmers.co.kr import collections def solution(people, limit): answer = 0 _people = collections.deque(sorted(people)) while _people and _people[-1] > limit - 40: #무게 넘는 사람 탈출 answer += 1 _people.pop() while _people: light = _people.popleft() if not _people: answer += 1 while _people: heavy = _people.pop() if light + heavy

문제풀러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 def solution(n, lost, reserve): answer = n loster = [] for l in lost: if l in reserve: reserve.remove(l) else: loster.append(l) for l in loster: if (l-1) in reserve: reserve.remove(l-1) elif (l+1) in reserve: reserve.remove(l+1) else: answer = answer - 1 return answer 탐욕법에 관..

프로그래머스 문제 풀러가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이: from itertools import combinations as combi def solution(phoneBook): answer = True for (a,b) in combi( sorted(phoneBook, key= len),2): if a == b[:len(a)]: answer = False return answer 테스트 케이스는 통과했지만 효율성 측면에서 통과하지 못했습니다. 문제 풀이 과정에서 from itertools import combinations ..