대표적인 데이터 구조8: 힙 1. 힙이란 -데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 1.1 완전 이진 트리 - 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 - 힙을 사용하는 이유 배열에 데이터를 넣고 최대값과 최소값을 찾으려면 O(n)이 걸림 이에 반해 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용 2. 힙 구조 -힙은 최대값을 구하기 위한 구조(=최대 힙) 와 최소값을 구하기 위한 구조(=최소힙) -힙은 두가지 조건을 갖고 있는 자료구조 - 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다(최대 힙 경우) 최소 힙의 경우는 ..

3. 대문자 O 표기법 빅 오표기법 또는 Big-O 표기법이라고도 부름 O (입력) -> 입력 n에 따라 결정되는 시간 복잡도 함수 O(1) ,O(logn), O(n), O(nlogn), O(n2 ) O(2n ) O(n!) 으로 표기 -> 입력 n의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있다 O(1) 단순하게 입력n에 따라 몇번 실행이 되는지를 계산하면 됩니다 - 표현식에 가장 큰 영향을 미치는 n의 단위로 표기 - n이 1이든 100이든 1000이든 10000이든 실행을 무조건 2회 실행: O(n) if n> 10: print(n) - n에 따라 n번 , n+10번 또는 3n +10 번등..

1. 삽입 정렬 (insertion sort) 란? -삽입 정렬은 두 번째 인덱스부터 시작 - 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사 -이를 key 값이 더 큰 데이터를 만날때까지 반복, 그리고 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동 직접 눈으로 보면 더 이해가 쉽다 for index in range(10, 1, -1): print (index) - 출력:10 9 8 7 6 5 4 3 2 2. 어떻게 코드로 만들까? (결국 프로그래밍으로 일반화할 수 있도록 만드는 것) - 알고리즘 연습 방법에 기반해서 단계별로 생각해봅니다. - 데이터가 두개 일 때 동작하는 삽입 정렬 알고리즘을 함수로 만들어보세요 프로그래밍 근육을 키우..

1. 인터페이스 ->일종의 추상클래스 ->추상클래스처럼 추상메서드를 갖지만 추상클래스보다 추상화 정도가 높아 ->추상클래스와는 달리 몸통 갖춘 일반 메서드 또는 멤버변수를 구성원으로 가질 수 없다 ->기본적으로 추상메서드의 모음 ->인터페이스는 구현과 상속을 모두 할 수 있다 public interface Walkable { void walk(); } ->구현부가 없으므로 인터페이스를 만든다면 반드시 구현하는 클래스를 만들어야 하며 -> 인터페이스를 구현하기로 한 클래스는 반드시 인터페이스에 명시되어 있는 추상메서드를 모두 구현해야 한다 – 만약 이를 구현하지 않으면 컴파일 에러가 발생 public class Dog implements Walkable { // ... @Override public voi..

동적 계획법 (Dynamic Programming)과 분할 정복 (Divide and Conquer) 1. 정의 - 동적계획법 (DP 라고 많이 부름) - 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 - 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 - Memoization 기법을 사용함 - Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 - 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨 - 예: 피보나치 수열 ..

기술 예상 질문 [ Programming ] 1. 프로그램이란 ? 컴퓨터가 사람 일을 할 수 있게 해주는 것 컴퓨터에 처리되는 작업의 순서를 논리적으로 명령어로 작성하는 것 2. 객체 지향 프로그래밍 언어 특징? 캡슐화 데이터와 데이터를 처리하는 함수를 하나로 묶는 것 캡슐화된 객체들은 재상용이 용이 정보 은닉 캡슐화에서 가장 중요한 개념 다른 객체에게 자신의 정보를 숨기고 자신의 연산만을 통해 접근 허용 추상화 = 모델화 불필요한 부분을 생략하고 객체의 속성 중 가장 중요한 것에만 중점을 두어 개략화 데이터의 공통된 성질을 추출해 슈퍼 클래스를 선정 상속성 이미 정의된 상위 클래스의 모든 속성과 연산을 하위 클래스가 물려받는 것 하위 클래스는 상위 클래스의 모든 속성과 연산을 자신의 클래스 내에서 다시..