L.O.K

[스프링] 어플리케이션 컨텍스트 ( Application Context ) [스프링] 프레임워크란 무엇인가? ( 제어의 역전 (IOC) ) 스프링은 '프레임워크(FrameWork)'이다. 프레임워크가 개발자의 작업을 도와준다는 말을 많이 들어봤을 것이다. 어떻게 도와준다는 말일까? ' lordofkangs.tistory.com 지난 포스팅에서 프레임워크의 핵심 원리인 '제어의 역전(IoC)'을 구현하는 어플리케이션 컨텍스트에 대해서 알아보았다. 그럼 이번 포스팅에서는 Maven으로 Spring 라이브러리를 추가한 후, 어플리케이션 컨텍스트를 실제로 생성해보겠다. Maven으로 Spring 라이브러리 추가하기 어플리케이션 컨텍스트를 사용하려면 어플리케이션 컨텍스트 기능이 담긴 인터페이스가 필요하다. 표준 ..

1427번: 소트인사이드 첫째 줄에 정렬하고자하는 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 문제 추상화 주어진 수의 각 자리수를 내림차순으로 정렬하시오 2. 알고리즘 1. 수를 문자열로 받는다. 2. 문자열의 길이만큼 정수 배열을 생성한다. 3. 문자열의 각 문자를 배열에 정수로 저장한다. 4. 내림차순 정렬을 한다. 1번 - 3번까지의 코드는 아래와 같다. // 1. 수를 문자열로 받기 public static void setInputData() { Scanner sc = new Scanner(System.in); input = sc.next(); } // 2. 문자열의 길이만큼 정수배열 생성하기 public static void ..

2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 1. 문제 추상화 주어진 수들의 산술평균, 중앙값, 최빈값, 범위를 구하시오. 2. 알고리즘 1) 정렬 알고리즘 퀵정렬, 합병정렬, 카운팅 정렬, 힙정렬로 풀어볼 것이다. ( 참고로 버블정렬은 시간초과가 난다. ) (각 정렬의 알고리즘은 아래 포스팅을 참고바랍니다!) [알고리즘] 퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort)은 이름 그대로 정렬을 빠르게 하는 알고리즘이다. 그러나 버블정렬에 비해 빠를 뿐, 이름만큼 가장 빠른 정렬 알고리즘은 아니다. 퀵 정렬(..

힙 정렬( Heap Sort )은 성능 좋은 정렬 알고리즘이지만 원리를 이해하기 쉽지 않다. 그 이유는 완전 이진 트리를 이용하기 때문이다. [자료구조] 완전이진트리 배열에 저장하기 완전 이진 트리를 이해하기 위해 이진 트리에 대해서 알아보자. 이진 트리란? 위 그림은 이진트리의 가장 기본적인 구조이다. 부모는 자식을 갖는다. 이는 굉장한 의미를 갖는다. 버블정렬, 퀵 lordofkangs.tistory.com 완전이진트리는 위 포스팅에 정리해놓았다. 간단히 요약하면 이진트리는 계층구조에 특별한 조건을 적용하면 탐색효율을 올릴 수 있다. 그 중에서 완전이진트리는 좌측노드부터 빈 노드 없이 채우기에 배열로 구현하기 쉽다. 배열로 구현하려면 부모와 자식간의 인덱스 관계를 알아야 한다. 부모의 인덱스가 N이라..

완전 이진 트리를 이해하기 위해 이진 트리에 대해서 알아보자. 이진 트리란? 위 그림은 이진트리의 가장 기본적인 구조이다. 부모는 자식을 갖는다. 이는 굉장한 의미를 갖는다. 버블정렬, 퀵정렬, 병합정렬은 모든 데이터가 동등한 지위를 갖었다. 그러나 힙정렬은 계층구조를 이용한다. 이런 수직적 구조는 '탐색'에 유용하기에 선택정렬을 응용한 힙정렬에는 알맞는 구조이다. 부모보다 작은 값은 왼쪽 자식, 부모보다 큰 값은 오른쪽 자식에 저장된다고 가정하자. 만약 탐색값이 부모보다 크다면 왼쪽 트리는 탐색할 필요가 없다. 그러므로 탐색할 노드의 수가 절반으로 줄어든다. 이와같이, 이진트리는 부모와 자식간의 규칙을 설정할 수 있다. 규칙은 데이터의 위치를 특정지을 수 있다. 이는 탐색에 유용하다. 그렇다면 구현은 ..

[스프링] 프레임워크란 무엇인가? ( 제어의 역전 (IOC) ) 스프링은 '프레임워크(FrameWork)'이다. 프레임워크가 개발자의 작업을 도와준다는 말을 많이 들어봤을 것이다. 어떻게 도와준다는 말일까? '프레임워크'란 무엇인가? 프레임워크를 사용하지 않으 lordofkangs.tistory.com 지난 포스팅에서 프레임워크(Framework)란 무엇인가 알아보았다. 간단히 요약하면 프레임워크는 객체의 생성 및 관계 설정 권한을 소스코드로부터 완전히 가져오는 도구를 의미한다. 이를, 제어의 역전(IoC)이라 부른다. 그럼 이번 포스팅에서 구체적으로 어떤 방식으로 제어의 역전이 이루어지는지 알아보자. 어플리케이션 컨텍스트 ( Application Context ) 지난 포스팅에서 객체의 생성 및 관계 ..

10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 1. 문제 추상화 N개의 수를 오름차순 정렬 하시오. 2. 알고리즘 카운팅 정렬을 사용하는 문제이다. 카운팅 정렬은 퀵, 병합, 힙 정렬같이 복잡하지 않고 단순하고 직관적이다. 시간복잡도도 O(N)으로 굉장히 빠르다. 이해하기 쉽고 빠르다는 장점이 있지만 많은 수의 정렬은 힘들다. 1. 입력받은 N개의 수를 배열에 저장하고 제일 큰 값을 구한다. 2. 제일 큰 값이 10이므로 배열의 크기가 ( 10 + 1 )인 카운팅 배열 하나를 생성한다. 3. 입력받은 수와 대응하는 인덱스가 가..

2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1. 문제 추상화 주어진 수의 나열을 시간복잡도 O(NlogN) 이상의 알고리즘으로 오름차순 정렬하라. 2. 알고리즘 O(NlogN) 시간복잡도는 정렬을 두 구간으로 분할정복할 때의 시간복잡도이다. N개의 수를 N번 비교하면 O(N2) ( 버블정렬 ) N개의 수를 분할한 수만큼 비교하면 O(NlogN) ( 퀵정렬, 병합정렬 ) 퀵정렬은 최악의 경우 O(N2)의 시간복잡도를 가진다. 테스트케이스 중 퀵정렬 저격용 최악의 경우도 있기 때문에 웬만하면 병합..

시간복잡도 O(N2)과 O(NlogN)의 차이는 분할정복을 하느냐 안 하느냐의 차이이다. N개의 수를 N번 비교하는게 아니라 (버블정렬) N개의 수를 분할한 수만큼 비교하는 것이다. (퀵정렬) [알고리즘] 버블정렬 향상 시키기 버블정렬은 가장 쉽고 이해하기 쉬운 정렬이다. 그러나 시간복잡도가 O(n2)이어서 효율이 좋지 않다. 7개의 수를 일차원 배열에 저장하였다. 이제 버블정렬을 사용하여 오름차순으로 바꾸어 보 lordofkangs.tistory.com [알고리즘] 퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort)은 이름 그대로 정렬을 빠르게 하는 알고리즘이다. 그러나 버블정렬에 비해 빠를 뿐, 이름만큼 가장 빠른 정렬 알고리즘은 아니다. 퀵 정렬(Quick Sort) 알고리즘이란? 정렬 ..

[알고리즘] 퀵 정렬 (Quick Sort) 퀵 정렬(Quick Sort)은 이름 그대로 정렬을 빠르게 하는 알고리즘이다. 그러나 버블정렬에 비해 빠를 뿐, 이름만큼 가장 빠른 정렬 알고리즘은 아니다. 퀵 정렬(Quick Sort) 알고리즘이란? 정렬 알고리 lordofkangs.tistory.com 이전 포스팅에서 재귀(recursive)함수를 활용한 퀵 정렬(Quick Sort)를 알아보았다. 일반적으로 퀵정렬은 재귀함수로 구현되지만 재귀함수는 한 가지 문제가 있다. 재귀는 메소드를 반복적으로 호출한다. 메소드는 본인의 영역이 있어야 하므로 호출할 때마다, Stack 영역의 메모리를 차지한다. 너무 많은 재귀함수 호출은 스택오버플로우를 발생시킨다. 그러므로 메모리의 효율적 관리를 위해 재귀함수가 아닌..