Keep calm and carry on

세 수의 합 링크Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.Notice that the solution set must not contain duplicate triplets.배열을 입력받아 합으로 0을 만들 수 있는 3개의 엘리먼트를 출력하라. 입력: nums = [-1, 0, 1, 2, -1, -5] 출력: [[-1, 0, 1], [-1, -1, 2]]  해당 문제는 Brute force방법으로 O(n^3)에 답을 찾을 수 있으나, O(n^2)만에도 답을 낼 수 있다...

두 수의 합 링크 nums = [2, 6, 11, 15], target = 8 이 주어졌을 때, 배열에 있는 두 숫자를 덧셈하여 target과 같은 값을 만들 수 인덱스를 리턴하라. 'nums[0] + nums[1] == target' 인 경우 리턴은 'new int[] {0, 1};' 이다.  이 문제는 Map 자료형을 이용하여 O(n)에 풀이할 수 있다.인덱스를 조회할때 마다 조건에 대해 판별하고 조건에 부합하면 return 아니면 Map에 데이터를 추가하는 형식으로 진행.if (map.contains(target - nums[someIdx])) return new int[] {map.get(target - nums[someIdx]), someIdx}; map.put(nums[someIdx]..

자료구조는 크게 메모리 공간 기반의 연속(Contiguous)방식과 포인터 기반의 연결(Link)방식으로 나뉜다.배열은 이 중 연속방식의 가장 기본이 되는 자료형이다. 연결 방식의 가장 기본이 되는 자료형은 연결 리스트이다.배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할방받는 작업을 수행하는 자료형이다. 배열의 예시를 그림으로 살펴보자.  C언어를 기준으로 int arr[4] = {4, 7, 29, 0}; 라는 예시를 들면, 위 그림과 같다. 32비트 이상의 시스템에서는 int를 4바이트로 사용한다. 배열은 어느 위치나 O(1)에 조회가 가능하다는 장점이 있다. 동적배열 배열이란 고정된 크기만큼의 연속된 메모리 할당한다. 그러나 실제 크기를 가늠하기 어려운 상황에 따라 동적으로 메모리를 ..

'재귀 알고리즘의 예시와 분석'의 내용을 살펴봤다. 다음으로 재귀 알고리즘의 비재귀적 표현 방식과 메모화를 확인해본다.재귀 알고리즘의 비재귀적 표현 recur 메서드를 비재귀적으로 구현하는 방법을 살펴본다. 우선 '꼬리' 재귀를 제거 하는 방법이 있다. recur(n - 2)는 인수로 n - 2를 전달하여 recur 메서드를 호출한다.이 호출을 바꾼다. n값을 n - 2로 업데이트하고 메서드의 시작 지점으로 돌아간다. // 수정 이전의 코드if (n > 0) { recur(n - 1); System.out.println(n); recur(n - 2); // 꼬리를 제거, n - 2로 업데이트하고 메서드의 시작 지점으로 돌아가야 한다} // 수정 후의 코드, if 문을 while 문으로 수..

재귀 알고리즘 분석하기 재귀 호출을 여러 번 실행하는 순수(genuinely) 재귀의 예시.package org.study.bohyohshibata;public class Recur { static void recur(int n) { if (n > 0) { recur(n - 1); System.out.println(n); recur(n - 2); } } public static void main(String[] args) { recur(4); }} 출력 결과는 아래와 같다.1231412하향식 분석과 상향식 분석recur(4) 는 아래와 같은 순서대로 실행된다.recur(3)을 실행.4를 ..

빅오 (Big-O) 컴퓨터과학에서 빅오는 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구 사항(공간 복잡도)이 어떻게 증가하는지를 분류하는 데 사용되며, 알고리즘의 효율성을 분석하는 데도 매우 유용하게 활용된다.빅오 표기법이란 입력 크기가 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법으로, 특히 점근적 실행 시간이란 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 함수의 실행시간 추이를 의미한다. 알고리즘은 궁극적으로는 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다.빅오로 시간 복잡도를 표현할 때는 최고차 항만을 표기하며, 계..

자바 알고리즘 인터뷰 책을 보며 학습한 내용 // 예시List a = new ArrayList();// 삽입 시 add() 사용a.add(1);a.add(2);a.add(3);Set b = new HashSet();// 삽입, add() 로 동일b.add(1);b.add(2);b.add(3);Map c = new HashMap();// 삽입 시 put() 사용, 키/값 형태로 데이터 추가c.put("a", 1);c.put("b", 2); 초기 자료형의 성능 문제 자바는 1.0 정식 버전을 출시하던 초기 시절부터 목록형 자료형에 대한 고민이 있었다. 자바 컬렉션 프레임워크가 등장한 것은 그로부터 2년이나 더 지난 후였고, 그 전에는 C++의 영향을 받아 벡터 형태의 자료형과 해시 테이블 형태의 자료형을 별..

자료구조와 함께 배우는 알고리즘 입문 책을 보며 학습한 내용 이진 검색 이 알고리즘은 데이터가 키값으로 이미 정렬(sort)되어있다 전제 조건이 필요하다.이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다. 이진 검색 알아보기아래와 같이 오름차순으로 정렬된 데이터에서 39를 검색하는 예시다.int[] a = {5, 7, 15, 28, 29, 31, 39, 58, 68, 70, 95};먼저 배열의 중앙(10 / 2 == 5)에 위치한 요소인 a[5](값: 31)부터 검색을 시작.검색할 값인 39는 중앙 요소(a[5])보다 큼. 따라서 검색 대상을 뒤쪽의 5개(a[6] ~ a[10])로 좁힘. 그리고 다음 검색 범위의 중앙에 위치한 요소인 a[8](값: 68) 선택한다.검색할 값인 39는 중앙요소 a[..

자료구조와 함께 배우는 알고리즘 입문 책을 보며 학습한 내용 보초법으로 선형 검색 구현하기 선형 검색은 반복할 때마다 종료 조건 1, 2를 모두 판단함.처리할 데이터의 양이 많을수록 종료 조건을 검사하는 비용은 커짐. 보초법은 이 비용을 50%로 낮춤.    배열 요소 a[0] ~ a[6]은 원래의 데이터이다. 맨 끝 요소 a[7]은 검색하기 전에 값을 추가하여 저장한 보초(sentinel)이다.보초법을 사용시 아래의 코드와 같이 조건문 수정 가능함.int i = 0;a[n] = key;while (true) { if (a[i] == key) break; i++;}return i == n ? -1 : i;

자료구조와 함께 배우는 알고리즘 입문 책을 보며 학습한 내용 배열에서 검색하기선형검색: 무작위로 늘어서 있는 데이터 모임에서 검색을 수행함.이진검색: 일정한 규칙으로 늘어서 있는 데이터 모임에서 아주 빠른 검색을 수행함.해시법: 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행함.체인법: 같은 해시값의 데이터를 선형 리스트로 연결하는 방법오픈 주소법: 데이터를 위한 해시값이 충돌할 때 재해시하는 방법 선형 검색 요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색한다.이를 ‘선형 검색(linear search)’ 또는 ‘순차 검색(sequential search)’이라함.선형 검색에서 배열 검색의 종료 조건은 2개이다.검색 ..