코린이의 소소한 공부노트

1. 개념정리 1) 한쪽에서만 데이터 삽입과 삭제가 가능한 구조 2) LIFO(Last In First Out, 마지막 삽입 데이터가 먼저 삭제됨) 3) java.util 패키지에 Stack 클래스가 있다. 2. 구현 코드 class ArrayStack{ // int[]로 구현하는 스택 protected final int defCap = 10; // 스택의 용량 protected int[] stack; // 스택의 요소를 담을 배열 protected int topIndex = -1; // 스택의 가장 마지막 인덱스 public ArrayStack() { // 기본 생성자 stack = new int[defCap]; } public ArrayStack(int maxSize) { // 스택의 크기를 지정한 ..

1. 개념정리 1) 같은 타입인 여러 개의 변수를 하나로 묶어놓은 것 - 타입은 기본형, 참조형 가리지 않는다. - 물리적으로(하드디스크) 연속되지 않은 공간에 있어도 상관없다.. - java.util 패키지에 LinkedList 클래스가 있다. 2) 리스트의 요소를 노드(node)라고 부르며, 각 노드에는 값(value)과 다음 노드의 주소가 저장된 링크(next)가 있다. - 특히, 맨 앞 노드를 head, 맨 뒤 노드를 tail이라고 부른다. - 마지막 노드라면 next == null - 데이터가 추가되면 연결만 해주면 되기 때문에, 연결 리스트의 최대 크기는 정해져 있지 않다. 3) 이중 연결 리스트는 단순 연결 리스트에서 이전 노드의 주소가 저장된 링크(previous)가 추가된 것이다. - 맨..

1. 개념정리 1) 같은 타입인 여러 개의 변수를 하나로 묶어놓은 것 - 타입은 기본형, 참조형 가리지 않는다. - 물리적으로(하드디스크) 연속된 공간에 저장되어있다. - 자바는 참조변수에 배열의 시작주소를 저장해서 이용하고 있다. 2) 배열의 크기는 배열을 이루고 있는 요소의 개수와 같다. - 한번 선언된 배열의 크기는 바꿀 수 없다. - 크기를 늘리고싶다면 새 배열을 만들어 반복문이나 System.arraycopy() 등을 이용해 요소를 복사해야 한다. - java.util 패키지에 있는 ArrayList 클래스를 이용해서 유연한 배열을 사용할 수 있다. 3) 배열이 다른 배열의 요소가 될 수 있다. - 1차원 배열의 요소가 1차원 배열이라면 그 배열은 2차원 배열이 된다. 4) 인덱스(위치)는 0번..

1. 단순구조(기본구조): 언어에서 기본으로 제공하는 타입 2. 선형구조: 데이터가 연속적으로 붙어있거나 순서가 정해져 있는 구조 1) 리스트(배열, array): 데이터가 연속적으로 붙어 있는 구조 2) 연결 리스트(linked list): 불연속적인 데이터가 링크를 통해 연결되어 있는 구조 - 단순 연결 리스트: 한 데이터가 다음 데이터(next)를 가리키고 있는 구조. 순서가 있다. - 이중 연결 리스트(doubly linked list): 연결 리스트에서 이전 데이터(previous)를 가리키는 링크를 추가한 구조 - 원형 연결 리스트(circular linked list): 이중 연결 리스트에서 맨 앞 데이터와 맨 뒤 데이터를 연결하는 링크를 추가한 구조 3) 스택(stack): 한쪽에서만 데이..

1. Problem - 이진 트리에서 원하는 값을 찾아보자. // 이진 트리란? 1) 값(key)을 가진 노드들의 모임 2) 노드는 자식 노드를 왼쪽 하나(left subtree), 오른쪽 하나(right subtree)를 가질 수 있다. 3) 왼쪽 자식의 노드 값은 부모 노드(root)보다 작거나 같고, 오른쪽 자식의 노드 값은 크거나 같다. 2. Input 1) 이진 트리를 가리키는 포인터 tree 2) 찾아야 할 값 keyin 3. Output 1) 찾아야 할 값이 있는 노드를 가리키는 포인터 p 4. PseudoCode void search(node_pointer tree, keytype keyin, node_pointer p){ boolean found; p = tree; found = fals..

1. Problem - 여러 개의 노드가 연결되어 있는 그래프가 있다. 노드의 연결선에는 그 선을 지나는데 필요한 비용(가중치)이 있다. 모든 노드에 대해 다른 노드로 가는 데 필요한 가장 적은 비용(지름길)을 계산해보자. 2. Input 1) weighted graph의 vertex 수 n 2) 그래프를 나타내는 2차원 배열 W (1-indexed) 3. Output 1) 지름길을 나타내는 2차원 배열 D (1-indexed) - D[i][j]는 i번째 vertex에서 j번째 vertex로 가는 지름길의 길이를 나타낸다. 4. PseudoCode void floyd(int n, const number W[][], number D[][]){ index i, j, k; D = W; for(k=1 ; k

1. Problem - nCk를 계산해보자. 2. Input 1) 음이 아닌 정수 n 2) 음이 아닌 정수 k - 이때 k

1. Problem - nCk를 계산해보자. 2. Input 1) 음이 아닌 정수 n 2) 음이 아닌 정수 k - 이때 k

1. 전략: bottom-up approach 1) 문제의 가장 작은 단위부터 사용할 수 있는 반복문을 작성한다. 2) 가장 작은 문제부터 차례대로 풀어나간다. 3) 저장된 결과를 재사용한다. 3) divide and conquer와의 공통점 - 문제를 작게 쪼개서 해결한다. 4) divide and conquer와의 차이점 - DAC의 경우 top-down 형식이기 때문에 중복 계산이 여러 개 생겨날 수 있다. - DP는 bottom-up 형식이기 때문에 중복 계산이 생기지 않는다. 2. 예시 - binomial coefficient - Floyd's algorithm for shortest paths - traveling salesperson problem - chained matrix multipl..

[HTML이란?] 1. HyperText Markup Language 2. 웹 사이트의 모습을 기술하기 위한 언어 3. 문서의 구조나 서식을 태그를 이용해 표현한다. 4. 태그는 로 시작하면 로 끝맺는다. 가장 기본이 되는 태그 몇 가지만 소개하고자 한다. [기본 구조 태그] Hello, world! 1. : 어떤 마크업 언어를 썼는지 표시하는 태그. HTML은 아래처럼 쓰면 된다. 2. : HTML이 작용하는 범위를 지정하는 태그로 위의 DTD를 제외한 전체를 이 태그로 둘러싼다. 3. : HTML 문서의 속성 범위를 지정하기 위한 태그이다. 이 태그 안에 타이틀이나 메타 태그 등을 넣는다. 4. : HTML 문서의 본문 범위를 지정하기 위한 태그이다. 초등학생때 배울때는 body 태그에 여러 속성들을..