알고리즘 (15) 썸네일형 리스트형 링크드 리스트(Linked List) - 1 링크드 리스트 구조 연결 리스트라고도 함 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조 (미리 그 길이를 정해둬야한다.) 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 여결해서 관리하는 데이터 구조 파이썬은 리스트 타입이 링크드 리스트의 기능을 모두 지원 링크드 리스트 기본 구조와 용어 노드(Node) : 데이터 저장 단위(데이터값, 포인터) 로 구성 포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 # 기본 노드 만들기 class Node: def __init__(self, data): self.data = data # 이전 노드와 연결 할 데이터 값 self.next = None # 다음 노드와 연결 할 주소 공간 if __n.. 스택(Stack) 스택(stack) 데이터를 제한적으로 접근할 수 있는 구조 (한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조) 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 데이터 구조 (LIFO 정책) 스택 구조 스택은 LIFO(Last In First Out) 또는 FILO(First In Last Out) 데이터 관리 방식을 따름 LIFO : 마지막에 들어간것이 가장 먼저 나온다. FILO : 처음 들어간것이 가장 나중에 나온다. 대표적인 스택의 활용 - 컴퓨터 내부의 프로세스 구조의 함수 동작 방식 주요 기능 push() : 데이터를 스택에 넣기 pop() : 데이터를 스택에서 꺼내기 스택 구조와 프로세스 스택 스택 구조는 프로세스 실행 구조의 가장 기본 자료 구조 스택의 장단점 장점 구조가 단순해서, 구현이.. 큐(Queue) 큐(Queue) 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 예) 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일 (줄을 서는 행위와 유사하다) FIFO 와 LILO 정책이다. 알아둘 용어 Enqueue : 큐에 데이터를 넣는 기능 Dequeue : 큐에서 데이터를 꺼내는 기능 큐가 많이 쓰이는곳 멀티 태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용됨 LIFO Queue Last In First Out으로 마지막에 들어간 데이터가 가장 앞에 있는 데이터가 된다. 그러므로 데이터를 꺼내 올 땐 가장 마지막 데이터 부터 꺼내올 수 있다. (스택과 같은 형태라고 생각하면 된다.) import queue # LIFO 기법 data_queue = queue... 재귀함수 재귀함수는 자기 자신을 다시 호출하는 함수를 의미 한다. 자신을 호출하면서 (재귀함수 - 복사본)이 만들어져서 실행되기 때문에 가능하다. 그렇다면 계속 자신을 호출하면 언제 끝내야하나? 그래서 재귀함수에서 필요한게 재귀의 탈출 조건이다. 예를들어 재귀의 탈출 조건이 0이 탈출 조건이라면 해당 조건이 성립되어 함수가 반환되기 시작한다. (자기 자신을 호출 했던 반대로 타고 올라간다 생각하면 된다.) 몇가지 예시를 코드로 들어볼 수 있다. # 1 def func(n): if n == 1: return n elif n % 2 == 0: return func(int(n / 2)) else: return func(3 * n + 1) func(3) 위 코드는 짝수일때 n을2로 나누고 홀수일때 3*n+1을 한다. 그.. 삽입정렬 -스터디- 삽입정렬이란? 정렬되지 않은 부분의 데이터를 뽑아서 정렬된 부분의 적절한 위치에 삽입하는 방법이다. 말 그대로 삽입 해서 넣는 정렬 방법이다. 다른 정렬방식과는 다르게 앞의 원소들과 큰지 작은지 비교하여 정렬하는 방식이다. 앞의 원소와 비교해야하기 때문에 index1부터 시작한다. (제일 앞의 index는 0이다.) 리스트의 길이가 길 수 록 효율이 떨어진다. 공부 방법 정렬 순서를 차근차근 손으로 써가며 알아봤다. 손으로 쓰기 좀 길지만 길이가 5인 리스트를 정렬해 보았다. 삽입정렬은 두번째 원소인 index가 1인 원소부터 시작해야한다는 점을 기억하고 시작하자. 전체적인 흐름을 말하자면 삽입할 index와 비교할 index의 크기를 비교하여서 비교할 index가 더 크면 서로의 위치를 바꾸는 방식이다.. 선택정렬 -스터디- 선택정렬이란? 리스트(배열)안에 난잡하게 정렬되어있는 수들을 오름차순(1->2->3->...) 시킨것이다. 그런데 어떻게 정렬시켰는지가 중요한데, 버블정렬처럼 현재 선택된 수와 그 다음수를 비교해서 변경하는것과는 약간 다르게 선택된 인덱스에 있는 값과 리스트 전체의 값들을 한번씩 비교해가며 한번 순회할때마다 최소값을 찾아서 처음 선택된 인덱스와 바꿔주는 것을 선택정렬이라한다. 공부 방법 노트에 직접 적어가며 리스트의 내용이 선택정렬로 정리 되는 과정을 하나하나 직접 그려가며 말로 나열 하며 이해함. [5, 4, 3, 2, 1] 이라는 리스트가 있다. 해당 정렬 기법은 처음 선택된 idx와 해당 idx를 제외한 전체 리스트의 idx의 값을 비교하여최소값을 찾아서 선택된 idx와 최소값으로 선택된 idx를 .. 버블정렬 - 스터디- 무엇인가? 순서 없이 정렬된 리스트를 하나하나 비교해가며 순서대로 정렬하는 기법이다. (오름 차순으로 정렬하는걸 정리함) 공부 방법 노트에 직접 상황들을 적어가며 공부함 길이가 긴 리스트여도 흐름을 파악할때까지 리스트의 길이를 늘림 다행히 길이가 4까지만 해도 이해가 되었다. 생각한 내용 적어보기 처음 생각한대로 내용 적고 코딩한 결과 list1 = [5, 3, 4, 1, 2] for i in range(len(list1)): for j in range(len(list1)-1): if list1[j] > list1[j+1]: list1[j+1], list1[j] = list1[j], list1[j+1] print(list1) 첫 for문에서 list1의 길이를 체크해서 그 횟수만큼 돌고 j가 포함되어있는.. 약수의 합 프로그래머스 약수의 합 정수 n을 입력받아 n의 약수를 모두 더한 값을 리턴하는 함수를 완성하라. ex) 12의 약수는 1, 2, 3, 4, 6, 12입니다. 이를 모두 더하면 28입니다. public class Solution2 { public int solution(int n) { int answer = 0; if(n == 1) { answer = 1; }else { for(int i=1;i 이전 1 2 다음
