leesche blog

트리다 트리!!! 문제 링크 문제 설명 n개의 음의 아닌 정수를 적절히 더하거나 빼서 타깃 넘버로 만드는 경우를 수를 구하는 문제다. 해결 과정 결국 n 개의 모든 수를 각각 더하거나 뺄 수 있다. 그리고 그 경우의 수를 알고, 그 값들이 타깃 넘버인지 비교해야 한다. 처음에는 어떻게 이 모든 경우를 반복문으로 구한단 말인가? 절망하다가 뭔가 규칙이 느껴지는 듯 했다. 더하거나, 빼거나, 더하거나 빼거나 ... 그리고 그 값은 누적된다. 트리다 트리!! 마치 위와 같은 형태였다. 오오, 이것은 트리였다! 트리의 모든 요소를 다뤄야 하나? 그리고 numbers로 들어온 요소의 수를 더하든 빼든 그 결과만 모아서 확인해야 하는데, 그것은 트리에서 같은 깊이, Level을 들여다보면 됐다. 그렇다면 트리를 어..

List 자료 구조 선택하기 (Java) ArrayList와 LinkedList 중 어떤 자료구조를 선택하면 좋을까? 이중 연결 리스트 구현은 ArrayList 클래스보다 시작에 요소를 추가하고 삭제하는 연산이 좋다. 끝에 요소를 추가하고 제거하는 연산은 ArrayList와 동일하다. 따라서 ArrayList 클래스의 유일한 이점은 get과 set 메서드이다. 연결 리스트는 심지어 이중 연결 리스트일 때도 선형 시간이 필요하다. 응용 프로그램의 실행 시간이 get과 set 메서드에 의존한다면 ArrayList 클래스가 좋은 선택이다. 실행 시간이 시작이나 끝 근처에 요소를 추가하거나 제거하는 연산에 의존한다면 LinkedList 클래스가 좋다. 하지만 이러한 추천은 큰 문제의 증가 차수에 기반을 두고 있..

사전(Dictionary)의 구현: 해시 테이블(Hash Table) 해시 테이블(Hash Table)은 문자열을 인수로 받아서 정수를 반환하는 '해시 함수'를 사용해서 문자열과 값의 대응 관계를 표현하는 방법이다. 값을 넣기 위해서 우선 큰 배열을 준비한다. 그리고 해쉬 함수를 사용해서 문자열을 '적당한 정수'로 변환한 후 해당 배열 어디에 넣을지를 결정한다. → 실제로 해쉬 테이블을 구현할 때 몇 가지 문제가 있다. 다른 키를 해쉬 함수에 넣었는데 가끔 같은 번지의 값을 참조하는 경우, 이를 해시 충돌(Hash Collision)이라 하며, 해결 방법으로 Chaining, Open Addressing이 있다. 공간 효율성이 떨어진다. 데이터가 저장되기 전에 미리 저장 공간..

edwith 강의 마지막에 생각해보기 질문이 다음과 같았다. 만약 정렬되지 않은 배열이 있다면, 선형 검색이 빠를까요 이진 검색이 빠를까요? [LECTURE] 1) 검색 알고리즘 : edwith 들어가기 전에 지난시간까지 우리는 메모리의 구조, 자료형, 배열과 같은 기본적인 개념을 익혔습니다. 이번 강의부터는 여태까지 배운 내용을 활용하여 검색이나 정렬과 같은 문제를 푸는... - www.edwith.org 내가 현재 가지고 있는 자료구조와 알고리즘 책에서는 이진 검색의 '전제'가 '정렬된 데이터'에서 검색하는 것이기 때문에 문제가 성립하지 않는다. 하지만 무시하고 진행시키면 속도는 어떻게 측정할 수 있을까? 선형 검색의 경우 그냥 처음부터 검사하면 되지만, 이진 검색의 경우 문제가 생긴다. 이진검색은 ..

이진 검색 이진 검색(binary search)은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다. 방법 (정렬된) 배열의 중앙에 위치한 요소를 검색하여 원래 검색하려는 값과 크기를 비교한다. 만약 값이 크다면, 중앙값 다음 순서부터 끝까지 배열의 중앙 값을 찾는다. 그리고 원래 검색하려는 값과 비교한다. 그렇게 검색 범위를 한 번에 절반씩 좁혀나간다. 중앙값이 검색하려는 값과 일치하거나 검색 범위가 더 이상 없는 경우 알고리즘을 종료한다. 이진 검색은 검색을 반복할 때마다 검색 범위가 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n 이다. 복잡도 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 한다. 복잡도는 아래의 두 가지 요소를 가지고 있다. 시간 복잡도:..

좋은 알고리즘의 특징 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 한다. 유일성 : 각 단계마다 명확한 다음 단계를 가져야 한다. 타당성 : 구현할 수 있고 실용적이어야 한다. 입력 : 정의된 입력을 받아들일 수 있어야 한다. 출력 : 답으로 출력을 내보낼 수 있어야 한다. 유한성 : 특정 수의 작업 이후에 정지해야 한다. 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 한다. 알고리즘 개발의 정형적인 단계 문제 정의 → 모델 고안 → 명세 작성 → 설계 → 검증 → 분석 (복잡도 등) → 구현 → 테스트 → 문서화 분류 구현 : 재귀적 알고리즘, 연역적 알고리즘, 결정론적 알고리즘, 근사 알고리즘, 양자 알고리즘 등. 설계 : 무차별 대입 공격, 분할 정복 알고리즘, 그래프 순회, 분기 한..

데이터 집합에서 원하는 값을 가진 요소를 찾아내려면 어떻게 해야 할까? 검색과 키 주소록에서 원하는 사람을 검색한다고 가정했을 때, '키'를 사용해 사람을 찾는다. '키(key)'는 형이 여러 개다. 예를 들어 (국가, 나이, 이름 등 ...) 키 값과 일치하거나, 키 값의 구간을 지정하거나, 키 값과 비슷하도록 지정해서 검색할 수 있다. 배열에서 검색하기 배열 검색의 경우 다음의 알고리즘을 활용한다. 선형 검색: 무작위로 늘어놓은 데이터 모임에서 검색을 수행한다. 이진 검색: 일정한 규칙으로 늘어놓은 데이터 모임에서 아주 빠른 검색을 수행한다. 해시법: 추가,삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다. 체인법: 같은 해시 값의 데이터를 선형 리스트로 연..

클래스 클래스는 임의의 데이터형을 자유로이 조합하여 만들 수 있는 자료구조이다. 자바의 클래스란, 노션에서는 템플릿, PPT에서는 슬라이드 마스터, 티스토리 블로그에서는 서식 같은 존재가 아닐까. 클래스는 클래스 이름, 데이터 요소(필드)로 구성된다. 필드는 임의의 데이터형이 될 수 있다. 클래스형 변수를 사용할 때는 먼저 클래스형 변수(실체를 참조하는 변수)를 만들고, 그리고 실체인 클래스 인스턴스를 생성해야 한다. // 클래스 XYZ class XYZ { int x; // int형 필드 long y; // long형 필드 double z; // double형 필드 } XYZ a; // XYZ형의 클래스형 변수 a 선언 a = new XYZ(); // XYZ형의 클래스 인스턴스(실체를 생성) 클래스의 ..

간단하게 2차원 배열을 선언하자면, int[][] x = new int[2][4] 과 같다. Java는 엄밀한 의미에서 다차원 배열이 없다. 2차원 배열을 '배열의 배열'로 생각하고 3차원을 '배열의 배열의 배열'로 생각하기 때문이다. 따라서 배열 x의 형은 아래와 같다. int 형을 구성 자료형으로 하는 배열"을 구성 자료형으로 하는 배열 다차원 배열 개념을 연습해보기 위해 예시를 들어보자. 한 해의 경과 일 수를 나타내는 프로그램 package chap02; import java.util.Scanner; // 그 해 경과 일수를 구함 class DayOfYear { // 각 달의 일 수 static int[][] mdays = { {31, 28, 31, 30, 31, 30, 31, 31, 30, 31..

어떤 정수 n에 대하여 아래의 조건을 만족하면 소수임을 알 수 있다. 2부터 n-1 까지의 어떤 정수로도 나누어 떨어지지 않는다. 그래서 처음 아래와 같은 프로그램을 작성한다면, 나눗셈을 하는 횟수가 너무 많아진다. 책에서는 위와 같은 문제를 해결하기 위해 아래와 같은 코드를 제시했다. 아래 알고리즘은 배열을 이용했고, 정수 n 이 소수이려면, 2부터 n-1 까지의 어떤 소수로도 나누어 떨어지지 않는다. 는 조건을 만족해야 한다는 아이디어를 바탕으로 하고 있습니다. package chap02; // 1,000 이하의 소수를 열거(버전 2) class PrimeNumber2 { public static void main(String[] args) { int counter = 0; // 나눗셈의 횟수 int..