본문 바로가기

분류 전체보기146

[알고리즘] LIS : Longest Increasing Subsequnce 알고리즘 - DP 활용(최장 증가 부분 수열) LIS (최장 증가 부분 수열)란, 주어진 수열에서 오름차순으로 정렬된 가장 긴 부분 수열을 의미한다.  예를 들어, 아래의 그림처럼 수열 {10, 50, 20, 30, 10, 60} 이 있을 때,만들 수 있는 증가하는 수열은 { 10, 50, 60 } 그리고 { 10, 20, 30, 60 } 이다. (이때, 꼭 등차수열이거나 순서가 연속적일 필요는 없다.)이때, 가장 긴 증가하는 부분 수열(LIS)은 { 10, 20, 30, 60 } 임을 알 수 있다.  백준 11053번의 가장 긴 증가하는 부분 수열 의 예시로 알고리즘을 설명하겠다. https://www.acmicpc.net/problem/11053 1. DP 테이블 정의하기수열의 크기가 n인 배열이 입력으로 주어지면, 우리는 i 번째 원소의 LIS.. 2024. 8. 28.
[운영체제] IPC(Inter Process Communication) IPC(Inter-Process Communication) 은 커널영역(Kernel-mode)에서 하는 프로세스들 간의 통신이다.✔️ IPC가 필요한 이유프로세스는 각각 OS로부터 할당된 독립된 공간에서 실행된다.독립적으로 실행된다는 것은 다른 프로세스에게 영향을 받지 않는다고 말할 수 있다.(↔︎ 스레드는 프로세스 안에서 자원을 공유하므로 다른 스레드로부터 영향을 받는다. ) 각각 독립된 공간을 가진 프로세스 간의 통신을 해야하는 상황에서 필요한 통신이 IPC 통신이다. 프로세스는 커널 영역(Kernel-mode)에서 커널(Kernel)이 제공하는 IPC 설비를 통해 프로세스들 간에 통신(=IPC 통신)을 한다. ✔️IPC 모델(종류)➕ Shared Memory : 공유 메모리  Shared Memor.. 2024. 8. 28.
[백준] 2748 피보나치 수2 (자바) : DP [브론즈2] ✔️ 문제 설명 (펼치기)더보기문제피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.n=17일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다. 출력첫째 줄에 n번째 피보나치 수를 출력한다. 예제 입력 1 10예제 출력 1 55  ✔️ 문제 풀이이 문제의 경우 이전에 풀었던 .. 2024. 8. 27.
[운영체제] I/O 처리 방식 : Synchronous/Asynchronous & Blocking/Non-Blocking ✔️ Synchronous(동기) vs Asynchronous(비동기)►Synchronous : 요청이 들어온 순서에 맞게 하나씩 처리하는 방식으로, 요청 후 결과가 와야만 다음 작업이 이루어짐.              ↕︎►Asynchronous : 하나의 요청이 끝나기 전에 다른 요청을 동시에 처리할 수 있는 방식 ►Synchronous (동기)Synchronous(동기)의 경우 요청된 작업이 완료되어야 다음 작업을 수행한다.  ►Asynchronous (비동기)Asynchronous(비동기)의 경우 요청된 작업의 완료 여부를 따지지 않고 바로 다음 작업을 수행한다.호출되는 함수에게 callback을 전달해서 작업을 완료하면 실행하도록 한다.  ➕ Callback : 어떤 이벤트가 발생하거나 특정 .. 2024. 8. 27.
[백준] 11726 2xn 타일링 (자바) : DP [실버 3] 이번 포스팅에서는 DP 알고리즘 백준 11726 2xn 타일링 문제를 풀어보도록 하겠습니다. 상세한 설명 포함 !! ✔️ 문제 설명 (펼치기)더보기 문제2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. ✔️ 문제 풀이[의식의 흐름] 1. 처음에는 n이라는 숫자를 1의 배수의 합과 2의 배수의 합으로 나타내야 한다고 생각했다. 2. a+2b = n 이라는 방정식을 세웠다 .3. for 문을 활용해서 a와 b를 어떻게든 구할 수 있겠다. 4. n이 5일 때 2x1 타일이 1개이고 1x2 타일이 2개 일 때, 각 타일을 어디다가 배치할지에 대한 고민이 생긴다. 위의 그림처럼 타일을 배치하는거에 따.. 2024. 8. 26.
[백준] 2579 계단 오르기(자바) : DP [실버3] ✔️ 문제 설명더보기문제계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.예를 들어 와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.계단 오르는 데는 다음과 같은 규칙이 있다.계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.마지막 도착 계단은 반드시 밟아야 한다.따라서 첫 번째 .. 2024. 8. 26.