전체 글

[알고리즘] 그리디 알고리즘의 특징과 그리디 구분법

그리디 알고리즘 특징 그리디 알고리즘은 최적해를 구하는 데 사용되는 근시안적인 방법이다. 최적화 문제(optimization)란 가능한 해들 중에서 가장 좋은(최대 또는 최소) 해를 찾는 문제이다. 일반적으로, 머리 속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy 접근이 된다. 여러 경우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다. 일단, 한번 선택된 것은 번복하지 않는다. 이런 특성 때문에 대부분의 탐욕 알고리즘들은 단순하며, 또한 제한적인 문제들에 적용된다. 그리..

Item 01. 생성자 대신 정적 팩터리 메서드를 고려하라 - 이펙티브 자바

클라이언트가 클래스의 인스턴스를 얻는 전통적인 수단은 public 생성자이다. 하지만 클래스는 생성자와 별도로 정적 팩터리 메서드를 제공할 수 있다. 정적 팩터리 메서드 (static factory method) public static Boolean valueOf(boolean b){ return b ? Boolean.TRUE : Boolean.FALSE; } 위 코드는 Boolean 객체를 얻는 정적 팩터리 메서드의 예시이다. 디자인 패턴에서의 팩터리 메서드와는 다른 개념이니 주의해야 한다. 정적 팩터리 메서드를 사용하면 생성자를 통하지 않고도 객체를 얻을 수 있다는 점 때문에 장단점만 잘 파악한다면 유용하게 사용할 수 있을 것이다. 정적 팩터리 메서드의 장점 이름을 가질 수 있다. 생성자에 넘기는 ..

[BOJ] 14499. 주사위 굴리기 - JAVA

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 문제 크기가 N×M인 지도가 존재한다. 지도의 오른쪽은 동쪽, 위쪽은 북쪽이다. 이 지도의 위에 주사위가 하나 놓여져 있으며, 주사위의 전개도는 아래와 같다. 지도의 좌표는 (r, c)로 나타내며, r는 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로부터 떨어진 칸의 개수이다. 2 4 1 3 5 6 주사위는 지도 위에 윗 면이 1이고..

커밋 메시지 가이드 (Udacity Git Commit Message Style Guide)

Intro 프로젝트를 진행하다 보면 자연스럽게 git으로 코드관리를 하게 된다. 프로젝트의 기능을 구현하면 commit을 하게 되는데, 이 때 작성하는 commit 메시지가 일관성 있고, 내용을 봤을 때 직관적으로 알아볼 수 있어야한다. 유다시티의 커밋 메시지 스타일 가이드는 커밋 메시지를 다른 사람과 협업 시 통일성과, 체계적인 커밋 메시지 스타일을 제시했는데, 이를 다시 한번 정리하고자 이 글을 작성하기로 했다. Udacity Git Commit Message Style Guide https://udacity.github.io/git-styleguide/ Message 구조 유다시티 커밋 메시지 가이드는 커밋 메시지를 제목, 본문, 꼬리말 세 부분으로 나누어 구성한다. type : subject bo..

컨텍스트 스위칭(Context Switching) 이란?

컨텍스트 스위칭이란? 멀티 프로세스 환경에서 CPU가 어떤 하나의 프로세스를 실행하고 있는 상태에서 인터럽트 요청에 의해 다음 우선 순위의 프로세스가 실행되어야 할 때, 기존의 프로세스의 상태 또는 레지스터 값을 저장하고 CPU가 다음 프로세스를 수행하도록 새로운 프로세스의 상태 또는 레지스터 값을 교체하는 작업을 말한다. 예를 들어 프로세스 A가 있고, 프로세스 B가 있을 때, CPU가 실행하는 프로세스를 A에서 B로, B에서 A로 바꾸는 기술이라고 할 수 있다. 그렇다면 프로세스 A, B의 정보를 기억해야할 필요가 있는데, 이 정보를 기록하는 곳이 바로 PCB(Process Control Block) 이다. PCB (Process Control Block) 프로세스 식별자(PID) 프로세스 상태정보 ..

프로세스 메모리 구조

스택 영역 (Stack) 함수 실행을 위한 지역변수 등이 저장되는 영역 프로그램이 자동으로 사용하는 임시 메모리 공간이다. 지역변수 (local variable), 매개변수 (parameter), 리턴값 등 잠시 사용되었다가 사라지는 데이터를 저장하는 영역 스택 사이즈는 각 프로세스마다 할당되지만 메모리에 로드 될 때 스택 사이즈가 고정되어 있어, 런타임 시에 스택 사이즈를 바꿀 수는 없다. 메모리의 가장 높은 주소에서 낮아지는 방향으로 데이터가 저장된다. 힙 영역 (Heap) 힙 영역은 동적으로 할당된 메모리를 위한 공간 메모리 주소 값에 의해서만 참조되고 사용되는 영역이다. C의 경우 malloc(), C++, java의 경우 new() 함수를 이용할 때 힙영역에 데이터가 저장된다. 데이터 영역 (D..

Arrays 클래스와 메서드정리 (java.util.Arrays)

Arrays 클래스 Arrays 클래스에는 java의 배열을 다루기 위한 다양한 메서드가 제공된다. 특징 항목정렬, 항목검색, 항복비교와 같은 메서드들을 제공 java.util 패키지에 포함되어 있는 클래스로 import문을 추가하여야 사용이 메서드 사용이 가능하다. Arrays 클래스의 모든 메서드는 static 으로 구성되어 있기 때문에 구현체없이 바로 사용이 가능하다. 메서드 설명 asList(값들) 전달받은 배열을 고정크기의 List로 반환한다. binarySearch(배열, 찾는 값) binarySearch(배열, 시작인덱스, 끝인덱스, 찾는 값) 전달받은 배열에서 key에 해당하는 값을 이진탐색 알고리즘을 통해 탐색 후 해당 인덱스를 반환한다. 배열이 정렬되어 있어야 이진탐색알고리즘이 제대로 ..

논리 회로 - 기본 논리 게이트 정리 (AND, OR, NOT, NAND, NOR, XOR, XNOR)

AND 게이트 모든 입력이 '1' 상태일 경우에만 출력이 '1' 상태가 된다. A B Out 0 0 0 1 0 0 0 1 0 1 1 1 OR 게이트 입력 중 하나만 '1' 상태이면 출력이 '1' 상태가 된다. A B Out 0 0 0 1 0 1 0 1 1 1 1 1 NOT 게이트 입력이 '1' 상태이면 출력을 '0' 상태, 입력이 '0' 상태이면 출력을 '1' 상태가 된다. A Out 0 1 1 0 NAND 게이트 NAND는 negative-AND 의 뜻으로 입력을 AND로 출력한 결과에 NOT을 통과시킨 값이다. 따라서, 모든 입력값이 '1' 상태일 때에만 출력이 '0' 상태가 된다. A B Out 0 0 1 1 0 1 0 1 1 1 1 0 NOR 게이트 NOR는 negative-OR 의 뜻으로 입력을..