DFS/BFS 실제
1) DFS 그래프 탐색 python 코드 구현 스택이 아닌 재귀호출을 이용한 DFS 구현 2) BFS 그래프 탐색 python 코드 구현 데크를 이용한 BFS 구현
Merge sort
Divide and conquer 문제를 쪼개서 각각 따로 처리한 다음 결과를 합쳐나가는 방법. Merge 배열의 길이가 1이면 정렬이 끝난 것이다. 아니라면 배열을 반으로 나눠서 왼쪽과 오른쪽을 따로 정렬한다. 둘 다 정렬이 끝나면 merge라는 작업을 통해 배열을 합쳐준다. Merge operation 이미 sorted인 2개의 서브 배열 이 2개의 서브 배열의 merge된, 병합된 하나의 결과를 담을 배열 와 같이... » read more
Insertion sort
삽입정렬 sorted된 배열에 원소를 추가할때 sorted가 깨지지 않게 원소의 위치를 찾아서 넣는 알고리즘이 insertion sort다. 각 숫자를 적절한 위치에 삽입하는 정렬 기법이다. 들어갈 위치를 선택하는데 N번, 선택하는 횟수로 N번이지만 선택정렬보다 약간 빠르다. 선택정렬과 똑같이 O(N^2) 의 시간 복잡도를 가진다. 삽입정렬의 작업 순서 가장 앞 인덱스의 원소가 정렬되어있다고 가정했을때 바로 뒷부분의 인덱스부터 올바른 위치로 insertion하는 알고리즘이다. temp변수를 두고... » read more
알고리즘; 해싱 #2, 스택, 정렬
2월 4일 목요일 알고리즘 스터디에서 진행한 프로그래머스 문제 풀이다. 브레인스토밍과 채점이 끝나고 다른사람의 코드 보기를 보면 파이써닉한 코드가 많은데 그렇게까지 해야 할 필요가 있나 싶다.. 프로그래머스 해시 #3 코드 및 알고리즘 해설 같은 카테고리로 dictionary를 만든다 dictionary key의 길이를 구한다 (총 카테고리의 개수) n개의 카테고리중 1개만 입는 경우를 구한다 → 각 카테고리의 원소 개수를 전부... » read more
알고리즘; 문자열 해싱 #1
오늘 한 것 알고리즘 교집합 슬라이딩 윈도우 습득한 지식 프로그래머스 Hash; 완주하지 못한 선수 참가자와 완주자의 명단에서 완주하지 못한 참가자를 가져온다. 두 리스트의 교집합을 증명하는 과정에서 완주자와 비교해 참가자를 반환한다 (완주하지 못한 참가자) 소스코드 프로그래머스 Hash; 전화번호 목록 리스트 내 원소에 대해 슬라이딩 윈도우로 비교하고 요구조건에 따라 boolean을 반환한다. 소스코드 프로그래머스 Hash; 위장 첫번째 시도... » read more
단방향 암호화 Hash함수
Hash 함수 해시함수는 메시지 길이가 길던, 짧던 항상 동일한 길이의 메시지를 만들어내는 함수다. 메시지를 일정한 길이의 블록으로 분할 후 해시 함수에 입력한다. 짧고 일정한 길이의 메시지 다이제스트 (160,256,512bit)생성 대표적인 Hash함수 : MD5, SHA-256, SHA-512 1) Hash 함수의 요구사항 어떤 크기의 데이터 블록이든지 적용 가능해야 한다. 일방향성을 만족해야한다 = 메시지 다이제스트로부터 원래의 메시지를 만들어낼 수 없어야... » read more