Merge sort

Divide and conquer 문제를 쪼개서 각각 따로 처리한 다음 결과를 합쳐나가는 방법. Merge 배열의 길이가 1이면 정렬이 끝난 것이다. 아니라면 배열을 반으로 나눠서 왼쪽과 오른쪽을 따로 정렬한다. 둘 다 정렬이 끝나면 merge라는 작업을 통해 배열을 합쳐준다. Merge operation 이미 sorted인 2개의 서브 배열 이 2개의 서브 배열의 merge된, 병합된 하나의 결과를 담을 배열 와 같이 …
Merge sort 더보기

Insertion sort

삽입정렬 sorted된 배열에 원소를 추가할때 sorted가 깨지지 않게 원소의 위치를 찾아서 넣는 알고리즘이 insertion sort다. 각 숫자를 적절한 위치에 삽입하는 정렬 기법이다. 들어갈 위치를 선택하는데 N번, 선택하는 횟수로 N번이지만 선택정렬보다 약간 빠르다. 선택정렬과 똑같이 O(N^2) 의 시간 복잡도를 가진다. 삽입정렬의 작업 순서 가장 앞 인덱스의 원소가 정렬되어있다고 가정했을때 바로 뒷부분의 인덱스부터 올바른 위치로 insertion하는 알고리즘이다. temp변수를 두고 …
Insertion sort 더보기

알고리즘; 해싱 #2, 스택, 정렬

2월 4일 목요일 알고리즘 스터디에서 진행한 프로그래머스 문제 풀이다. 브레인스토밍과 채점이 끝나고 다른사람의 코드 보기를 보면 파이써닉한 코드가 많은데 그렇게까지 해야 할 필요가 있나 싶다.. 프로그래머스 해시 #3 코드 및 알고리즘 해설 같은 카테고리로 dictionary를 만든다 dictionary key의 길이를 구한다 (총 카테고리의 개수) n개의 카테고리중 1개만 입는 경우를 구한다 → 각 카테고리의 원소 개수를 전부 …
알고리즘; 해싱 #2, 스택, 정렬 더보기

알고리즘; 문자열 해싱 #1

오늘 한 것 알고리즘 교집합 슬라이딩 윈도우 습득한 지식 프로그래머스 Hash; 완주하지 못한 선수 참가자와 완주자의 명단에서 완주하지 못한 참가자를 가져온다. 두 리스트의 교집합을 증명하는 과정에서 완주자와 비교해 참가자를 반환한다 (완주하지 못한 참가자) 소스코드 프로그래머스 Hash; 전화번호 목록 리스트 내 원소에 대해 슬라이딩 윈도우로 비교하고 요구조건에 따라 boolean을 반환한다. 소스코드 프로그래머스 Hash; 위장 첫번째 시도 …
알고리즘; 문자열 해싱 #1 더보기

코딩테스트를 위한 파이썬 정리

알고리즘 스터디를 위해 파이썬에서 코딩테스트를 위해 자주 쓰이는 연산자와 내장함수 관련 내용을 간략하게 정리해봤다. 연산 기존 언어와 파이썬에서 다른 연산자 파이썬에서 나누기는 /와 //가 있다. 전자는 소수점을 표시하고 후자는 정수만을 생성한다. 파이썬의 제곱 연산자는 ** 이다. 그 외 C스타일과 동일. 추가적인 연산관련 내장함수 문자열 혹은 리스팅 + : 문자열의 연결 string[i:j] : 분할 얕은 복사 …
코딩테스트를 위한 파이썬 정리 더보기