최씨네 블로그

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..

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 ..

3월 14일 코딩테스트를 준비하기 위해 남은 한달동안 파이썬을 이용해 알고리즘을 풀려고 합니다. 알고리즘과 파이썬 기초가 많이 부족하니 많이 지적해주시면 감사하겠습니다~~ :) 프로그래머스 문제풀러 가기 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 : def solution(heights): answer = [] for i in range(len(heights)-1,-1,-1): head = i - 1 while heights[head] = 0: head = head - 1 if head == -1: answer.append(0) else: a..