Data Structure(1) Linked List (연결 리스트) 📌Linked List (연결 리스트) linked list는 떨어진 곳에 존재하는 데이터들을 포인터로 '연결'해서 관리하는 data structure 장점(배열의 단점 극복): 비연속적 데이터를 포인터로 연결하기 때문에 메모리를 미리 할당받을 필요가 없음 배열은 연속적으로 연결된 공간에 데이터를 나열하기 때문에 특정한 연결된 공간을 미리 할당받아야 함 단점: 각 데이터마다 다음 노드를 가리키는 주소(포인터)도 같이 저장해야하므로 저장공간 효율↓ 첫 노드(head)부터 쭈우우-욱 검색해야 해서 연결 정보를 찾는 시간이 필요하여 데이터에 접근하는데에 시간이 소요 (배열은 index로 바로 접근 가능) 중간에 데이터를 추가/삭제할 때, 추가적 작업이 필요 📌일반(간단한) linked list .. BAEKJOON #2920) 음계 # 내 풀이 num = list(map(int, input().split())) result = [] for i in range(len(num)-1): if num[i]+1 == num[i+1]: result.append("ascending") elif num[i]-1 == num[i+1]: result.append("descending") else: result.append("mixed") if "mixed" in result: print("mixed") elif "ascending" in result: print("ascending") else: print("descending") # 풀이 num = list(map(int, input().split())) ascending = True descend.. Recursive Call (재귀함수, 재귀호출) 재귀함수는 매우 많은 알고리즘에서 사용된다. 앞으로 다룰 quick sort와 merge sort 알고리즘을 공부하기 전, 이 알고리즘들에 쓰이는 전략인 Dynamic Programming(동적 계획법)과 Divide and Conquer(분할 정복)에 대해 공부하기 위하여 오늘은 재귀함수를 공부하여 보겠다. 즉, quick sort와 merge sort를 공부하기 위해 DP와 DC를 공부해야하고 이를 위해서는 기본적인 재귀함수(재귀호출/재귀용법/recursive call)을 알아야한다... ㅎㅎ(앞으로 더 배워야 할 알고리즘들이 많으니 기쁜 마음으로 차곡차곡 공부를 해보자^0^/) 📌재귀 함수 recursive call 재귀 함수란, 함수가 본인 함수를 다시 호출하는 함수를 말한다. 📌재귀 함수의 일반.. 탐색알고리즘(2) Binary Search (이진 탐색) Binary Search 이진 탐색 탐색 알고리즘 중 두번째, 이진 탐색이다. 순차 탐색은 그냥 말그대로 앞에서부터 쭈우우-욱 미련하게 찾는 것이었다면 binary search는 리스트를 반씩 쪼개면서 찾는 데이터가 없을 것이라고 판단한 반쪽 리스트는 과감히 버린다. 따라서 당연히 순차 탐색보다 계산량이 적다. 반복문을 쓰지는 않지만 재귀용법을 사용하여 그에 따른 시간 복잡도를 가진다. 알고리즘 구현 def binary_search(data_list, search): if len(data_list) == 1 and search == data_list[0]: return True if len(data_list) == 1 and search != data_list[0]: return False if len(.. 탐색알고리즘(1) Sequential Search (순차 탐색) 정렬 알고리즘 5개를 마치고, 이번 포스팅은 탐색 알고리즘의 시작으로 순차 탐색에 대한 포스팅이다. 탐색 알고리즘은 말그대로 여러 데이터 중에서 내가 원하는 데이터를 찾아내는 알고리즘이다. 이 중 순차탐색은 알고리즘/자료구조 강의 전체를 통틀어서 가장 쉬웠던 부분이다. 그냥 python 기본 문법 공부하는 정도의 난이도랄까..?ㅎㅎㅋ 간단히 포스팅해보도록 하겠다-! Sequential Search 순차 탐색 순차탐색은 원하는 데이터를 찾고자할 때, 데이터가 담겨있는 리스트에의 맨 처음부터 하나하나 순서대로 비교해가며 탐색하는 알고리즘이다. sequential search 또는 linear search 알고리즘이라고도 불린다. (뭔가 더 설명을 쓰고 싶지만 진짜 이게 끝이다. ,,,ㅎㅋㅋ) 알고리즘 구현 .. 정렬알고리즘 - Quick Sort (퀵 정렬) | C, Python 코드 구현 이제 재귀함수에 대해 공부했으니 이를 이용해 quick sort를 공부하여 보겠다. Quick Sort. 정렬 알고리즘의 꽃이라고 할 수 있는 알고리즘이다. 공부하면서 정말 quick이라는 말이 왜 붙었는지 알 정도로 이해하기 간단하고 구현하기 굉장히 편리했다. 특히 pythonic code로 구현하니 코드가 아주아주 간결하고 깔끔했다. 코드가 간결할 뿐만 아니라 시간 복잡도 측면에서도 지금까지의 정렬 알고리즘보다 낮아지는 경우가 가능하였다. 살펴보자. 📌Quick Sort 퀵 정렬 quick sort는 pivot(기준점)을 정해서, 기준점보다 작은 데이터는 왼쪽에, 큰 데이터는 오른쪽으로 모으는 과정을 반복하여 정렬을 하는 알고리즘이다. 나누어진 왼쪽과 오른쪽이 재귀용법을 사용해서 그 안에서 또 왼쪽과.. 정렬알고리즘 - Merge Sort (병합정렬) | C, Python 코드 구현 📌Merge Sort 병합 정렬 분할(Divide): 정렬하고자 하는 리스트를 같은 크기의 2개의 리스트로 분할한다. 정복(Conquer): 각 리스트를 정렬하고, 각 리스트의 크기가 더 분할 가능하다면 재귀적으로 분할 정복을 반복한다. 결합(Combine): 정렬된 각 리스트를 하나의 리스트로 합친다. 📌puedo code 구현 split 만약 리스트 개수가 한 개이면 해당 값 리턴 그렇지 않으면 리스트를 left와 right로 나누기 (재귀용법을 이용하여 리스트 개수가 한 개가 될 때까지(더이상 쪼갤 수 없을 때까지)) left = split(앞) right = split(뒤) left와 right 합치기 merge 정렬된 숫자들을 넣을 리스트 생성 (sorted) left와 right의 비교할 데이.. 정렬알고리즘- Selection Sort (선택 정렬) | C, Python 코드 구현 정렬 알고리즘 중 세번째이다. 선택 정렬이다. 개인적으로 bubble sort와 insertion sort보다는 직관적으로 더 쉽다고 생각이 들었다. 왜냐하면 selection sort는 그냥 전체에서 최솟값을 찾아서 앞으로 옮기는 걸 계속 반복하는 알고리즘이기 때문이다. 우리가 흔히 프로그래밍이아닌 현실에서 숫자들을 정렬한다고 하면 바로 이 selection sort와 같은 방법을 쓸 것이다. 📌선택 정렬 Selection Sort 선택 정렬이란, 먼저 최소값을 찾고 그 최소값을 정렬된 이후의 맨 앞 인덱스까지 옮기며 정렬하는 것이다. 즉, 주어진 데이터 중 최소값을 찾음 해당 최소값을 데이터 맨 앞에 위치한 값과 교체함 맨 앞의 위치를 뺀 나머지 데이터를 동일한 방법으로 반복함 pseudo code .. 정렬알고리즘 - Insertion Sort (삽입 정렬) | C, Python 코드 구현 계속해서 정렬알고리즘에 대하여 공부하고 있다. 오늘은 정렬 알고리즘 중 삽입정렬 insertion sort에 대하여 알아보겠다. 삽입정렬을 두 번째 인덱스부터 기준점으로 잡고 기준점에서 앞 데이터들과 비교하며 기준점 데이터를 삽입할 위치를 정하여 정렬하는 알고리즘이다. 📌삽입정렬이란 삽입정렬은 두 번째 index부터 시작하고, 이를 기준점으로 잡는다. 해당 인덱스 앞에 있는 데이터들과 비교하여 기준점의 데이터의 값이 앞 데이터들보다 더 작으면, 기준점을 그 앞 데이터의 뒤 인덱스로 복사한다. (기준점 바로 앞에 있는 값들부터 하나하나 비교하며 기준점이 더 크면 swap한다고 볼 수도 있겠다.) 기준점이 앞 데이터들 중에서 자신보다 더 큰 데이터를 만날 때까지 이를 반복하고, 큰 데이터를 만난 위치 바로 .. 정렬 알고리즘 - Bubble Sort (버블 정렬) | C, Python 코드 구현 알고리즘 공부 시작-! 알고리즘에서 기본 중의 기본, 필수 중의 필수, 정렬 알고리즘 sorting algorithm에 대하여 공부를 시작한다. 정렬 알고리즘의 종류는 매우 다양하며, 따라서 똑같은 문제에 대해서도 다양한 알고리즘이 고안될 수 있다. 이때, 각 알고리즘간 성능 비교와 분석을 통해 보다 효율적인 알고리즘을 사용할 수 있도록 공부해보자. 정렬 sorting 정렬 sorting: 주어진 데이터들을 정해진 순서대로 나열하는 것 프로그램 작성시 필요한 경우가 많음 알고리즘 학습에서의 기본!! 버블정렬 bubble sort bubble sort는 두 인접한 데이터를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 sorting algorithm이다. 버블 정렬은 인접한 두개.. 이전 1 ··· 13 14 15 16 다음
