꿈 많은 사람의 이야기

파이썬 알고리즘 기본을 계속 하고 있다. 지난 번에 공부 했던 힙 정렬, 삽입 정렬, 선택 정렬, 버블 정렬 등도 계속 복습도 해야하는데.. 주말에 해야하는데 참 쉽지 않다. 아무튼 이번 포스팅은 정말 기본적인 알고리즘이다. 숫자 뒤집는 방법(거꾸로 출력하는 방법), 소수 값 출력하는 방법과 배수 출력하는 방법이다. 너무 간단한다 먼저 배수이다 만약 3의 배수를 구하고 싶으면 어떤 값을 3으로 나누었을 때 0으로 떨어지면 그 값은 3의 배수이다 3과 5의 배수를 동시에 구하고 싶으면 n % 3 == 0 and n % 5 == 0 의 조건이 성립되면 된다 이 조건을 가지고 코드를 작성하면 된다. 아래와 같다. 숫자를 거꾸로 출력하는 방법(혹은 문자열을 거꾸로 출력)은 reverse 방법을 이용하는 방법이나..

이번 포스팅은 힙 정렬(heap sort)에 대해서 공부를 합니다. 먼저 힙(heap)에 대해서 알아야겠죠. 힙은 크기(우선 순위)을 중심으로 정렬된 시퀀스를 활용할 때 유용한 자료구조입니다. 힙은 한 노드가 최대 두 개의 자식노드를 가지면서 마지막 레벨을 제외한 모든 레벨에서 완전 이진트리(complete binary tree)를 기본으로 구조를 가지고 있습니다. 바로 위 사진처럼 되어 있는 구조가 힙 구조입니다. 잘 보면 이진 탐색 트리(binary search tree)와 구조가 살짝 차이가 있는데요 각 노드의 값은 자신의 자식노드보다 크거나 같습니다. 이게 이진 탐색 트리와는 차이점이죠. 이진 탐색 트리에서는 자식의 노드가 부모의 노드보다 값이 클 수도 있습니다. 하지만 힙에서는 그렇지 않습니다...

이번 포스팅은 합병정렬(Merge sort)에 대해서 정리합니다. 병합정렬이라고도 불리우는 이 정렬은 데이터를 잘게 쪼개고(divide) 크기를 비교해 정렬합니다(conquer) 그리고 이를 합칩니다(merge) 이를 더 이상 합칠 array가 없을 때까지 반복합니다. 위 그림을 보시면 쉽게 나와있습니다. 칸아카데미 페이지에 나와있는 설명인데요. 위에선 2개씩 잘개 쪼갭니다. 쪼갠 뒤 정렬을 하면서 합쳐줍니다. 그러면 최종적으로 정렬된 데이터가 나오게 되겠죠! 그럼 코드로는 어떻게 될까요? 파이썬을 활용해서 코드를 작성해봅니다. 풀 코드를 보기 전에 merge_sort가 어떻게 보이는지 봅니다. list가 1보다 작거나 같으면 return하고 그게 아니면 mid 값을 // 2로 해서 절반을 기준으로 합니..

이번 포스팅은 파이썬으로 자료구조, 알고리즘 공부하기 쉘 정렬(shell sort)과 버블 정렬(bubble sort)에 대해서 정리합니다. 여러가지 정렬 알고리즘이 있습니다. 지난 포스팅에선 삽입 정렬, 선택 정렬에 대해서 보았는데요 기본적인 정렬 중 버블 정렬이라는 것이 있습니다! 버블 정렬은 말 그대로 거품처럼 뽀글뽀글 올라가며 정렬을 하는데요 예시를 들면 이렇게 진행됩니다. 처음부터 하나씩 비교를 하면서 큰 것을 뒤쪽으로 몰아넣죠. 그리고 fix 시킵니다. 그리고 그 다음 루틴에서 또 돌고.. 이렇게 진행합니다. 바로 파이썬 코드로 봅시다 핵심은 def bubble_sort입니다. 정렬되지 않은 list를 입력 받습니다. 2개의 for문을 돌면서 진행합니다. 맨 처음 for문은 len - 1 범위..

파이썬으로 알고리즘, 자료구조 공부하기! 이번에는 삽입 정렬, 선택 정렬이다 정렬 알고리즘에서 많이 나오는 것들이 버블 정렬, 삽입 정렬, 선택 정렬 등이 있는데 당분간 이 정렬에 대해서 공부하고 정리하려고 한다! 먼저 선택 정렬(selection sort)이다 선택 정렬은 위 그림을 보면 이해가 편하다 매 step으로 나뉘어 진행하는데 첫 번째에 스탭을 돌면 가장 작은 값이 맨 처음으로 온다. 그리고 첫 번째 값을 fixed 시켜놓고 2번째 값 부터 시작하고 또 다시 비교한다. 그렇기 때문에 비교는 N * (N-1)만큼 비교를 하게 된다. 하지만 교환 횟수는 N - 1 정도이다 파이썬으로 코드를 구현해보자 이렇게 간단한 하나의 함수로 만들 수 있다. 2개의 for문을 돈다. N * (N -1)이므로 그..

지난번 포스팅에서 배열 정렬에 관해서 잠깐 다루었었습니다. http://lsjsj92.tistory.com/94 이 글을 보시면 배열에 관해 정리하면서 정렬도 다루었었는데요 sort 함수를 사용하면 정렬은 가능하지만 완벽하지는 않습니다. 예를들어 아래와 같은 상황이 발생되죠 숫자를 정렬한다고 가정합시다 숫자가 들어있는 somelist 배열에는 1,2,4,~ 256의 숫자가 들어있습니다. 그걸 sort 함수를 이용해서 정렬을 하면 아래와 같이 출력됩니다 이상하죠? 내가 원했던 정렬은 1,2,4,8 순서대로 가는 정렬인데요 1, 128, 16, 2, 256, 32, 4, 64, 8 순으로 정렬이 되어 있습니다. 자세히 보면 가장 맨 앞 숫자는 순서대로 작은 값입니다. 즉 정렬이 아스키값으로 정렬이 되기 때문..

펄 배열 2번째 이야기를 시작합니다. 몇몇 특징과, push, pop에 대해서 볼까해요! 먼저 아래와 같은 특징이 있습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 @who = (qw(fred array soojin lee))[2,3]; #이런식으로 잘라서 넣을 수도 있다. print($who[0].", ".$who[1]."\n "); @fred = (7,8,9); @barney = (2,1,0); @backfred = @fred[@barney]; #barney가 2,1,0 이니까 $fred[2] 와 같은 값이 들어간다. -> 슬라이스로 들어가게됨 #@fred[2,1,0] 또는 ($fred[2], $fred[1], $fred[0]), 또는 (9,8,7) 과 동일하다. for($i = ..

배열을 정렬하는 방법은 프로그래머가 직접 정렬 메소드를 만들어 사용할 수도 있지만 기본적으로 자바에서 제공해주는 정렬 기능도 있다. Arrays.sort()를 이용하면 된다. Arrays 클래스에 있는 sort()메소드이다. 다음 예제를 보자 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 public class SortEx { public static void main(String[] args) { int[] scores = {99, 95, 98}; Arrays.sort(scores); for(int i = 0 ; i