TIL 1일차

알고리즘

---

이진 탐색

이진 탐색은 여러가지 탐색 알고리즘 중에 하나입니다. 일단 이진 탐색을 하기 위해서는 Data들이 정렬이 되어 있어야 합니다. 대학교때에 술게임중에 업다운게임을 생각하시면 조금 쉽게 생각할 수 있을 것 같습니다.

예를 들어 보겠습니다.

이 알고리즘은 계속 범위가 반씩 줄어들기 때문에 빅오 표기법으로 표기하자면 O(logN)의 시간복잡도를 가지고 있습니다.

주의사항으로는 아까 위에서 기술했던 것처럼 범위를 좁혀 나가는 것이기 때문에 데이터가 정렬이 되어 있어야 한다는 점입니다.

다음 알고리즘을 파이썬으로 작성한 코드입니다.
값이 없을 시에는 -1을 반환하게 만들었습니다.
값이 있을 시에는 해당 값의 인덱스를 반환하게 됩니다.

data = [1,3,5,9,11,14,18,32,54]

def binarySearch(target):
    start = 0
    end = len(data)
    # 존재하지 않으면 -1을 출력
    answer = -1

    while start <= end:

        mid = (start + end) // 2
        if data[mid] == target:
            answer = mid
            break
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid - 1

    return answer

print(binarySearch(11))
print(binarySearch(12))

##출력 
4
-1

이진 탐색 알고리즘을 이용한 문제는 코딩테스트에서도 자주 볼 수 있습니다.

프로그래머스에서 예산이라는 문제가 있습니다. 이진 탐색을 이용한 문제인데요..
한번 풀어보도록 하겠습니다.

def solution(budgets, M):
    answer = 0
    start = 0
    end = max(budgets)
    mid = 0
    while (start <= end):
        mid = (start + end) // 2
        sumBud = sumBudget(budgets, mid)
        if(sumBud > M):
            end = mid - 1
        elif sumBud == M:
            return mid
        else:
            answer = mid
            start = mid + 1
    return answer

def sumBudget(budgets, limit):
    answer = 0
    for i in budgets:
        if(i <= limit): 
            answer += i
        else: 
            answer += limit
    return answer

다음과 같은 코드로 문제를 풀 수 있습니다.

자바의 스레드

자바의 스레드를 어느정도 알고 있다고 생각했지만, 막상 짜보려고 하니 잘 되지 않았다.
잘 정리를 해서 머리속에 기억해 두기 위해서 기록을 해 둡니다.

스레드는 프로세스 내에서 실행되는 프로세스의 실행 흐름입니다.
스레드는 각각 stack 만 할당받고, 나머지 부분은 프로세스 내의 다른 스레드와 공유를 합니다.

자바에서 Thread 클래스는 java.lang 패키지 안에 존재합니다.

스레드는 두가지 방법으로 구현을 할 수 있습니다.
1. Thread 클래스를 extends 해서 구현하는 방법
2. Runnable 인터페이스를 implements 해서 구현하는 방법
3. 람다식을 이용해 재정의 하는 방법

Thread thread = new Thread(() -> {// 코드 작성});

2번을 익명함수 방식으로 구현하면

Thread thread = new Thread( new Runnable() {
  public void run() {
    // 코드 
  }
});

다음과 같이 간편하게 구현을 할 수도 있습니다.

세개 다 결국은 run() 이라는 메소드를 재정의 해서 사용을 하게 됩니다.
밑은 첫번째 방법을 이용하여 스레드의 기본적인 예를 구현한 것입니다.

package Main;

public class Test extends Thread{
	int count = 1;
	
	public Test(int num) {
		count = num;
	}
	
	public void run() {
		System.out.println(count + "번째 스레드 동작");
		
	}

	public static void main(String[] args) {
		for(int i=0; i < 10; i++) {
			Thread t = new Test(i);
			t.start();
		}
		System.out.println("메인 문 동작 완료");
	}

}

thread를 실행시키면 run 함수 내부에 있는 내용이 실행되게 됩니다. 스레드는 실행 순서가 보장이 되지 않습니다. 위 코드의 실행 결과는 실행 할 때마다 달라지고, 0부터 9까지 실행이 되지 않고 아래 사진과 같은 순서대로 실행됩니다.

그렇기 때문에 Thread는 공유 자원을 사용할 때에 의도치 않은 에러가 일어날 수 있습니다. Synchronize 키워드를 사용하여 이러한 문제를 해결 할 수 있는데, 다음에 정리하여 올리겠습니다.

스레드는 5가지의 상태를 가지고 있습니다.

New -> 스레드가 생성된 상태
Runnable -> 실행 중 또는 실행이 가능한 상태
Blocked -> Lock 이 풀릴 때까지 기다리는 상태
Waiting -> 끝나진 않았지만, 실행이 가능하지 않은 일시정지 상태
Terminated -> 스레드가 종료된 상태

스레드의 공부는 여기까지 마치고, 내일은 Thread를 이용한 소켓 채팅 프로그램을 만들어보면서 더욱 배우고 내용을 보완하려고 합니다.

프로그래머스 타일 장식물

파일 장식물 알고리즘은 부분부분 나눠서 해결하는 문제이다.
재귀함수는 같은 연산을 많이 하게 되므로 메모리제이션이라는 기법을 사용하였다..

memo = [-1] * 90
memo[0] = 1
memo[1] = 1
def select(num):
    if memo[num] != -1:
        return memo[num]
    else:
        memo[num] = select(num-1) + select(num -2)
        return memo[num]

def solution(N):
    return 2*(select(N)+ select(N-1))