☑️ To-do 이진 트리 이론 정리 전위, 중위, 후위 순회 Introduction to Algorithms 이진 트리 Week03 문제 풀이 1707 / 21606 이진 트리 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리 자식 노드의 최대 개수는 2이다. 💡 두 자식 가운데 하나 또는 둘 다 존재하지 않는 노드가 있어도 상관없다! 완전 이진 트리 루트부터 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리 마지막 레벨을 제외하고 모든 레벨에 노드를 가득채운다. 왼쪽으로 노드들이 치우친 상태 이진 검색 트리(Binary Search Tree) Field key : 키 값 left : 왼쪽 자식 right : 오른쪽 자식 p(parent) : 부모 노..

☑️ To-do 그래프 이론 기본 정리 Week03 문제 풀이 1991 / 11725 / 1707 / 2178 / 1260 / 11724 / 2606 / 5639 그래프 🆚 트리 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재 여부 루트 노드가 없음 루트 노드가 존재 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관계 모델의 종류 네트워크 모델 계층 모델 트리(tree) 관련 용어 노드(node) (=정점) 엣지(edge) (=간선) 루트(root) : 최상위 노드 리프(leaf) 단말 노드 (terminal node) 외부 노드 (external node) 리프를 제외한 노드 : 비단말 노드(non-terminal node = inter..

문제 1 소요 시간 : 30분 카테고리 : 분할 정복, 재귀 input이 잘린 걸 모르고 이상한 input으로 테스트하다가 문제가 이해가 안돼서,, 문제 이해에만 10분을 날렸다. 문제를 제대로 안읽어서 전체가 0또는 1일때도 () 안에 넣어서 출력하게끔 구현해서 10분을 삽질함 🏃‍♂️ Try 1 Fail 83% import sys input = sys.stdin.readline n = int(input()) graph, answer = [], [] dx = [0, 1, 0, 1] dy = [0, 0, 1, 1] for _ in range(n): graph.append(list(input().rstrip())) # 색이 모두 동일한 지 판단 def validation(n, x, y): color = g..

☑️ To-do 이분 탐색 이론 정리 이론 탐색 문제 접근 방식 정리 Week02 문제 풀이 11053 / 2630 / 1629 / 10830 / 6549 / 13334 이분 탐색(Binary Search) 데이터가 정렬되어있는 상태 타깃 데이터 탐색 중앙값 비교를 통한 대상 축소 방식 시간복잡도 $$O(lgN)$$ 이진 탐색 과정 1. mid 값 특정 2. if mid > target, 왼쪽 탐색 3. if mid < target, 오른쪽 탐색 4. if mid == target, 탐색 종료 파라메트릭 서치(Parametric Search) 최적화 문제(문제의 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제)를 결정 문제로 바꾸어 푸는 것 1. 결정 문제를 정의했을 때, 쉽게 풀 수 있는 경..

☑️ To-do 힙 정렬 코드 내, heapify 부분 로직 이해 스택 계산기 코드 이해 프로젝트 AWS NBP로 마이그레이션 프로젝트 자문 멘토링 소프트웨어 아키텍쳐 고민 📝 문제 특정 배열의 원소들이 정렬되는 과정을 힙과 배열로 그려 본다. 스택을 활용해 사칙 연산이 가능한 계산기를 구현하는 과정을 공부해본다. 📄 1번 문제 이진 트리 : 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조 완전 이진 트리: 좌우 균형을 이루는 이진 트리 def heap_sort(arr): def down_heap(arr, left, right): temp = arr[left] parent = left # 왼쪽 노드의 인덱스(부모 노드라고 가정) while parent < (right + 1) // 2: ..

☑️ To-do 스택 이론 정리 week02 문제 풀이 2493 / 11866 / 3190 스택 스택에서는 두 가지 연산만을 사용해서 원소의 수정을 할 수 있다. push , pop LIFO (Last In First Out) : 후입선출 스택 용어 top (위치) : 삽입과 삭제 발생 push : top에 데이터 삽입 pop : top 데이터 삭제 후 반환 peek : top 데이터 확인 활용 DFS 백트래킹 재귀 Stack 자료형 정의(Ver 1) 스택의 원래 정의대로 스택 자료형의 조작 범위를 제한하기 위해 클래스로 새로운 자료형을 정의한다. 고정된 길이의 스택으로 정의한다. 스택 구현에 필요한 메소드들 __init__() : 스택 초기화 __len__() : 스택 내 데이터 개수 확인 is_emp..

☑️ To-do Week01 테스트 복기 자바 코딩테스트 대비 스터디 진행 숫자 블록 주차 요금 계산 Week02 문제 풀이 10828 / 10773 / 9012 / 17608 / 18258 / 2164 Week01 TEST 문제 1 : 10분 단순한 완전 탐색 문제. 입력으로 주어진 숫자의 나머지 연산과 몫 연산을 반복적으로 수행. 문제 2 : 10분 모든 경우의 수를 고려해야하는 완전 탐색 문제. combinations 모듈을 사용해서 모든 조합의 경우 도출 문제 3 : 10분 dp 로 접근. 입력 데이터의 개수가 12밖에 되지 않아, 애초에 dp 테이블 전체를 만들어주는 방향으로 구현 🙁 Worst : 문제 자체를 꼼꼼히 안읽어서 조건을 캐치하지 못한 경우가 있었다. -> 난이도에 비해 시간을 많이..

프로그램 실행 이전에 어떤 일이 일어나는 가를 탐구 1-1. Information is bits + Context 소스 프로그램 : 비트들의 연속, 8 비트라 불리는 바이트로 구성되어 있다. 대부분의 컴퓨터 시스템에서는 바이트 표준으로 텍스트 문자를 표현한다. hello.c 프로그램은 일련의 byte로 저장이된다. (Figure 1.2) 각 바이트는 일부 문자와 해당하는 정수 값을 의미한다. 이후 \n 개행 문자에 의해 줄 바꿈이 일어난다. ASCII 문자로 구성된 파일을 텍스트 파일이라고 한다. 그 외에 다른 모든 파일들은 바이너리 파일이다. 시스템의 모든 정보는 모두 비트 묶음으로 표시된다. 동일한 바이트 시퀀스더라도 정수형, 실수형, 문자열, 기계어로 나타낼 수 있다. 프로그램 실행시, 각 문자열을..

☑️ To-do 정렬 알고리즘 정리하기 주요 정렬 알고리즘 안보고 코딩 해보기 ✔️ 버블 정렬 ✔️ 삽입 정렬 ✔️ 선택 정렬 ✔️ 셸 정렬 ✔️ 퀵 정렬 ✔️ 도수 정렬 CSAPP Ch 1.6 까지 정리하기 1. 버블 정렬 루프를 돌면서 인접 데이터간 대소 관계 비교 후, swap 연산 수행 루프가 하나씩 돌 때마다 오른쪽 원소가 정렬된다. 서로 이웃한 원소만 교환하므로 안정적이다. def bubble_sort(array): for i in range(len(array)): for j in range(len(array) - 1 - i): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j] return array 뒤에서 ..