순간을 기록으로

삽입정렬이란 현재 원소를 타깃으로 한다. 그리고 현재 원소의 이전 원소들을 비교해서 이전 원소가 크면 이전 원소를 현재 원소로 밀어준다. 그리고 이전 원소가 크지 않을 때 타깃 원소를 넣어주는 정렬 방법이다. 삽입 정렬 특징 데이터를 비교하면서 정렬하므로 비교 정렬이다. 데이터 비교할 때 추가적인 공간을 요구하지 않으므로 제자리 정렬(in-place sort)이다. 삽입정렬 장점 제자리 정렬이라서 추가적인 메모리 소모가 적다. 만약 거의 정렬된 상태라면 매우 효율적이다. 즉 최선의 경우 시간 복잡도는 O(N) 안장 정렬이 가능하다. 삽입정렬 단점 정렬이 역순으로 되어있으면 매우 비효율적이다. 즉 최악의 경우 시간 복잡도는 O(N^2) 데이터의 정렬 상태에 따라 성능 편차가 크다. 코드 import jav..

문제 유형: 스택 바구니가 한쪽으로만 데이터를 넣는 스택 모양 풀이법 우선 스택 문제니 Stack을 선언한다. 그리고 크레인의 작동 위치 횟수만큼 반복되므로 for-each 문을 사용한다. 크레인의 좌우 위치 값은 2차원 board 배열에서 열에 해당되므로 board [][move-1]로 넣어준다. 인덱스의 이므로 -1을 해줘야 한다. 그리고 크레인이 내려가는 모양은 for문으로 구현한다. i가 증가하면서 만약 인형이 없으면(=원소 값이 0이면) 내려가게 되고, 인형이 있으면 스택 바구니 상단과 비교해 같으면 pop()을하고 값을 2 증가시킨다. 만약 같지 않다면 push()를 이용해 바구니에 넣는다. 그리고 인형을 뺏으니 보드에 인형이 있던 위치에 0을 넣는다. 그리고 크레인은 아래로 안 내려가므로 b..

느낀 점 재귀함수란 함수 안에서 자시 자신을 호출하는 함수를 말한다. 이렇게 함수가 자기 자신을 호출하게 되면 끊임 없이 호출이 계속되는데 이렇게 되면 스택오버플로우가 발생하게된다. 따라서 재귀함수는 반드시 1.탈출 조건 2. 자신 호출이 있어야한다. 보통 구조는 다음과 같이 if-else 구조를 가진다. public void function(int n) { if(탈출 조건){ return; } else { function(n-1); } } public class Main { public void DFS(int n) { if (n == 0){ return; } else { DFS(n/2); System.out.print(n%2); } } public static void main(String[] args..

오늘 푼 문제는 버플 정렬 구현 문제이다. 구현이 쉬운 정렬 중 하나다. 버블 정렬은 정렬되는 과정에서 원소 값이 교환하는게 수면위로 올라가는 거품의 이동과 비슷하다고 하여 그렇게 지어졌다고 한다. 버블정렬(=거품정렬, bubble sorting): 두 개의 인접한 원소의 값을 비교하여 정렬하는 방식. 시간 복잡도는 이중 for문을 돌기 때문에 O(N^2)이다. 버블 정렬 특징 데이터를 비교하면서 찾기 때문에 비교 정렬. 정렬 도중 추가적인 공간을 필요로 하지 않기에 제자리 정렬(in-place sort) 참고로 두 원소의 값을 교환하는 과정에 생성하는 임시 변수 temp는 충분히 무시할 수 있도록 작기에 제자리 정렬에 영향을 주지 않는다. 앞에서부터 차례대로 데이터를 비교하기 때문에 '안정 정렬'이다...

느낀 점 Stack의 대표적인 문제는 괄호 문제다. 닫는 괄호(')')이면 액션을 취하고 닫는 괄호(')') 이외의 문자(여는 괄호, 다른 문자)는 stack에 넣어주는 게 포인트. 알아가는 것 스택도 제네릭 타입이어서 for-each문으로 접근할 수 있다. stack.pop()의 리턴 값은 제거된 원소이다. 스택은 stack.get(i) 메서드처럼 인덱스로 접근할 수 있다. import java.util.Scanner; import java.util.Stack; /* * 수도코드 * 문자열을 한 문자씩 탐색한다 * 만약 문자가 ')'이라면 가장 가까운 '('까지 스택에 쌓인 문자열을 제거한다. * 만약 ')'이외의 문자라면 스택에 추가한다. * * 스택의 사이즈만큼 반복한다. * 인덱스를 이용해서 스택..

안녕하세요. 이번에는 멀티쓰레드 환경에서도 안정적인 다양한 싱글톤 패턴을 구현해보겠습니다. 가장 기본적인 싱글톤 패턴 public class Settings { private static Settings instance; private Settings() { }// private 생성자 public static Settings getInstance() {// static 메소드 if (instance == null) { instance = new Settings(); } return instance; } } 지난 포스팅 때 배운 가장 기본적인 싱글톤 패턴입니다. private 생성자를 이용해 외부에서 객체 생성을 막습니다. 직접 객체 생성대신 메소드를 통해 간접적으로 인스턴스를 제공해주는 static 메..

안녕하세요. 오늘은 싱클톤 패턴에 대해 알아보겠습니다. 싱글톤 패턴 싱글톤 패턴이란 인스턴스를 오직 한 개만 제공하는 클래스를 만드는 패턴입니다. 인스턴스가 무조건 한개여만 됩니다. 예를들어 오버워치를 하고 있는데 마우스 속도가 너무 느린거에요. 셋팅창을 열어 마우스 감도를 90으로 올렸어요. 그런데 이번에는 너무 마우스가 빨라서 속도를 다시 줄이려 마우스 감도를 60으로 줄이려고해요. 이때 만약 셋팅창 인스턴스가 여러개면 어떤 셋팅창에는 마우스 감도가 90이고 어떤 채팅창에는 마우스 감도가 60이라서 문제가 발생하게되죠. 이럴 때 싱글톤 패턴을 이용해서 문제를 해결하게 됩니다. 코드로 살펴보기 우선 App.java와 Settings.java파일을 만듭니다. public class Settings { }..

문제 https://www.acmicpc.net/problem/11729 코드 리뷰 맨 처음에 System.out.println()으로 여러번 출력을 하다가 시간초과가 났다. 그래서 StringBuilder를 사용하여 문자열을 계속 붙여준뒤에 메인함수 마지막에서 System.out.println()을 한 번 호출했다. 입력은 BufferedReader를 사용했다. 변수 num에는 원판의 수를 입력받아 저장한다. sb는 메인 메소드 안에서 선언하지 않고 한 단계 위에서 선언해서 다른 메소드에서도 접근할 수 있도록 했다. 변수 count에는 원판의 총 이동 횟수를 저장한다. 하노이 탑에서 원판의 총 이동횟수는 원판의 갯수가 n이라 할 때 2^n -1이다. 이때 Math.pow()를 사용하는데 입력값과 반환값..