본문 바로가기
삽입 정렬 정렬되지 않은 부분의 첫 번째 요소를 정렬된 부분의 알맞은 위치에 삽입하는 알고리즘 * 타겟인 요소와 이전 위치(이미 정렬된)에 있는 요소들을 비교하여 알맞은 위치를 찾는다. 1. 타겟 요소와 바로 이전 요소와 비교 2. 타겟 요소가 작다면 이전 요소와 교환하고 아니면 종료 3. (교환했다면) 타겟 요소와 교환한 위치의 이전 요소와 비교 4. 타겟 요소가 작다면 교환하고 아니면 종료 5. 하나의 요소의 위치가 정해지면 원래 타겟 요소 다음 위치의 요소로 위 과정을 반복한다. 차례대로 비교/교환하므로 안정적이다. 거의 정렬된 경우에는 (best 상황) n번의 비교만 하고 교환하는 과정이 없으므로, O(N) 역순인 경우 (worst 상황) 타겟 요소가 이전 요소들 중에 제일 작을 것이므로, 타겟 요소를 맨 .. 2021. 11. 16.
선택 정렬 가장 작은 요소부터 선택해 맞는 위치로 옮기면서 순서대로 정렬하는 알고리즘 1. 주어진 배열의 요소들 중에서 최소값을 찾는다. 2. 해당 값을 배열의 맨 앞자리 요소와 교환한다. 3. 맨 앞자리를 뺀 나머지 요소들도 위와 같은 방법으로 교환한다. 즉, 정렬하지 않은 부분에서 최소값을 찾고, 그 값을 정렬하지 않은 부분의 첫 번째 요소와 교환하는 과정을 반복한다. 최소값을 찾으려고 비교한 횟수가 n-1, n-2, n-3, ... , 2, 1번이므로 시간 복잡도는 O(N^2)이다. 그리고 서로 떨어져 있는 요소를 교환하므로 안정적이지 않다. 2021. 11. 16.
버블 정렬 일반적으로 가장 기본적으로 생각할 수 있는 방법 인접한 두 요소의 대소 관계를 비교하여 교환을 반복! 앞(혹은 뒤)에서부터 차례대로 비교/교환이 이루어지기 때문에 안정정렬 맨 앞에서부터 현재 요소와 바로 다음 요소끼리 비교 현재 요소가 다음 요소보다 크다면 교환 다음 인덱스로 이동해 그 다음 요소와 비교/교환을 반복 배열의 요소 갯수가 n개라 한다면, 이웃한 요소끼리 비교/교환 작업을 처음부터 끝까지 한 번 진행하면, 가장 큰 요소가 맨 마지막 인덱스로 이동한다. 이 과정을 패스라고 한다.(n-1회 비교) 그리고선 남은 n-1개 요소로 비교/교환을 앞에서부터 끝까지 한 번 진행하면, 다음으로 큰 요소가 맨 마지막 직전 인덱스로 이동한다. (n-2회 비교) 이런 식으로 계속 진행하면, 이러한 작업이 총 n.. 2021. 11. 16.
(Java) 백준 1920 : 수 찾기 문제 : https://www.acmicpc.net/problem/1920 N개의 정수를 요소로 하는 배열을 M번 탐색하는 문제 순차탐색 : 시간복잡도 O(N * M) = 100억. 시간제한 1초당 1억 연산 횟수 정도로 보기 때문에 시간 제한에 걸린다. 이진탐색: 시간복잡도 O(M * logN) import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int[] intArr1 = new int[n]; for(int i=0; i 2021. 11. 12.
자바 배열 정렬 (Comparable / Comparator 차이) 둘 다 "객체를 특정 기준으로 비교할 수 있도록 한다." Comparable - Comparable 인터페이스를 쓰려면 compareTo(T o) 구현 - 자기 자신과 매개변수 (T클래스 자료형 o) 객체를 비교 - lang패키지에 있어 import 필요 x Comparator - Comparator 인터페이스를 쓰려면 compare(T o1, T o2) 구현 - 두 매개변수 객체를 비교 - util패키지에 있어 import 필요 - Comparator 인터페이스를 구현하는 클래스는 비교하는 두 객체와 아무 관련이 없고, compare()만 overriding해서 비교할 때만 사용하려고 하는 것이다. 그래서 Comparator을 구현하는 익명 객체를 생성하여 주로 사용한다. - Comparator을 구현.. 2021. 11. 12.
Java 기본 10 - 상속 자식클래스에서 부모클래스의 메소드를 오버라이딩할 때 주의할 점이 있다. - 접근 제한을 변경할 시, 부모클래스에서 보다 더 넓게만 가능하다. class Parent { public method() {..} } class Child extends Parent { @Override method() {...} // compile error } - 더 넓은 범위의 checked exception을 throw할 수 없다. unchecked exception(Runtime Exception)은 상관없다. -> 부모클래스에서 예외를 명시하지 않았으면, 자식클래스에서는 unchecked exception만 새로 명시할 수 있다. -> 부모클래스에서 checked exception을 명시했으면, 자식클래스에서는 같은 e.. 2021. 11. 11.
Java 기본 9 - 중첩 클래스/중첩 인터페이스/익명 클래스 중첩 클래스 특정 클래스와 관계를 맺을 경우는 관계 클래스를 클래스 내부에 선언하는 것이 좋다. 두 클래스(Outer, Inner)의 멤버들을 서로 쉽게 접근할 수 있다. 한 클래스(A)에서만 쓰이는 클래스(B)의 경우, 클래스(B)를 클래스(A)에 내장하도록 하는 것이 가독성, 유지보수 측면 모두에서 좋다. 즉, 외부에는 불필요한 클래스를 감춤으로써 코드의 복잡성을 줄일 수 있다. (캡슐화) 1) 멤버 클래스 1-1) 인스턴스 멤버 클래스 - 외부 클래스 객체를 생성한 후 내부 클래스 객체를 생성하여 사용 - 인스턴스가 생성되어야만 접근할 수 있기 때문에 static member 선언 불가 class Outer { class Inner {...} } //외부클래스 객체 생성, 컴파일 시 Outer.cl.. 2021. 11. 10.
for-each문과 for문의 차이 (for문, 향상된 for문에 대한 기본적인 설명은 생략) LinkedList[] lists = new LinkedList[size]; for(int i=0; i 2021. 11. 3.
싱글톤 Singleton Singleton패턴이란? - 인스턴스를 '한 번'만 생성하고, 이를 여러 군데에서 공유하면서 사용하도록 하는 디자인 패턴 장단점 https://tecoble.techcourse.co.kr/post/2020-11-07-singleton/ Singleton 구현 방식 https://jobjava00.github.io/language/java/basic/singleton/ 2021. 10. 20.
숫자 야구게임 1 어렸을 때 학교에서 했던 숫자 야구게임을 Java로 구현해보고자 한다. 4개의 숫자를 중복없이 0~9까지 고르고, 상대방이 4개의 숫자를 부른다. 이 때, 같은 숫자가 있을 때 위치가 다르면 1ball, 위치까지 같으면 1strike, 같은 숫자가 없다면 out이다. 이를 토대로 처음에 어떤 4개의 숫자를 어디에 위치시켰는지 추론해나가는 게임이다. 기본 컨셉 게임이 시작되면 컴퓨터가 0~9까지 숫자 중 4개를 중복없이 순서대로 뽑는다. 그 뒤, 유저가 똑같이 0~9까지 숫자 중 4개를 중복없이 적으면, 컴퓨터가 뽑은 4개의 숫자와 비교한다. 비교한 결과(strike, ball갯수, out 여부)값을 리턴해주고, 유저는 결과를 보고 다시 입력한다. 이러한 과정을 반복한 뒤, 4개의 숫자와 위치까지 전부 맞.. 2021. 6. 1.

티스토리툴바