L.O.K

퀵 정렬(Quick Sort)은 이름 그대로 정렬을 빠르게 하는 알고리즘이다. 그러나 버블정렬에 비해 빠를 뿐, 이름만큼 가장 빠른 정렬 알고리즘은 아니다. 퀵 정렬(Quick Sort) 알고리즘이란? 정렬 알고리즘은 두 가지 원칙에서 비롯된다. 1. 두 수의 대소를 비교한다. 2. 두 수의 위치를 교환한다. '비교' 와 '교환'은 정렬의 근본개념이다. 비교와 교환을 어떻게 하느냐에 따라 다양한 정렬 알고리즘이 만들어진다. 퀵정렬의 비교, 교환 방식을 이해하기 위해 단순한 버블정렬과 비교하여 설명하겠다. 버블정렬은 우측 끝부터 두 수를 비교하는 방식이다. 그래서 포인터가 우측에서 좌측으로 이동하면서 두 수를 비교하여 작은 값을 좌측으로 교환한다.(오름차순) 버블정렬은 동일한 위치에서 비교와 교환이 일어난..

스프링은 '프레임워크(FrameWork)'이다. 프레임워크가 개발자의 작업을 도와준다는 말을 많이 들어봤을 것이다. 어떻게 도와준다는 말일까? '프레임워크'란 무엇인가? 프레임워크를 사용하지 않으면 개발자의 소스코드가 프로그램의 흐름을 제어한다. User user = new User("22231123l","민구","1111"); // user 객체 생성 ConnectionMaker connectionMaker = new AConnectionMaker(); // connectionMaker 객체 생성 UserDao userDao = new UserDao(connectionMaker); // userDao객체 생성 및 userDao와 connectionMaker 간의 관계설정 어떤 객체를 생성할지 어떤 객체..

버블정렬은 가장 쉽고 이해하기 쉬운 정렬이다. 그러나 시간복잡도가 O(n2)이어서 효율이 좋지 않다. 7개의 수를 일차원 배열에 저장하였다. 이제 버블정렬을 사용하여 오름차순으로 바꾸어 보자. 버블정렬은 우측 끝부터 두 개씩 대소를 비교하여 위치를 바꾸는 방법이다. 모든 비교가 끝났을 때, 맨 좌측에는 오름차순일 경우 가장 작은 수, 내림차순인 경우 가장 큰 수가 자리잡는다. 이렇게 반복하여 좌측을 하나씩 오름차순 혹은 내림차순으로 정렬하는 방식이 버블정렬이다. 그러나 버블정렬은 효율이 좋지 않다. n개의 수를 정렬한다고 가정해보자. 1회전 : n-1 번 비교 2회전 : n-2 번 비교 3회전 : n-3 번 비교 . . n-1회전 : 1번 비교 (n-1) + (n-2) + (n-3) + .... + 2 ..

2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 1. 문제 추상화 N개의 수가 주어졌을 때, 오름차순으로 정렬하시오. 2. 알고리즘 ( 아래 포스팅에 정리해두었으니 참고바랍니다. ) [ JAVA ] 버블정렬 향상 시키기 버블정렬은 가장 쉽고 이해하기 쉬운 정렬이다. 그러나 시간복잡도가 O(n2)이어서 효율이 좋지 않다. 그러니 일반적인 버블정렬과 버블정렬의 효율을 높이는 방법 두 가지를 소개하겠다. 7개의 lordofkangs.tistory.com 3. 코드 구현 3-1) 버블정렬 코드 //..

Clean Code 『CLEAN CODE(클린 코드)』은 오브젝트 멘토(OBJECT MENTOR)의 동료들과 힘을 모아 ‘개발하며’ 클린 코드를 만드는 최상의 애자일 기법을 소개하고 있다. 소프트웨어 장인 정신의 가치를 심어 주며 book.naver.com switch문은 클린코드에 부적합하다. 이유는 크게 두 가지이다. 1. 여러가지 case가 있어 한 가지 함수에 다양한 작업이 포함될 수 있다. 2. 작게 만들 수 없다. 함수는 작고 한 가지 작업만 수행되어야 한다고 믿는 로버튼 C. 마틴에게 swith문은 부적합한 문법이다. 사용하기 어려운 switch문 // 월급 계산법 public Employee caculatePay(Employee e) { switch(e.type) { case COMMISS..

1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 1. 문제 추상화 "666"이 들어간 수를 작은 순서대로 시리즈 넘버로 한다. N번째 시리즈의 번호를 구하라. 2. 알고리즘 API를 이용하면 굉장히 쉽게 풀 수 있는 문제다. String 객체의 contains() 메소드를 이용하여, 작은 수부터 666이 들어간 모든 경우의 수를 조사하면 된다. [ 브루트 포스 ] 그러나 나는 규칙성을 찾는 도중 재귀함수 냄새를 맡았고 재귀함수로 풀려다가 실패했다. contains() 메소드를 알고 있었지만 기억하지 못했다...

Clean Code 『CLEAN CODE(클린 코드)』은 오브젝트 멘토(OBJECT MENTOR)의 동료들과 힘을 모아 ‘개발하며’ 클린 코드를 만드는 최상의 애자일 기법을 소개하고 있다. 소프트웨어 장인 정신의 가치를 심어 주며 book.naver.com '클린코드'의 저자 로버트 마틴은 말한다. 함수는 작은 함수가 좋다고 확신한다. 작은 함수는 한 가지 기능만 한다. 만약 함수가 두 가지 기능으로 설명된다면 이미 큰 함수이다. 여기서 한 가지 기능이란, 한 가지 '추상화'를 의미한다. 한 가지 추상화 아래 코드는 회원가입을 수행하는 함수이다. 회원가입 버튼을 누르면 해당 함수가 실행된다. 회원가입은 세 가지 작업으로 세분화된다. 1. ID 유효성 검사 2. DB에 저장 3. 페이지 전환 정리하면, 한..

1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 1. 문제 추상화 M X N 크기의 보드를 8X8로 잘라 체스판을 만들려 한다. M X N의 보드는 격자마다 무작위로 색칠되어 있을 때, 어느 부분을 8X8로 잘라야 최소한의 색칠로 8X8체스판을 만들 수 있을까? ( 체스판은 격자간 색깔이 겹치면 안 된다. ) 2. 알고리즘 알고리즘 구상은 쉬우나 사소한 조건을 놓칠 수 있어 코드 구현이 만만치 않은 문제이다. 나는 두 가지 방법으로 풀었다. 첫 번째 방법은 나의 알고리즘이고 두 번째 방법은 인터넷에서 ..

7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 1. 문제 추상화 A(x, y), B(p, q)에서 x > p 그리고 y > q 이면 A가 B보다 크다고 할 때,입력된 값들의 크기 순위를 매겨라. 순위는 자신보다 큰 수의 개수 + 1이다. 2. 알고리즘 풀이는 쉽지만 문제 뉘앙스가 헷갈릴 여지가 있다. 상식적으로 몸무게가 같고 키가 크면 덩치가 더 크다 말할 수 있다. 그러나 여기서는 아니다. 키와 몸무게가 둘 다 커야 덩치가 큰거다. 문제를 풀 때는 상식이 아닌 조건으로 풀어야 한다. 1. 이차..

2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 1. 문제 추상화 임의의 값 M이 주어질 때, M의 생성자(N) 중 최소값을 구하라. ( 생성자(N)는 생성자와 생성자 각 자리 수의 합이 M과 같은 수를 의미한다. ) 2. 알고리즘 생성자(N)의 각 자리수의 합을 SUM이라 하겠다. M = N + SUM 이므로 M > N이다. 그러므로 가장 쉬운 방법은 1부터 M까지 모든 경우의 수를 조사하는 방법이다. (브루트 포스) 그러나 M은 1 ≤ M ≤ 1,000,000 이므로 경우의 수..