그럼에도 불구하고

Overview 이 장에서는 여러 Data Structure의 개념과 자바에서는 실제로 어떻게 구현되어 있는지 알아보도록 한다. Linear Data Structure Array 논리적 저장순서와 물리적 저장순서가 일치한다. 즉 메모리에서 연속적으로 데이터가 기록되는 자료구조이다. 이 특성 덕에, 특정 아이템을 인덱스를 알면 O(1)안에 접근이 가능하지만(random access), 아이템 삭제나 추가를 진행할 때, 연속성을 유지해야 하기 때문에 최대 O(n)의 시간복잡도가 발생한다. 보통 자바에서는 []를 통해서 Array를 생성하며, 아래와 같이 스택 영역에 Array의 레퍼런스를 저장하고 힙 영역의 메모리에 연속적으로 데이터를 할당하고 있다. 이 때, 메모리의 크기는 고정적이다. 또한 Array에서..

출처: http://t1.kakaocdn.net/codefestival/preliminary.pdf 이번에 풀어볼 문제는 다음과 같습니다. 이번 문제를 풀 때 DFS search를 써서 인접한 영역들을 찾아내고 그 크기를 계산하는 것을 시도했습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 class Solution { public static int m,n; public static int[][] picture; public static boolean visited[]..

Selection Sort(선택정렬) & Bineary search(이진탐색) 목차 선택정렬 설명 & 코드 이진탐색 설명 & 코드 알고리즘 코딩을위한 팁 Selection Sort(선택정렬) 설명 선택정렬이란?: 선택 정렬은 전체배열에서 가장 작은 것(또는 큰것)들을 하나씩 선택하여 정렬을하는방법입니다. 선택정렬을위한 단계 주어진 리스트 중에 최솟값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 자 그럼 단계를 알았으니 이것을 C언어로 프로그래밍해보겠습니다. 프로그램은 배열의 크기와 배열을 입력받아서 이를 선택정렬후 출력하도록합니다. 시작하기전 어떻게 코딩을 할것인지 각주를 통해 구상을 해봅시다. 1. 배열을 입력받아야하..

Transposing Sparse Matrix 1. 희소행렬(Sparse Matrix)이란? 희소행렬은 행렬안의 값들 중에서 0이외의 값이 희소한 행렬을 의미합니다. 따라서 대부분 0이라면 모든 값들을 표현하지 않고 0이아닌 값과 그 위치만 알고 나머지는 0이다 라고 표현을 할 수 있습니다. 그러므로 평소에 그리던 행렬을 이런 방식으로 표현할 수 있습니다.(변환 방식은 생략) 2. 희소행렬의 대칭이동 위에서 봤던 간단하게 표현된 행렬을 통해서 대칭이동을 하겠습니다. 단순한 대칭이동은 그저 row와 col값을 교환해주면 간단합니다. 그러나 정렬을 유지 하고싶다면 어떻게 해야할까요? 단순 교환은 정렬이 유지되지 않습니다. 따라서 새로운 방법을 궁리해야합니다. 3. 대칭이동과 정렬 우선 기존행렬을 A, 바뀐 ..