코딩 일기장

문제 링크 :https://www.acmicpc.net/problem/1082 1082번: 방 번호 스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해 www.acmicpc.net 문제 스타트링크가 입주한 사무실은 방 번호를 직접 정할 수 있다. 방 번호를 정하려면 1층 문방구에서 파는 숫자를 구매해야 한다. 숫자를 구매하기 위해 준비한 금액은 M원이고, M원을 모두 사용해야 한다. 문방구에서 파는 숫자는 0부터 N-1까지이고, 각 숫자 i의 가격은 Pi이다. 문방구에서는 같은 숫자를 여러 개 구매할 수 있고, 문방구는 매우 많은 재고를 보유하고 있기 때문에, 항상 ..

문제 링크 :https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만들어 보려고 한다. 화면에 있는 이모티콘을 모두 복사해서 클립보드에 저장한다. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다. 화면에 있는 이모티콘 중 하나를 삭제한다. 모든 연산은 1초..

문제 링크 : https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 문제 지구 온난화로 인하여 북극의 빙산이 녹고 있다. 빙산을 그림 1과 같이 2차원 배열에 표시한다고 하자. 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장된다. 빙산 이외의 바다에 해당되는 칸에는 0이 저장된다. 그림 1에서 빈칸은 모두 0으로 채워져 있다고 생각한다. 빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 줄어들기 때문에, 배열에서 빙산의 각..

메모이제이션 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술, 동적 계획법의 핵심 추가적인 메모리 공간이 필요. 재귀 함수 호출로 인한 시스템 호출 스택을 사용, 실행 속도 저하 또는 오버플로우 발생 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. Exception Handling 에러와 예외 어떤 원인에 의해 오동작 하거나 비정상적으로 종료되는 경우 심각도에 따른 분류 Error 메모리 부족, stack overflow와 같이 일단 발생하면 복구할 수 없는 상황 프로그램의 비 정상적 종료를 막을 수 없음 → 디버깅 필요 Exception 읽으려는 파일이 없거나 네트워크 연결이 안되는 등 수습될 수 있는 비교적 상태가 약한 것들 프로그램 코드에 의해 수습될 수 있는 상황 exception handling(예외 처리)란 예외 발생시 프로그램의 비 정삭적 종료를 막고 정상적인 실행 상태를 유지하는 것 예외 클래스의 계층 checked exception 예외에 대한 대처 코드가 없으면 컴파일이 진행되지 않음 unchecked exception (R..

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