본문 바로가기

자료구조 & 알고리즘108

[자료구조] 링크드 리스트(linked list) 👨🏻‍🏫 fastcampus 알고리즘/기술면접 완전 정복 올인원 패키지 - 이준희 강사님 1. 구조 연결 리스트 어떤 데이터를 저장할 때 그 다음 순서의 자료가 있는 위치를 데이터에 포함시키는 방식으로 자료를 저장 링크드 리스트는 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구현 리스트 타입이 링크드 리스트의 기능 지원 기본 구조와 용어 노드(Node) : 데이터 저장 단위 (데이터 값, 포인터)로 구성 포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 2. 장단점(전통적인 C언어에서의 배열과 링크드 리스트) 장점 미리 데이터 공간을 할당하지 않아도 됨 배열은 미리 데이터 공간을 할당 해야 함 단점 연결을 위한 별도 데이터 공간이 필요.. 2022. 9. 21.
[자료구조] 트리(Tree) 👨🏻‍🏫 fastcampus 알고리즘/기술면접 완전 정복 올인원패키지 - 이준희 강사님 1. 트리 구조 Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용되나? 트리 중 이진 트리(Binary Tree) 형태의 구조로, 탬색(검색) 알고리즘 구현을 위해 많이 사용됨 2. 용어 정리 Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node : 트리 맨 위에 있는 노드 Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 Child Node : 어떤 노드의 상위 레벨에 연.. 2022. 9. 19.
[알고리즘] 동적 계획법 (Dynamic Programming) 👨🏻‍🏫 fastcampus 알고리즘/기술면접 완전 정복 올인원패키지 - 이준희 강사님 1. 정의 동적계획법 (DP 라고 많이 부름) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 Memoization 기법을 사용함 Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨 예: 피보나치 수열 분할 정복 문제를 나눌 수 없을 때까지 .. 2022. 9. 8.
[알고리즘] 정렬 알고리즘 👨🏼‍🏫 이준희 강사님 fastcampus(알고리즘 이론) 목록의 요소를 특정 순서대로 넣는 알고리즘, 대개 숫자식 순서와 사전식 순서로 정렬 정렬의 시간 복잡도 1. 버블 정렬 가장 느린 알고리즘 ### 수도코드(sudo) Bubblesort(A) for i from 1 to A.length for j from 0 to A.length -1 if A[j] > A[j+1] swap a[j] with a[j+1] def bubblesort(A): for i in range(1,len(A)): for j in range(0, len(A)-1): if A[j] > A[j+1]: A[j], A[j+1] = A[j+1], A[j] bubblesort([2,3,5,1]) 2. 병합 정렬 ‘존 폰 노이만(John v.. 2022. 9. 7.
[CodeUp Python 기초 100제] # 98번_성실한 개미 /codeup.kr/problemsetsol.php?psid=33 문제집 / Python 기초 100제 codeup.kr 6098 : [기초-리스트] 성실한 개미(py) 영일이는 생명과학에 관심이 생겨 왕개미를 연구하고 있었다. 왕개미를 유심히 살펴보던 중 특별히 성실해 보이는 개미가 있었는데, 그 개미는 개미굴에서 나와 먹이까지 가장 빠른 길로 이동하는 것이었다. 개미는 오른쪽으로 움직이다가 벽을 만나면 아래쪽으로 움직여 가장 빠른 길로 움직였다. (오른쪽에 길이 나타나면 다시 오른쪽으로 움직인다.) 이에 호기심이 생긴 영일이는 그 개미를 미로 상자에 넣고 살펴보기 시작하였다. 미로 상자에 넣은 개미는 먹이를 찾았거나, 더 이상 움직일 수 없을 때까지 오른쪽 또는 아래쪽으로만 움직였다. 미로 상자의 구.. 2022. 4. 20.
[CodeUp Python 기초 100제] # 97번_설탕과자 뽑기 6097 : [기초-리스트] 설탕과자 뽑기(py) 부모님과 함께 놀러간 영일이는 설탕과자(설탕을 녹여 물고기 등의 모양을 만든 것) 뽑기를 보게 되었다. 길이가 다른 몇 개의 막대를 바둑판과 같은 격자판에 놓는데, 막대에 있는 설탕과자 이름 아래에 있는 번호를 뽑으면 설탕과자를 가져가는 게임이었다. (잉어, 붕어, 용 등 여러 가지가 적혀있다.) 격자판의 세로(h), 가로(w), 막대의 개수(n), 각 막대의 길이(l), 막대를 놓는 방향(d:가로는 0, 세로는 1)과 막대를 놓는 막대의 가장 왼쪽 또는 위쪽의 위치(x, y)가 주어질 때, 격자판을 채운 막대의 모양을 출력하는 프로그램을 만들어보자. 입력 첫 줄에 격자판의 세로(h), 가로(w) 가 공백을 두고 입력되고, 두 번째 줄에 놓을 수 있는 막.. 2022. 4. 20.

티스토리툴바