코딩 일기장

문제 링크 : https://www.acmicpc.net/problem/2146 문제 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다는 생각을 하게 되었다. 그래서 그는, 생색내는 식으로 한 섬과 다른 섬을 잇는 다리 하나만을 만들기로 하였고, 그 또한 다리를 가장 짧게 하여 돈을 아끼려 하였다. 이 나라는 N×N크기의 이차원 평면상에 존재한다. 이 나라는 여러 섬으로 이루어져 있으며, 섬이란 동서남북으로 육지가 붙어있는 덩어리를 말한다. 다음은 세 개의 섬으로 이루어진 나라의 지도이다. 위의 그림에서 색이 있는 부분이 육지이고, 색이 없는 부분이 바다이다. 이 바다..

메모이제이션 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술, 동적 계획법의 핵심 추가적인 메모리 공간이 필요. 재귀 함수 호출로 인한 시스템 호출 스택을 사용, 실행 속도 저하 또는 오버플로우 발생 1. 중복 부분문제 구조 DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해를 이용하여 순환적으로 큰 문제를 해결한다. 순환적인 관계를 명시적으로 표현하기 위해서 동적 계획법에서는 일반적으로 수학적 도구인 점화식을 사용한다. DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에 필요하게 되는데 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 어떤 저장 공간..

개념 다익스트라 알고리즘은 그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘. 이 과정에서 도착 정점 뿐만 아니라 모든 다른 정점까지 최단 경로로 방문하여 각 정점까지의 최단 경로로 모두 찾는다. 동작 인접 행렬로 구현하는 방법 출발 노드와 도착 노드를 설정한다. 최단 거리 테이블을 초기화 한다. 현재 위치한 노드의 인접 노드 중 방문하지 않은 노드를 구별하고, 방문하지 않은 노드 중 거리가 가장 짧은 노드를 선택한다. 그 노드를 방문 처리한다. 해당 노드를 거쳐 다른 노드로 넘어가는 간선 비용을 계산해 최단 거리 테이블을 갱신한다. 1 ~ 4 과정을 반복한다. // N: 정점 개수, V: 간선 개수, start: 출발 정점, end: 도착 정점, weight: 비용 // map: 인접..

그래프에서 최소 비용 문제 모든 정점을 연결하는 간선들의 가중치 합이 최소가 되는 트리 두 정점 사이의 최소 비용의 경로 찾기 신장 트리 n개의 정점으로 이루어진 무향 그래프에서 n개의 정점와 n-1개의 간선으로 이루어진 트리 최소 신장 트리 (Minimum Spanning Tree) 무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장트리 1. KRUSKAL Algorithm 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴 → 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 n-1 개의 간선이 선택될 때까지 2번 반복 MST_KRUSKAL(G, w) for vertex v in G.V // G.V : 그래프의 정점..

1. 순열 서로 다른 것들 중 몇 개를 뽑아서 한 줄로 나열하는 것 nPr nPr = n * (n-1) * (n-2) * ... * (n-r+1) nPn = n! n! = n * (n-1) * (n-2) * ... * 2 * 1 다수의 알고리즘 문제들은 순서화된 요소들의 집합에서 최선의 방법을 찾는 것과 관련 N개의 요소들에 대해서 n! 개의 순열들이 존재한다. n>12 인 경우, 시간 복잡도 폭발적으로 증가 반복문을 통한 순열 생성 for i from 1 to 3 for j from 1 to 3 if j != i then for k from 1 to 3 if k != i and k != j then print i, j ,k end if end for end if end for end for public..

1. Collection Framework 자료구조 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미 데이터 값의 모임, 또 데이터 간의 관계, 그리고 데이터에 적용할 수 있는 함수나 명령을 의미 배열 가장 기본적인 자료구조 homogeneous collection: 동일한 데이터 타입만 관리 가능 타입이 다른 객체를 관리하기 위해서는 매번 다른 배열 필요 Polymorphism Object를 이용하면 모든 객체 참조 가능 → Collection Framework 담을 때는 편리하지만 빼낼 때는 Object로만 가져올 수 있음 런타임에 실제 객체를 타입 확인 후 사용해야 하는 번거로움 Generic을 이용한 타입 한정 컴파일 타임에 저장하려는 타입 제한 → 형변환의 ..

1. abstract class 정의 자손 클래스에서 반드시 재정의해서 사용되기 때문에 조상의 구현이 무의미한 메서드 메서드의 선언부만 남기고 구현부는 세미콜론으로 대체 구현부가 없다는 의미로 abstract키워드를 메서드 선언부에 추가 객체를 생성할 수 없는 클래스라는 의미로 클래스 선언부에 abstact를 추가한다. abstract 클래스는 상속 전용의 클래스 클래스에 구현부가 없는 메석드가 있으므로 객체를 생성할 수 없다. 하지만 상위클래스 타입으로써 자식을 참조할 수는 있다. 조상 클래스에서 상속 받은 abstract 메서드를 재정의 하지 않은 경우 클래스 내부에 abstract 메서드가 있는 상황이므로 자식 클래스는 abstract 클래스로 선언되어야 함 추상 클래스를 사용하는 이유 abstra..

1. 상속 객체지향 언어의 특징 OOP is A.P.I.E 특성 내용 Abstraction(추상화) 현실의 객체를 추상화 해서 클래스를 구성한다. Polymorphism(다형성) 하나의 객체를 여러 가지 타입으로 참조할 수 있다. Inheritance(상속) 부모 클래스의 자산을 물려받아 자식을 정의함으로 코드의 재사용이 가능하다 Encapsulation(데이터 은닉과 보호) 데이터를 외부에 직접 노출시키지 않고 메소드를 이용해 보호할 수 있다. 상속(Inhritance: Java Is A PIE) 기존 클래스의 자산(멤버)을 자식 클래스에서 재사용하기 위한 것 부모의 생성자와 초기화 블록은 상속하지 않는다 기존 클래스의 멤버를 물려 받기 때문에 코드의 절감 부모의 코드를 변경하면 모든 자식들에게도 적용..

1. 객체지향 프로그래밍이란? Object Oriented Programming 객체란? 주체가 아닌 것, 주체가 활용하는것 우리 주변에 있는 모든 것으로 프로그래밍의 대상 객체지향 프로그래밍 주변의 많은 것들을 객체화 해서 프로그래밍 하는 것 객체지향 프로그래밍의 장점 블록 형태의 모듈화된 프로그래밍 신뢰성 높은 프로그래밍이 가능하다 추가/수정/삭제가 용이하다 재 사용성이 높다 2. 클래스 클래스 객체를 정의해 놓은 것, 즉 객체의 설계도 , 틀 클래스는 직접 사용할 수 없고 직접 사용되는 개체를 만들기 위한 틀을 제공할 뿐 객체 클래스를 데이터 타입으로 메모리에 생성된 것 객체들은 모두 클래스에서 선언된 속성을 가짐 객체 별로 다른 상태 값을 가짐 객체 생성과 메모리 JVM의 메모리 구조 클래스 영역..