문제 [Gold I] 다리 만들기 2 - 17472 문제 설명 섬으로 이루어진 나라가 있고, 모든 섬을 다리로 연결하려고 한다. 이 나라의 지도는 N×M 크기의 이차원 격자로 나타낼 수 있고, 격자의 각 칸은 땅이거나 바다이다. 섬은 연결된 땅이 상하좌우로 붙어있는 덩어리를 말하고, 아래 그림은 네 개의 섬으로 이루어진 나라이다. 색칠되어있는 칸은 땅이다. 나라의 정보가 주어졌을 때, 모든 섬을 연결하는 다리 길이의 최솟값을 구해보자. 입력 첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 지도의 정보가 주어진다. 각 줄은 M개의 수로 이루어져 있으며, 수는 0 또는 1이다. 0은 바다, 1은 땅을 의미한다 출력 모든 섬을 연결하는 다리 길이의 최솟값을 출력한다. 모든..

최소 신장 트리 그래프에서 모든 노드를 연결할 때 사용된 Edge들의 가중치의 합을 최소로 하는 트리이다. 특징 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않는다. N개의 노드가 있을 때 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1개이다. 핵심 이론 모든 Edge들을 '가중치'를 기준으로 오름차순 정렬 후, 가중치가 낮은 Edge부터 연결한다. 이때 사이클이 형성되지 않을 때만 연결한다. 1. Edge 리스트로 그래프를 구현하고 유니온 파인드 배열 초기화하기 그래프를 Edge 중심 형태로 Edge 리스트로 저장한다. edge class는 시작 노드, 끝 노드, 가중치로 구성된다. 사이클 여부를 확인하기 위해 유니온 파인드 배열(parent)를 인덱스의 값으로 초기화..

생성자 생성자의 특징 • 메소드이다. • 객체당 한 번 호출된다. • 리턴타입을 지정할 수 없다 • 목적은 객체의 초기화이다. 생성자는 객체가 생성될 때 반드시 호출된다. • 개발자가 생성자를 생성하지 않았다면 컴파일러가 자동으로 기본 생성자 삽입한다. 기본 생성자 매개 변수 없고 아무 작업 없이 단순 리턴하는 생성자 컴파일러가 만든다 하지만 개발자가 클래스 생성자를 하나라도 작성한 경우 컴파일로는 기본 생성자를 만들지 않는다. this 레퍼런스 ▶︎ this 객체 자신에 대한 레퍼런스 ▶︎ this() 클래스 내의 다른 생성자 호출 생성자 내에서만 사용가능 반드시 생성자 코드의 제일 처음에 수행 public class Book{ String title; String author; public Book(..

벨만-포드 알고리즘 벨만-포드 알고리즘 한 정점에서 다른 모든 정점간의 최단 거리를 구하는 알고리즘이다. 특징 • 음의 간선을 포함하는 그래프에서 사용한다. • 음의 사이클의 존재여부를 판단할 수 있다. 시간 복잡도 • O(VE) - V : 정점의 개수 E : 간선의 개수 주요 아이디어 노드의 수가 N개일 때 N-1번 동안 모든 Edge를 탐색하면서 최단 경로를 구한다. 그러므로 시간 복잡도가 O(VE)이다. 아무리 멀리 떨어진 노드라고 할지라도 N-1개의 간선을 지나면 어떠한 노드라도 도달할 수 있다. 그래서 벨만 포드 알고리즘은 보통 N-1번만큼 반복하여 최단경로를 알아낸다. 또한 벨만 포드 알고리즘은 주로 음의 사이클 존재 여부를 판단할 때 더 많이 쓰인다. 이때는 N번만큼 반복하며 N번일 때 최단..

객체 지향언어 객체 세상 모든 것이 객체로 이루어진다. (TV, 냉장고, 컴퓨터, 사람...) 실세계 객체의 특징 객체마다 고유한 특성(state)와 행동(behavior)를 가짐 다른 객체들과 정보를 주고 받는 등, 상호작용하면서 존재 객체 지향 언어의 목적 ▶︎ 소프트웨어 생산성 향상 컴퓨터 산업 발전에 따라 소프트웨어 생명주기가 단축됨 상속, 다형성, 객체, 캡슐화 등 소프트웨어 재사용을 위한 여러 장치가 내장됨 ➞ 재사용, 부분 수정 용이. 다시 만들 필요 없음 ▶︎ 실세게에 대한 쉬운 모델링 실세계에서 발생하는 일을 프로그래밍하기 때문에, 절차나 과정보다 물체들의 상호작용으로 묘사하는 것이 용이 절차 지향 프로그래밍과 객체 지향 프로그래밍 ▶︎ 절차 지향 프로그래밍 작업 순서 표현 작업을 함수로..

문제 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 핵심 풀이 이 문제는 건설해야 할 건물(W)을 지을 수 있는 최소시간을 구하는 문제이다. 건물을 짓는 순서가 있고 싸이클이 없는 그래프이므로 '위상 정렬'을 이용한다. 더 고려해야 하는 점은 건물을 짓는데 걸리는 시간이 있기 때문에, 선수 건물이 여러 개라면 그 중 가장 오래 걸리는 건물 시간에 맞춰야 한다. 즉 A -> C , B -> C라는 선후 관계가 있을 때 A 건물을 지을 때 30, B 건물을 짓는데 50이라면 50분 있다가 C건물을 지어야한..

배열 배열은 인덱스(index)와인덱스에 대응하는 데이터들로 이루어진 연속적인 자료 구조로서, 같은 종류의 데이터들이 순차적으로 저장된다. 자바에서의 배열 생성은 C/C++와 달리 2단계로 이루어진다. 배열에 대한 레퍼런스 변수 선언 배열 생성 - 배열의 저장공간 할당 1. 배열에 대한 레퍼런스 변수 선언 int intArray []; 배열 공간을 할당되지 않으며 레퍼런스 변수 intArray만 생성된다. intArray는 배열 공간에 대한 주소 값을 가지며 그 자체가 배열은 아니다. 이때 intArray의 값은 null이다. 이처럼 배열 주소를 레퍼런스라고 부르며, 주소값을 가지는 변수를 레퍼런스 변수라고 한다. 2. 배열 생성 배열 생성은 데이터를 저장할 배열 공간을 할당받는 과정이다. 반드시 new..

자바의 데이터 타입 ▶︎ 기본 타입 (8가지) 기본 타입의 크기가 정해져 있다 자바는 플랫폼 독립적인 언어이므로 모든 플랫폼에서 실행될 수 있도록 데이터의 크기가 항상 일정하다. 하지만 C인 경우 CPU의 처리 능력이나 운영체제에 따라 데이터가 차지하는 메모리 크기가 다르다. int형이 2바이트 일수도, 4바이트일 수도 있다는 것이다. 논리 타입 : boolean 1비트. JVM에 따라 1비트가 아닐수 있다. 문자 타입 : char 무조건 2바이트, Unicode 사용 Unicode는 최대 4바이트까지 표현될 수 있지만 UTF-16 인코딩 방식을 사용하여 2바이트로 표현될 수 있기 때문이다. 정수 타입 : byte 1바이트, -128 ~ 127 정수 타입 : short 2바이트 정수 타입 : int 4..

문제 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 핵심 풀이 위상 정렬을 이용해야하는 문제이다. 왜 위상 정렬을 이용하여 해결해야 하는가? 이 문제는 일부 학생들의 키 순서가 주어졌을 때, 전체 학생을 키 순서대로 줄을 세운 결과를 반환해야 한다. 즉 일분 학생간의 순서를 지키며, 전체 학새생을 줄 세워야한다. 위상정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다. 예를 들어 과목의 선수과목이 있는 과목들이 주어질 때 선수과목을 고려해서 수강 순..

본 포스팅은 '명품 JAVA Programming (개정4판)- 황기태 저' 책을 바탕으로 작성되었습니다.😀 프로그래밍 언어 기게어 어셈블리어 고급언어 - JAVA 언어의 진화 기계어 ➞ 어셈블리어 ➞ Fortran(수학 전용 언어) ➞ C ➞ C++ C 언어 왜 생겼을까? (1972) 유닉스라는 운영체제를 개발하기 위해 만든 언어 : 절차 지향 언어 시대 C++ 왜 생겼을까? (1983) PC가 생기면서 규모가 커져 만들고 관리하는 것이 너무 힘들어짐. 객체 지향언어 시대 JAVA 왜 생겼을까? (1995) 나온 이유 : C++의 어떤 문제를 해결하기 위해 등장 (어떤 문제인지 아래에서 기술) C++의 모양을 빌어 등장. 조상이 C++이다 컴파일 방식 자바 : .Java ➞ .class (링킹 과정 없..