코딩처럼

탐욕 알고리즘(Greedy Algorithm)이란?말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다. 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 탐욕 알고리즘으로 문제를 해결하는 방법선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가..

시간 복잡도문제를 해결하기 위해 알고리즘의 로직을 코드로 구현할 때 입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가를 의미한다.  시간 복잡도 표기법Big - O (빅 - 오)Big - Ω (빅 - 오메가)Big - θ (빅 - 세타)위 세 가지 표기법은 각각 최악, 최선, 평균의 경우에 대하여 나타내는 방법이다. 이 중 Big - O 표기법이 가장 자주 사용된다. Big - O 표기법은 최악의 경우를 고려하기 때문에 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있다. O(1)Constant complexity라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다.입력값의 크기와 상관없이, 즉시 출력값을 얻어낼 수 있다는 의미이다.public in..

그래프(Graph)그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다. 그래프의 구조직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다.간접적인 관계라면 몇 개의 점과 선에 걸쳐 이어진다.하나의 점을 그래프에서는 정점(vertex)라고 표현하고 하나의 선은 간선(edge)라고 한다.  그래프의 표현 방식인접 행렬두 정점을 바로 이어주는 간선이 있다면 두 정점은 인접하다고 이야기한다. 인접 행렬을 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 나타낸다. 만약 A라는 정점과 B라는 정점이 이어져 있다면 1(true), 이어져 있지 않다면 0(false)으로 표시한 일종의 표이다.                                    ..

StringBuilder한번 생성된 String 클래스의 인스턴스는 여러 개의 문자열을 더할 때 매번 새로운 인스턴스를 생성해야 한다. 만약 100만개의 문자열이 있는데 모두 더하는 작업이 필요하다면 인스턴스 생성과정이 100만번 이루어져야 하기 때문에 매우 비효율적이다. 그래서 StringBuilder를 사용한다. StringBuilder stringBuilder = new StringBuilder();stringBuilder.append("문자열 ").append("연결");String str = stringBuilder.toString();System.out.println(stringBuilder);System.out.println(str);/* 출력문자열 연결문자열 연결*/먼저 StringBuil..

트리(Tree)란?Tree는 이름 그대로 나무를 거꾸로 뒤집어 놓은 형태를 가지고 있다. 그래프의 여러 구조 중 단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태이다. 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조이다. 데이터를 순차적으로 나열시킨 선형 구조가 아니라, 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조이다.아래로만 뻗어나가기 때문에 사이클이 없다.트리 구조는 루트(root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(edge)으로 연결한다. 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다. A는 B와 C의 부모 노드(Parent Node)..

StringTokenizerStringTokenizer 클래스는 문자열을 우리가 지정한 구분자로 문자열을 쪼개 주는 클래스이다. 그렇게 쪼개어진 문자열을 토큰(token)이라고 부른다. 이 클래스를 사용하기 위해서는 java.util.StringTokenizer를 import 해야 한다.import java.util.StringTokenizer;public class Main { public static void main(String[] args) { String str = "This is a string example using StringTokenizer"; StringTokenizer tokenizer = new StringTokenizer(str); System.out.print..

String 문자열 이란?기본적으로 String 타입은 큰따옴표(" ")로 감싸진 문자열을 의미한다. 자바는 String 클래스 타입을 사용하여 문자열을 다룬다. 다시 말해 문자열은 String 클래스를 통해 다루어지고 그 안에 있는 메서드들을 통해 여러 문자열 관련 메서드들을 사용할 수 있다. String 타입의 변수 선언과 할당// 문자열 리터럴을 String 타입의 변수 name에 할당하는 방법String name1 = "Kim Coding";// String 클래스의 인스턴스를 생성하는 방법String name2 = new String("Kim Coding");String 타입의 변수는 String 변수명; 으로 선언한다.선언한 변수에 문자열을 할당하는 방법에는 두 가지가 있다.문자열 리터럴을 할..

https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때,www.acmicpc.net 셀프 넘버는 1부터 10000까지 검사한 뒤, 생성자로 하는 수가 있으면 그 수를 출력하지 않는 것이다. 셀프넘버를 찾기위한 반복문 구성 Ex. d(75) = 75 + 7 + 5 = 87이 나오도록 구성해야한다.각 자리수를 더해주기 위해서 나눗셈 단위로 number을 줄여 갈 것이기 때문에 number가 0보다 클 때까지 반복한다. 첫 째 자리수를 구..

큐(Queue)란?사전적 의미로는 무엇을 기다리는 사람, 혹은 줄을 서서 기다리는 것을 의미하는데 이처럼 줄을 지어 순서대로 처리되는 것이 큐라는 자료구조이다. 이 자료구조에서는 앞(front)과 뒤(back)가 존재한다. 가장 먼저 진입한 데이터가 가장 먼저 나가고 마지막에 진입한 데이터는 먼저 들어온 데이터가 모두 빠져나가기 전까지는 빠져나갈 수 없다. 큐 사용 사례프린터 인쇄※ 프린터 인쇄 과정문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업(임시 기억 장치의) Queue에 들어간다.프린터는 인쇄 작업 Queue에 들어온 문서를 순서대로 인쇄한다.예시처럼 컴퓨터 장치들 사이에서 데이터를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구..

스택(Stack)이란?Stack은 쌓다, 쌓이다, 포개지다 와 같은 뜻을 가지고 있다. 마치 접시를 쌓아 놓은 형태와 비슷한 이 자료구조는 직역 그대로, 데이터(data)를 순서대로 쌓는 자료구조이다. 다시 말해 가장 먼저 들어간 데이터는 가장 나중에 나올 수 있고 마지막에 들어간 데이터가 가장 먼저 나올 수 있는 구조이다. 스택의 사용 사례음료수 진열대 (먼저 들어간 것이 나중에 나옴)인터넷 브라우저 창 (뒤로 가기, 앞으로 가기 기능) 스택의 특징입력과 출력이 하나의 방향으로 이루어지는 제한적인 접근에 있다. LIFO(Last In First Out) 혹은 FILO(First In Last Out)이라고 부른다.데이터는 하나씩 넣고 뺄 수 있다.스택 클래스 메서드empty()해당 스택이 비어 있는지 ..