SCodaily_코딩_데일리 SCodaily_코딩_데일리

Binary Search Tree란? 이진 탐색 트리 Binary Tree : 오직 두 개의 자식을 가지는 tree구조 Binary Search Tree : 부모의 왼쪽 자식은 부모의 데이터값보다 작은 값을 가짐, 오른쪽 자식은 크거나 같은 값을 가짐 Binary Search Tree의 장점 1. 이진 탐색의 장점 -> 탐색 시간복잡도 O(logN), 삽입 삭제 불가능 2. 연결리스트의 장점 -> 데이터의 삽입 삭제 가능 Binary Search Tree의 시간복잡도 데이터 삽입, 삭제, 탐색 -> O(logN) Binary Search Tree의 기본 구성 요소 - Attribution ( 속성 ) Node 1. 데이터 값 2. left child, right child class Node: def _..

Linked List란? - Linked List란? 배열 -> 연결된 공간에 데이터 나열 Linked List -> 각각의 공간에 존재하는 데이터를 연결해서 관리 - Linked List의 구성 요소 및 용어 노드(Node) : 데이터 저장 단위 -> 데이터 값, 포인터로 구성 -> 포인터(Pointer) : 노드 끼리의 연결 정보 저장 헤드(Head) : Linked List의 시작을 의미, 데이터 값으로 NULL을 가짐 Linked List 기본 구성 요소 구현 - Attribution ( 속성 ) Linked List의 구성 요소 : head, node, pointer Node의 구성 요소 : value(값), pointer -> Node 클래스 생성 -> Linked List 클래스 생성 -> ..

객체지향 VS 절차지향 - 절차 지향 ( Procedural Programming ) -> C언어 Top Down 방식 ( 순차적인 처리 ) 프로그램 전체가 유기적으로 연결 장점 : 실행속도가 빠름 단점 : 유지보수가 어려움, 디버깅이 어려움 - 객체 지향 ( Object Oriented Programming ) -> C++, Java, Python 실제 세계를 모델링하여 개발 속성(Attribution)과 행동(Method)로 이루어짐 3대 특성 1. 추상화 : 공통성과 본질을 모아 추출 2. 상속 : 상위 클래스의 속성과 method를 재사용할 수 있음 3. 다형성 : 하나의 객체가 다양한 속성과 method를 가질 수 있음 4. 캡슐화 : 연관된 속성과 기능을 하나의 캡슐로 만들어 외부로부터 데이터..

컴파일러(Compiler) VS 인터프리터(Interpreter) - C언어 ( Compiler ) 고급 프로그래밍 언어(C) -> 어셈블리어 -> 기계어 소스 코드 -> 컴파일러(컴파일 타임) -> 어셈블러 -> 실행파일(런타임) -> 실행 실행과정에서 메모리 배정하고 싶은 경우 : 동적할당 사용 (C언어 : malloc, free / C++ : new, delete) - Python ( Interpreter ) 한 줄씩 실행, 메모리를 한 줄마다 할당. 변수와 메모리 데이터(변수) : 주소와 메모리(값)이 존재 고급 프로그래밍 언어에서 변수의 이름은 데이터의 주소를 쉽게 보기 위함 -> 결과적으로 변수의 주소값이 중요 파이썬에서의 변수할당 ( Mutable VS Immutable ) - Mutable..

백트래킹 기본개념 탐색 알고리즘의 일종, 모든 경우의 수를 고려하는 알고리즘 트리 탐색 알고리즘 주로 DFS 사용 예시1) 조합(Combination) 길이가 n인 주어진 수열에서 k개를 뽑는 경우의 수 재귀 함수, 백트래킹을 통해 k개만 정확히 선택하며 이미 선택된 경우는 제거 내장 함수 itertools의 combination 함수 사용 # coding = utf-8 from itertools import combinations for choice in combinations([1,2,3,4],2) : print(choice) # 결과 (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4) 재귀 함수를 사용하여 조합을 구현 # coding = utf-8 choice = list()..

Divide and Conquer Top-Down 방식의 알고리즘 Divide : 가장 상위의 문제를 2개의 하위 단계의 문제로 나눈다. Conquer : 최적의 부분 구조까지 문제를 나눈 후 해결한다. Combine : 하위 문제에 대한 결과를 조합한다. 예시1) MergeSort(병합정렬) 기존 Selection sort, Bubble sort, Insertion sort의 시간복잡도 O(N^2) Merge sort의 시간복잡도 O(NlogN) 병합 정렬의 알고리즘 및 분할 정복 개념 적용 데이터 크기가 2 이상일 때, 데이터를 두 집합으로 분할 ( Divide ) 데이터의 크기가 0 또는 1이면 정렬된 데이터 데이터를 모두 분할한 후, 데이터 집합들을 병합 ( Combine ) 병합 과정에서 데이터..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net Silver1) 2178.미로 탐색 그래프 탐색, BFS, DFS BFS, DFS 문제도 많이 풀어봤지만, 다시 한번 기본적인 문제로 정리하고 싶어 풀어봤다. DFS와 BFS는 한 번 이해하면 쉽게 다가오지만 막상 코드를 직접 짜려하면 잘 떠오르지 않을 수 있다. 또한, 문제마다 주어진 형식에 맞춰 조정할 필요도 있기 때문에 잘 다져놓는 것이 좋다. 해당 문제는 가장 기본적인 미로찾기이다. 보통 BFS가 DFS보다 퍼포먼스가 좋..

https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net Gold5) 2293.동전 1 다이나믹 프로그래밍 다이나믹 프로그래밍 풀이가 계속 감이 잡히지 않아 아예 다이나믹 프로그래밍 카테고리에 들어가서 문제들을 풀었다. 골드5지만 다이나믹 프로그래밍은 난이도 체감이 천차만별이다. 기본적인 동전 문제 구성에 애초에 카테고리로 들어간 문제라 처음부터 DP로 접근했다. 사실 문제를 낯선 상황에서 만난다면 DP를 떠올리는 것부터가 문제이다. DP를 생각하고 접근..