전체 글
OOP - 클래스와 객체
복습하며 내용을 간단하게 정리하였다. 클래스와 객체 클래스 선언 참조 타입 String 클래스 필드 선언 메소드 변수 범위와 static 생성자 this 키워드 메소드 오버로딩 생성자 오버로딩 패키지 클래스와 객체 1. 클래스 선언 자바에서 객체를 만들기 위해서는 반드시 클래스를 만들어야한다. 간단하게 유명한 비유를 적어보자면 붕어빵을 만든다고 할 때, 붕어빵이 객체이고 붕어빵 틀이 클래스이다. Car라는 클래스를 만들어보자. public class Car { }이렇게 클래스만 만들었다고 하여 자동차 객체가 만들어진 것은 아니다. Car 객체를 만들어보자. public class CarMake { public static void main(String[] args) { Car c1=new Car(); C..
BOJ 11052 카드 구매하기
boj 11052 카드 구매하기 - 문제 링크 https://www.acmicpc.net/problem/11052 - 문제 해설 DP가 작은 문제부터 쌓아나가서 구하고자 하는 값을 구하는 알고리즘임을 생각하면 쉽게 접근 방법을 찾을 수 있다. 나는 보통 DP로 문제를 풀 때 D[i]를 어떻게 나눌지를 생각하는 편이다. D[i]를 i개의 카드를 사는 금액의 최댓값이라고 지정하자. 그러면 아래와 같이 쪼갤 수 있다. D[i-1] + P[1] : 카드 1개가 들어있는 팩의 구매 값 + i-1개의 카드를 구매한 최댓값 D[i-2] + P[2] : 카드 2개가 들어있는 팩의 구매 값 + i-2개의 카드를 구매한 최댓값 . . . D[0] + P[i] : 카드 i개가 들어있는 팩의 구매 값 + 0개의 카드를 구매한..
BOJ 2011 암호코드
boj 2011 암호코드 - 문제 링크 https://www.acmicpc.net/problem/2011 - 문제 해설 DP를 이용하여 간단히 풀 수 있는 문제이다. D[i]가 주어진 암호의 i번째까지에서 해석할 수 있는 가짓수라고 하자. 끝 두자리의 숫자가 10 ~ 26 범위이면 한자리 숫자 2개가 될 수도 있고 두자리 숫자 1개가 될 수도 있다는 점을 생각하면 문제를 쉽게 해결할 수 있다. 생각해볼 사항들이 무엇이 있는지 살펴보자. 암호의 처음 숫자가 0일 시에는 0을 출력한다. 맨 끝 한 자리가 0인 경우는 맨 끝 두 자리가 10, 20인 경우를 제외하고는 암호가 성립할 수 없다. 예를 들면 맨 끝 두 자리가 00, 30, 40 ... 90 같은 경우는 대응되는 알파벳이 없기에 암호가 성립되지 못한..
이분탐색(Binary search)
- 이분탐색이란? 이분탐색이란 정렬이 되어있는 배열에서 원하는 데이터를 찾기 위해 순서대로 찾아보는 방법 대신에 탐색 범위를 절반으로 줄여나가며 찾는 탐색 방법이다. boj 문제 중에 이분탐색을 요구하는 문제가 있어서 문제를 보면서 이분탐색의 개념을 정리했다. - boj 1920 수 찾기 https://www.acmicpc.net/problem/1920 예시로 A 배열에 '3 5 6 9 10 12 14 26 35 41' 이 주어졌다고 하고, 14가 있는지 알아본다고 하자. 입력 받은 후에 sort 함수를 이용해서 정렬하면 앞과 같이 정렬된 상태일 것이다. 원래 문제는 A 안에 14가 있는지만 확인하면 되지만, 14가 A 안에서 위치하는 인덱스를 반환하는 함수를 구현해보려고 한다. st와 e..
그래프(graph)
목차 그래프의 정의 그래프의 분류 그래프의 표현 그래프와 BFS 그래프와 DFS 1. 그래프의 정의 자료구조에서 의미하는 그래프는 다음과 같은 형태이다. 점을 정점(vertex/node)라고 부르고 점을 이어주는 선을 간선(edge)라고 부른다. 그리고, 각 정점에 연결되어있는 간선의 갯수를 차수(degree)라고 한다. 2. 그래프의 분류 - 무방향그래프와 방향그래프 위의 그림과 같이 그래프를 분류할 수 있다. 그래프의 간선에 방향이 없을 경우 무방향 그래프(undirected graph)라고 부르고, 아래와 같이 방향이 있을 경우에는 방향 그래프(directed graph)라고 한다. 이때, 방향 그래프에서 정점에서 나가는 간선의 수를 outdegree, 들어오는 간선의 수를 indegree라고 한다..