YANGORITHM

critical section과 semaphorecritical section은 두 개 이상의 스레드가 동시에 접근하는 경우 문제가 생길 수 있기 때문에 동시에 접근할 수 없는 영역이다semaphore는 특별한 형태의 시스템 객체이며 get, release 두 개 기능이 있다한 순간에 하나의 스레드만 semaphore를 얻을 수 있고, 나머지 스레드들은 대기 상태가 된다semaphore를 얻은 스레드는 critical section에 접근할 수 있다동기화두 개의 스레드가 같은 객체에 접근할 경우, 동시에 접근해서 오류가 발생한다동기화는 임계영역에 접근한 경우 공유 자원을 lock 하여 다른 스레드의 접근을 제어한다동기화를 잘못 구현하면 데드락에 빠질 수 있다synchronized자바에서는 임계영역에 동시..

문제https://www.acmicpc.net/problem/2630  풀이분할 정복으로 문제를 해결한다 (0~n, 0~n) 구역이 모두 같은 색이면 해당 색깔의 종이 수를 1 더하고 함수를 종료한다모두 같은 색이 아니라면 다음 4구역으로 나눈 후 각 구역에서 모두 같은 색인지 확인한다(0~n/2, 0~n/2)(n/2~n, 0~n/2)(0~n/2, 0/2~n)(n/2~n, n/2~n)  코드python1234567891011121314151617181920212223242526272829def solve(y, x, n):    global white, blue    reference_color = color_paper[y][x]     for i in range(y, y + n):        for j..

해당 게시물은 인프런 - "영리한 프로그래밍을 위한 알고리즘 강좌" 강의를 참고하여 작성한 글 입니다강의 링크문제그림에서 특정 좌표의 blob의 크기를 구하는 문제다Binary 이미지다각 픽셀은 image pixel 또는 background pixel이다서로 연결된 image pixel들을 blob이라고 부른다상하좌우 및 대각 방향으로도 연결된 것으로 간주한다위 그림에서는 총 4개의 blob이 있다문제를 정의하면 다음과 같다입력:N x N 크기의 2차원 그리드하나의 좌표 (x, y)출력:픽셀 (x, y)가 포함된 blob의 크기(x, y)가 어떤 blob에도 속하지 않는 경우에는 0Recursive Thinking이 문제를 Recursion을 이용해 해결해 본다수도 코드는 다음과 같다현재 픽셀이 imag..

문제https://www.acmicpc.net/problem/2477  풀이육각형의 빈 공간을 채워서 큰 직사각형의 넓이를 구한 후, 빈 공간의 직사각형의 넓이를 구해서 빼준다 입력에서 방향이 1번만 나오는 가로와 세로 길이가 가장 긴 길이다이를 이용해서 빈 공간을 채웠을 때 가장 큰 직사각형의 넓이를 구한다 빈 공간의 직사각형 넓이는 다음을 이용해 구한다가장 긴 가로 길이 인덱스에서 +3을 하면 빈 공간의 세로 길이 인덱스가 나온다가장 긴 세로 길이 인덱스에서 +3을 하면 빈 공간의 가로 길이가 나온다이를 이용해서 빈 공간에 직사각형의 넓이를 구할 수 있다  코드python12345678910111213141516171819202122232425directions = []lengths = []max_a..

문제https://www.acmicpc.net/problem/1489  풀이그리디 문제다 a[i]의 값보다 작은 수가 b에 존재한다면, 그 중에서 가장 큰 값을 이겨야 한다그래야 무승부를 최대한 적게 가져가면서 승리를 최대한 많이 가져가고, 점수를 최대한 많이 가져갈 수 있다 구현은 먼저 승리하는 경우의 점수를 더하고, 마지막에 무승부하는 경우에 점수를 더한다  코드python123456789101112131415161718192021222324252627282930313233343536result = 0csort_a = [0] * 1002csort_b = [0] * 1002 n = int(input())a = [int(x) for x in input().split()]b = [int(x) for x i..

문제https://www.acmicpc.net/problem/1071  풀이그리디 문제다사전 순으로 가장 앞선 것을 출력하기 위해 배열이 오름차순으로 정렬되어야 한다이를 위해 계수정렬을 통해 배열을 정렬한다 다음 규칙을 적용한다a[i] 값에 대하여1. a[i] + 1 값이 배열에 존재하면1-1. a[i] + 2 이상의 값 k가 배열 안에 존재하면, a[i] 값을 전부 출력하고 k를 출력한다1-2. a[i] + 2 이상의 값이 배열 안에 존재하지 않으면, a[i] + 1 값을 한번 출력한다 2. a[i] + 1 값의 배열에 존재하지 않는다면 a[i] 값을 전부 출력한다  코드python12345678910111213141516171819202122232425262728293031323334353637383..

문제https://www.acmicpc.net/problem/11729  풀이재귀를 이용해 문제를 해결한다1. 가장 큰 원판 n은 맨 밑에 있어야 하므로 n-1개를 첫 번째 장대에서 두 번째 장대로 옮긴다2. 원판 n을 첫 번째 장대에서 세 번째 장대로 옮긴다3. 원판 n-1개를 두 번째 장대에서 세 번째 장대로 옮긴다 원판을 옮겨야 하는 총 횟수는  2ⁿ-1 이다 재귀함수에서 2ⁿ으로 자기 자신을 호출하고 n == 1일 때 한 번만 호출하므로 -1을 해준다  코드python12345678910111213def hanoi(n, src, aux, dest):    if n == 1:        print(src, dest)    else:        hanoi(n - 1, src, dest, aux)..

Thread 우선순위Thread.MIN_PRIORITY = 1 ~ Thread.MAX_PRIORITY = 10디폴트 값은 Thread.NORMAL_PRIORTY = 5우선순위가 높은 스레드가 CPU 배분을 받을 확률이 높다public class PriorityThread extends Thread { @Override public void run() { int sum = 0; Thread t = Thread.currentThread(); System.out.println(t + " start"); for (int i = 0; i 결과는 다음과 같다반드시 그런건 아니지만 우선순위가 높은 스레드들이 먼저 끝나는 것을 볼 수 있다join()동시에 두..

문제https://www.acmicpc.net/problem/10872  풀이재귀를 이용해 해결한다  코드python123456789def factorial(n):    if 0 = n = 1:        return 1    return n * factorial(n - 1) n = int(input()) print(factorial(n)) Colored by Color Scriptercs

해당 게시물은 인프런 - "영리한 프로그래밍을 위한 알고리즘 강좌" 강의를 참고하여 작성한 글 입니다강의 링크Maze 미로찾기2차원 배열 입구(0,0)에서 출구(n-1,n-1)까지 찾아가는 문제흰색 칸은 이동할 수 있는 통로, 파란색 칸은 이동할 수 없는 벽이다Recursive Thinking순환적으로 생각해 문제를 해결한다현재 위치에서 출구까지 가는 경로가 있으려면 1) 현재 위치가 출구이거나 혹은 2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나Decision Problem답이 yes or no인 문제로 recursion을 생각해본다다음은 위 해결법의 수도코드다boolean findPath(x, y) if (x, y) is the exit // 현..