이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Merge Sort(병합 정렬)분할 정복법(Merge Sort, Quick Sort)분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할정복 : 각각의 작은 문제를 순환적으로 해결합병 : 작은 문제의 해를 합하여(Merge) 원래 문제에 대한 해를 구함 1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.3. 각 부분의 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.4. 두 부분의 리스트를 다시 하나의 정렬된 리스트로 합병한다. 의사코드 Merge Sort(A[], p, r) { // 배열 A[p...
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Bubble Sort(거품 정렬)거품 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 로 상당히 느리지만,코드가 단순하기 때문에 자주 사용된다. 출처 : 위키 백과 예제[4, 54, 2, 8, 63, 7, 55, 56] [4, 2, 8, 54, 7, 55, 56, 63] [2, 4, 8, 7, 54, 55, 56, 63] [4, 2, 54, 8, 63, 7, 55, 56] [2, 4, 8, 54, 7, 55, 56, 63] [2, 4, 7, 8, 54, 55, 56, 63]pass3[4, 2, 8, 54, 63, 7, 55, 56] [2, 4, 8, 7, 54, 55, 56, 63]pass 2[4, 2..
이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Selection Sort(선택 정렬)선택 정렬은 제자리 알고리즘의 하나로, 다음과 같은 순서로 이루어진다.1. 주어진 리스트 중에 최솟값 or 최대값을 찾는다.2. 그 값을 맨 앞 or 맨 뒤에 위치한 값과 교체한다.3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 비교하는 것이 상수 시간에 이루어진다는 가정 아래, n 개의 주어진 리스트를 이와 같은 방법으로 정렬하는 데에는 Θ(n2) 만큼의 시간이 걸린다. 출처 : 위키 백과 예제 [4, 54, 2, 8, 63, 7, 55, 56] -> initial array [4, 54, 2, 8, 56, 7, 55, 63] -> after 1st swap [4,..
문제 2016년 1월 1일은 금요일입니다.2016년 A월 B일은 무슨 요일일까요?두 수 A,B를 입력받아 A월 B일이 무슨 요일인지 출력하는 getDayName 함수를 완성하세요.요일의 이름은 일요일부터 토요일까지 각각 SUN, MON, TUE, WED, THU, FRI, SAT 를 출력해주면 됩니다. 예를 들어 A=5, B=24가 입력된다면 5월 24일은 화요일이므로 TUE를 반환하면 됩니다. 풀이(Java) class TryHelloWorld { public String getDayName(int a, int b) { String answer = ""; String[] week = {"FRI","SAT","SUN","MON","TUE","WED","THU"}; int[] month = {31,29,3..
문제 reverseInt 메소드는 int형 n을 매개변수로 입력받습니다.n에 나타나는 숫자를 큰것부터 작은 순으로 정렬한 새로운 정수를 리턴해주세요. 예를 들어 n이 118372면 873211 을 리턴하면 됩니다.n은 양의 정수 입니다. 풀이(Java) public class ReverseInt { public int reverseInt(int n){ String numStr = String.valueOf(n); int [] arr = new int[numStr.length()]; int temp = 0; int result = 0; for(int i=0; i
문제 소수 찾기 - Level2 numberOfPrime 메소드는 정수 n을 매개변수로 입력받습니다. 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하도록 numberOfPrime 메소드를 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 10을 입력받았다면, 1부터 10사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환 5를 입력 받았다면, 1부터 5사이의 소수는 [2,3,5] 3개가 존재하므로 3을 반환 풀이(Java) class NumOfPrime { int numberOfPrime(int n) { int result = 0; // 함수를 완성하세요. for(int i=2; i
1. Framework- 특정 형태의 소프트웨어 문제를 해결하기 위해 상호 협력하는 ClassFrame 와 InterfaceFrame의 집합- 특정한 틀을 만들어 놓고 거기에 살을 붙여 놓음으로써 프로그램을 만들어 작업시간을 줄여줍니다.- Framework는 특정 개념들의 추상화를 제공하는 여러 클래스나 컴포넌로 구성됩니다.- Framework는 이렇게 추상적인 개념들이 문제를 해결하기 위해 같이 작업하는 방법을 의미합니다.- Framework 컴포넌트 들은 재사용이 가능합니다.- Framework는 좀더 높은 수준에서 패턴을 조작합니다. Framewokr가 중요한 이유객체지향 개발을 하게 되면서 개발자의 취향에 따라 다양한 프로그램이 나오게 되었습니다.개발에 투입되는 개발자도 점점 늘어남에 따라 전체 ..
1. JavaJava는 네트워크 상에서 쓸 수 있도록 미국의 선 마이크로시스템즈가 1995년에 개발한 객체 지향 프로그래밍 언어, 2010년 썬이 오라클에 인수됨Java의 특징a. 자바가상머신(JVM)만 설치하면 컴퓨터의 운영체제에 상관없이 작동한다.(운영체제에 독립적)b. 기본 자료형을 제외한 모든 요소들이 객체로 표현c. 객체 지향 개념의 특징인 캡슐화, 상속, 다형성이 잘 적용된 언어d. Garbage Collector를 통한 자동적인 메모리 관리e. 멀티쓰레드(Multi-thread)를 지원 Garbage Collection(가비지 컬렉션)- 시스템에서 더 이상 사용하지 않는 동적 할당된 메모리 블럭을 찾아 자동으로 다시 사용 가능한 자원으로 회수하는 것입니다.- 시스템에서 가비지컬렉션을 수행하는..
1. OOP란? (객체지향 프로그래밍)OOP란 Object-Oriented Programming의 약어로써 객체지향 프로그래밍을 의미"데이터"가 아닌 데이터와 행위로 구성된 "객체"가 중심인 프로그래밍 패러다임입니다. OOP의 특징a. 객체지향 프로그래밍은 코드의 재사용성이 높다.b. 코드의 변경이 용이c. 직관적인 코드 분석d. 개발 속도 향상e. 상속을 통한 장점 극대화 2. OOP의 3대 조건A. 캡슐화객체의 속성(필드값)과 동작(메소드)를 하나로 묶는 것입니다.데이터의 일부를 감추어 외부와의 상호작용은 메소드를 통하여 할 수 있게 한다. 데이터를 모듈화 한다는 의미가 있는데, 캡슐화를 잘하려면 객체에 책임을 적절히 분배해야합니다. 데이터를 객체 안에 포함시키고, 그 데이터에 대한 직접적인 접근을 ..