패캠챌린지

패스트캠퍼스 챌린지 18일차

강의 날짜: 11/18/2021 시청 강의: 은근히 어려운 자료구조 : 링크드 리스트 LinkedList 정의 연결 리스트 (Linked List)로 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어있는 방식의 자료 구조. 링크드 리스트는 인덱스가 존재하지 않기 때문에 검색 및 수정 시 첫 번째 노드부터 순차적으로 모든 노드를 탐색해야 한다 → 시간 복잡도 : O(1) 특정 위치(index)로 삽입/삭제/탐색해야 하는 경우는 O(n) 이 걸린다. 따라서, 탐색을 자주해야 한다면 배열을 사용하고, 데이터의 추가/삭제가 많은 경우에 연결 리스트를 사용하는 것이 좋다. 연결 리스트는 단일 연결리스트, 이중 연결리스트, 원형 연결리스트가 있다. 단일 연결리스트 (Singly Linked List) 단일 연결..

패스트캠퍼스 챌린지 17일차

시청 날짜 : 11/17/2021 시청 강의 : 스택 Stack 데이터를 제한적으로 접근할 수 있는 구조 -> 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 구조 스택도 큐와 마찬가지로 https://visualgo.net/en/list에서 시뮬레이션해볼 수 있음. LIFO (Last in First Out) 가장 나중에 쌓은 데이터를 가장 먼저 뺄 수 있는 데이터 구조 FILO라고도 함 대표적인 스택의 활용 : 컴퓨터 내부 프로세스 구조의 함수 동작 방식 용어 push() : 데이터를 스택에 넣기 pop() : 데이터를 스택에서 꺼내기 peek() : 스택에 가장 마지막의 데이터 확인 장점 구조가 단순해서 구현이 쉽다 데이터 저장/읽기 속도가 빠름 단점 일반적인 스택 구현 시, 데이터 최대 개수를 미리 정해..

패스트캠퍼스 챌린지 16일차

시청 날짜 : 11/16/2021 시청 강의 : 큐 프로그래밍 중 가장 많이 쓰이는 자료구조 중 하나 : Data in and Data out 만 가능 https://visualgo.net/en/list의 queue탭에서 시뮬레이션 가능 FIFO (First in, First out) LILO라고도 불림 (last in last out) 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 (스택과 반대) front (앞)에선 무조건 삭제가 일어나고, rear(뒤, tail이라고도 함) 에선 무조건 삽입이 일어난다 "줄 서기"와 동일 용어 enqueue : 큐에 데이터를 넣는 기능 dequeue : 큐에서 데이터를 꺼내는 기능 peek : 맨 앞의 데이터가 무엇인지 훔쳐보는 기능 (literarlly ..

패스트캠퍼스 챌린지 15일차

시청 날짜 : 11/15/2021 시청 강의 : 투포인터(Two Pointers) Two Pointers 투포인터 알고리즘이란 화살표 두개에 의미를 부여해서 탐색 범위를 압축하는 방법 1차원 배열 위에 2개의 포인터를 만드는 경우 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동 start→ start→ 10 11 18 19 54 21 -> 전형적인 double for loop int[] arr = {10,11,18,19,54,21}; int N = arr.length; for(int i = 0 ; i< N ; i++){ //i 포인터 for(int j = 0 ; j< N ; j ++){ //j 포인터 ... } } 2개의 포인터가 양 끝에서 서로를 향해 이동 start→ ..............

패스트캠퍼스 챌린지 14일차

시청 날짜 : 11/14/2021 시청 강의 : 이분 탐색 이분 탐색 (Binary Search) 정렬이 보장되는 배열에서 기준 x를 가지고 범위를 "이분"하면서 탐색 Search for... x 가 존재하는가 x이하, 미만, 초과의 원소는 몇 개가 있는가 x 랑 가장 가까운 원소는 무엇인가 오름 차순 정렬된 배열의 특성 임의의 M번 인덱스에 있는 A [M] 이 X 보다 크다면, A [M... N] 은 전부 x 보다 크다 임의의 M번 인덱스에 있는 A [M] 이 X 보다 작다면, A [M... N] 은 전부 x 보다 작다 위 조건은 정렬이 된 상태에서만 사용 가능 Example x = 38 10 15 20 35 40 L = 1, R = 5로 잡음 L : 탐색할 가치가 있는 범위의 왼쪽 끝 인덱스 R : ..

패스트캠퍼스 챌린지 13일차

시청 날짜 : 11/13/2021 시청 강의 : 알고리즘 해결에 중요한 재귀 호출 이해 좀 늦은 감이 있지만, 재귀 호출 강의를 들어보았다. 재귀 재귀 함수란 특정 함수 내에서 자기 자신을 다시 호출하여 문제를 해결해나가는 함수이다. 문제를 해결하기 위해 원래 범위의 문제에서 더 작은 범위의 하위 문제를 먼저 해결하여 원래 문제를 해결해 나간다. Factorial 예제 그 유명한 팩토리얼 예제... 스택 오버플로우에서 그림과 코드를 가져와봤다. int factorial(int n) { if (n 1)로 주었지만, 대학에서 배울 때 Base Case를 콕 잡아서 코드 쓰는 게 더 편해졌기때문인지 몰라도, n==1일 때를 base case로 잡는 게 더 보기가 좋은 것 같다. public class Fact..