목록전체 글 (67)
ㅇTL
Merge sort A. concept : 두 sorted list를 합친다. 각각 리스트의 맨첨 애를 비교해서 작은 애를 새로운 리스트에 넣는 방식 -> 리스트를 1개 될때까지 다 절반으로 divide 한 담에 차례로 merge 합니다 처음에는 sorted안되어있으니까 다 1개인걸로 쪼개놓으면 sorted니까 쪼개서 합치는 것!! B. Code C. Analysis : O(nlogn) !! - (worst average 둘다) T(1)=1, T(n)=2T(n/2)+n 알고리즘 정리한거 참고 Quick Sort = 분할 정복 divide-and conquer 알고리즘. (그대로 해결할 수 없는 문제를 작은문제로 분할하여 문제 해결함) 1. 피벗 하나를 정해서 앞에는 피벗보다 작은걸 배치, 뒤에는 피벗보다..
프로세스 메모리를 할당받아 실행중인 프로그램. 운영체제로부터 실행에 필요한 메모리를 할당받아 어플리케이션의 코드를 실행 Thread - 하나의 프로세스 내부에서 독립적으로 실행되는 작업 단위. 프로세스 내에서 실행되는 흐름의 단위. - 프로세스 내부에 thread가 한개 -> 단일 스레드. single thread / 두개 이상 -> multi Thread - 서로 독립적. 오류발생해도 서로 영향x - 하나의 스레드 내부에서 작업 처리 단계는 순차적! -JVM에 의해 하나의 프로세스 발생 -> 메인 쓰레드가 main함수 실행하면서 어플리케이션 실행됨 여기에 다른 thread가 없을 경우 single thread 이고, 메인 스레드 내에서 다른 thread들을 만들게 되면 multiThread되는거임 (m..
Concept * • Hash : 많은 양의 데이터들을 그보다 작은 크기의 테이블로 대응시켜 저장할 수 있는 알고리즘 데이터를 특정 위치에 쌍으로 저장하는 것인듯! 해시란 데이터를 다루는 기법 중에 하나로 검색과 저장이 아주 빠르게 진행됩니다! 데이터를 검색할 때 사용할 key와 실제 데이터의 값이 (value가) 한 쌍으로 존재하고, key값이 배열의 인덱스로 변환되기 때문에 검색과 저장의 평균적인 시간 복잡도가 O(1)에 수렴하게 됩니다. hash function h(k)을 사용하여 key를 주소로 mapping해주어 빠르게 searching이 가능하도록 하는 방법이다. hashing은 key와 주소가 직접 연결된 구조가 아니라 hash function을 통한 key와 임의의 주소로 연결되는 구조이다..
Exception = 프로그램의 정상적인 수행 도중에 발생할 수 있는 오류 ! 이거 발생 -> 프로그램 종료 (exception 발생 - 프로그램이 이 exception catch를 실패하면 충돌이 일어나서 프로그램 종료! ) 이거 handling -> 프로그램 종료되지 않고 실행이 유지되도록 할 수 ㅇ handling 방안 1. try-catch 문 try{ //예외가 발생할 것 같은 코드 //exception이 발생하면 try안의 남은 코드들은 건너뛰어짐 } catch(Exception e){ //예외가 발생할 경우 어떻게 할 것인지 } finally{ //항상 실행되는 부분 } 예외 발생되는 말든 결국 이부분 실행 후에는 try-catch블록 이후의 코드들을 실행한다~~^^ -여러개의 catch 블..
정의 : 모든 노드에 대해서 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이차가 1이하는 BST (이진탐색트리) 리프노드의 height=0 균형도 값 = 좌측서브트리의 높이-우측서브트리의 높이. 이게 1보다 커지면 회전을 한다 *아무것도 없는것 : -1로 가정함 ! (NULL=-1) 이 값이 양수 -> 왼쪽 치우침 / 음수 -> 오른쪽 치우침 높이 결정법 MAX(좌 서브트리높이, 우서브트리높이) + 1 (둘중 더 큰 값 + 1 이 높이가 됩니당) LL: 왼쪽으로 치우쳐있으므로 오른쪽으로 회전함 RR: 오른쪽으로 치우쳐 있으므로 왼쪽으로 회전 (이건 반대로 회전) (얘넨 그대로 회전) LR : 왼쪽으로 치우쳤는데 왼쪽노드의 오른쪽서브트리가 더 무거울때 함 (왼쪽무겁-의 오른쪽무겁 이라서 LR) ..
Concepts ; Heap 이란 정의 : 여러개의 값들 중에서 가장 큰 값 / 가장 작은 값을 빠르게 탐색하도록 만들어진 binary tree 자료구조 • complete binary tree (완전 이진 트리) 임 ; 맨 아래 레벨 빼고 다 채워져있고, 맨 아래 레벨애들은 왼쪽부터 채워저 있는 것 -> 높이가 h일때 총 노드 개수는 2^h ~ 2^(h+1) -1 가 존재한당 (h-1 높이에서는 2^(h-1) -1 ) ( full : 자식이 0개 또는 2개인 것 ) • 부모노드의 키가 자식보다 같거나 크다 (MAX heap) - root 가 젤 큼 ( MIN heap은 자식이 더 크겠지용 ) 기능 • push : 해당 값을 완전 이진트리가 되도록 젤 왼쪽 자식 노드에 넣는다 그리고 부모값과 비교해서 계..
드뎌 내가 교환학생을 간다 예전부터 기대하고 기대했던 흑흑 대학생활을 거의 한게 없는 내가 꼭 해야하는 건 이 교환학생이었다 그런데 내가 드뎌 간다 ~~ to New York 학기는 8/25 - 12/22 인거같고 8/19일까지 도착해야 하는 것 같다 다시 영어공부 열심히 하장 ㅎㅎ
* OOP 의 세가지 중요 특징 - encapsulation - inheritance - polymorphism ! (다형성) Polymorphism = 하나의 객체가 여러 가지 타입을 가질 수 있는 것을 의미함 ! -> 부모 class type에 자식 클래스타입의 인스턴스 참조할 수 ㅇ ! = late binding 매커니즘을 통해 하나의 메소드 이름에 많은 의미를 연결하는 기능 ! -> late binding / dynamic binding 이라는 특별한 매커니즘을 통해 이루어진다 * binding = 메소드 호출과 메소드 정의를 연결하는 과정 ! 어떤 함수 부를지 결정하는 것 ( 프로그래머가 코딩을 해서 컴파일을 하게 되면 프로그래머가 값을 변경할 수 없는 상태가 되는 것) ♡ early(stat..
** 갑자기 포인터 이해하기 그냥 포인터 = 변수의 주소를 저장. -> 해당 변수의 값 변경 가능 ! (그걸 위함) 포인터의 포인터 = 변수의 주소를 담고있는 포인터변수의 주소를 저장 -> 포인터변수안의 값 접근, 변경 가능 ! 포인터 변수안에는 변수의 주소가 저장되어 있음 -> 주소 변경 가능 = 해당 포인터 변수가 다른 주소를 가리키게 할 수 있다 ! -> 실습 스택 코드에서 push할 때 top노드의 이중포인터 사용하는것은 top은 첫번째 노드의 주소 가지고 있는데 push하면 첫번째 노드가 달라지므로 top이 다른 주소를 저장해야댐 !! -> 걍 top의 값을 변경해줘야하니까 *한번 더붙임 !! -> 걍 *을 붙이는 것은 해당 변수 내부의 값을 바꿔주기 위해서 하나 더 붙여준다고 생각하자 !! (..