Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처이진 검색 트리 골드 4 📖 문제 노드가 최대 1만개 이며, 완전 이진 트리가 아니기 때문에 한쪽으로 치우쳐진 트리가 될 수 있다.이때 최대 인덱스는 iₙ = 2 * iₙ₋₁ + 1 점화식으로 증가하며, 1만번 반복되므로 상상을 초월하는 값이 나오기 때문에  절대로 배열로 해서는 안된다.  1~10까지를 순서대로 넣게되면1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047로 약 2^11 - 1 까지 커진걸 확인할 수 있다.  즉, 최대 1만개 노드라면 2^10000 - 1 까지 커질 수 있다. 따라서 노드 객체를 만들고 좌우에 노드를 연결하는 방식으로 접근해야한다. 자바에서는 객체의 주소 값을 복사하기 때문에 . 연산자로 접근해서 객체를 생성하여 ..

✔️ 리스트(List)데이터를 순서대로 저장한 자료구조 리스트는 배열과 연결리스트를 이용해 구현할 수 있다.  리스트 추상데이터타입insert(list, pos, item) // pos 위치에 요소를 추가insert_last(list, item) // 맨 끝에 요소를 추가insert_first(list, item) // 맨 처음에 요소를 추가delete(list, pos) // pos 위치의 요소를 제거clear(list) // 리스트의 모든 요소를 제거get(list, pos) // pos 위치의 요소를 반환size() // 리스트의 길이를 반환is_empty(list) // 리스트가 비었는지 검사is_full(list) // 리스트가 꽉 찼는지 검사print_list(list) // 리스트의 모든 요..

🧫 문제 분석✔️ 출처스택 수열 실버 2 📖 문제 1~N까지의 숫자들이 오름차순으로 스택에 push될 수 있고,입력된 수열, 여기서는[4 3 6 8 7 5 2 1] 이라는 수열을 만들기 위해 스택이 해야하는 연산을 출력하는 문제이다.push : + pop : - 우선 먼저 수열의 맨 처음인 4를 놓기 위해서는 1~4까지 스택에 push 후 1번 pop한다. 그럼 스택에는 1 2 3 이 남게 된다. 그다음은 3이므로 pop 한 번 한다.다음 6이므로 5 6 을 push하고 pop 하여 6을 빼낸다. 즉 수열의 각 순서에 따른 수만큼 push하고 top의 수가 현재 순서의 수면 pop하고 아니라면 NO를 출력하고 중단한다.push는 현재 까지 넣은 수에 따라서 진행한다. 현재까지 넣은 수보다 큰 수가 오..

✔️ 큐(queue)먼저 들어온 데이터가 먼저 나가는 자료구조선입 후출 : FIFO First-In Frist-Out  예시 : 식당에서 먼저 주문한 사람이 먼저 음식을 받는다. 큐에는 선형 큐와 원형 큐가 있다. 선형 큐는 배열처럼 일자 데이터 구조이고 원형 큐는 처음과 끝이 연결되어있는 데이터 구조이다.  ❗ 선형 큐의 문제점    dequeue()로 요소를 꺼내면 맨 앞자리가 비어있기 때문에 이를 채우기위해 뒤의 모든 요소들을 한 칸씩 앞으로 땡겨야    하기에 효율적이지 않다.   프로그램 상에서 어떻게 원형 큐를 구현할까?우리는 아주 좋은 %(나머지 연산)을 알고 있다. (마지막인덱스 + 1) 자리로 인덱싱 접근이 오면 % (큐의 크기) 연산을 해주어서 다시 맨 앞자리에 접근하게 한다. 이를 통..

같은 자료형의 데이터를 쌓아 놓는 자료구조후입 선출 : LIFO Last-In Frist-Out  함수 호출 역시 메모리 스택에 쌓이는 구조이다. func1() // 호출되어 쌓임main() // func1() 호출 스택 추상 데이터 타입create(size) // 최대 크기가 size인 공백 스택을 생성is_full(s) // if (스택의 원소수 == size) return TRUE; 아니라면 return False;is_empty(s) // if(스택의 원소수 == 0) return TRUE; 아니라면 return False;push(s, item) // 스택이 풀 상태이면 에러를 반환, 아니라면 스택 맨 위에 item 추가pop(s) // 스택이 비어있다면 에러 반환, 아니라면 맨 위 원소를 꺼낸..

✔️ 배열같은 자료형의 변수들이 연속된 메모리 공간을 차지하는 자료구조 인덱스와 인덱스에 대응하는 데이터들로 이루어진 자료구조이다.  int arr[5]; // 배열 선언arr[0] = 10; // 0번째 인덱스에 접근하여 값을 바꿈, set 연산int value = arr[0] // 0번째 인덱스에 접근하여 값을 가져옴, get 연산int arr[] = {1, 2, 3, 4}; // 배열 바로 초기화  1차원 배열 :  base(주소값) + n * sizeof(자료형) 2차원 배열 :  base(주소값) + (i * 열의 개수 + j )* sizeof(자료형)       // i : 행,  j : 열 이러한 형식으로 실질적인 배열 인덱스에 접근한다. 응용 : 행렬 (matrix)2차원 배열을 이용하여 ..