분류 전체보기
-
[백준/BOJ] 1149번 RGB거리 (C++)알고리즘 문제풀이/백준 2020. 12. 20. 12:46
www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net DP 유형의 문제입니다. 입력값의 각 열은 R, G, B 색깔, 행은 집의 수를 의미합니다. 문제의 조건은 결국 같은 색이 인접하면 안된다는 것을 의미합니다. 따라서 n번째 집의 색이 R, G, B 였을 때 n-1의 색이 다른 색이 되게끔, 최소값을 가지게끔 만들면 됩니다. 그런데 색깔에 따라 점화식을 만들어내야하므로, 2차원 dp배열을 이용하면 다음과 같은 점화식을 만들 수 있습니다. d..
-
[OS] 프로세스 동기화와 상호배제 (Process Synchronization and Mutual Exclusion) - ③Computer Science/운영체제 2020. 12. 19. 20:42
Language Level Solutions Monitor(모니터) 공유데이터와 임계 영역의 집합 wait(), signal() 연산 존재 사용이 쉽고, Deadlock(교착상태) 등 에러 발생 가능성이 낮음 Monitor의 구조 Entry Queue(진입 큐) : 모니터 내의 procedure(function) 수 만큼 존재 Mutual Exclusion(상호 배제) : 모니터 내에는 항상 하나의 프로세스만 진입 가능 Information Hiding(정보 은폐) : 공유 데이터는 모니터 내의 프로세스만 접근 가능 Condition Queue(조건 큐) : 모니터 내의 특정 이벤트를 기다리는 프로세스가 대기 Signaler Queue(신호 제공자 큐) : 모니터에 항상 하나의 신호 제공자 큐가 존재, ..
-
[OS] 프로세스 동기화와 상호배제 (Process Synchronization and Mutual Exclusion) - ①Computer Science/운영체제 2020. 12. 19. 20:40
SW + HW Solutions Process Synchronization(동기화) 여러 개의 프로세스들이 존재하는 다중 프로그래밍 시스템에서 프로세스들은 서로 독립적으로 동작합니다. 공유 자원 혹은 데이터가 있을 때, 각각의 독립된 프로세스가 그 자원에 동시에 접근한다면? 다시 말해서 병행 수행중인 비동기적 프로세스들이 공유 자원에 동시 접근할 때 문제가 발생할 수 있습니다! 이를 막기 위해 동기화가 필요한데, 동기화는 다음과 같이 정리할 수 있습니다. 프로세스들이 서로 동작을 맞추는 것 프로세스들이 서로 정보를 공유하는 것 Mutual Exclusion(상호 배제) 상호배제란 둘 이상의 프로세스가 동시에 임계 영역에 진입하는 것을 막는 것을 의미합니다. 이러한 상호배제를 위해서 고려해야 할 3가지 기..
-
[백준/BOJ] 14889번 스타트와 링크 (C++)알고리즘 문제풀이/백준 2020. 12. 19. 17:42
www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 삼성 역량 테스트 기출 문제 : DFS(조합) or 순열 next_permutation을 이용하여 팀을 나눠줍니다. (예를들어 0, 0, 1, 1 로 시작) 0은 start팀, 1은 link팀으로 나누어 각각의 합을 구하고 두 합의 차이의 최소값을 찾으면 간단히 해결할 수 있습니다. DFS를 이용하는 경우 조합을 구하여 true는 start팀, false는 link팀으로 나누어 동일하게 해결할 수 있습니다. #include #inc..
-
[백준/BOJ] 2579번 계단 오르기 (C++)알고리즘 문제풀이/백준 2020. 12. 19. 17:14
www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net DP 유형의 문제입니다. 마지막 계단을 오를 때 다음과 같이 두가지로 경우로 나눠서 생각합니다. 연속 O 도착 연속 X 도착 연속 O 도착인 경우, 그 전 계단을 오른 건 무조건 연속 X 입니다. 왜냐하면 연속이 되어버리면 3계단 연속이 되어버려 문제의 조건을 만족할 수 없게 됩니다. 그래서 연속 O 도착의 점화식은 다음과 같이 나타낼 수 있습니다. dp[n][1] = dp[i - 1][0] + v[i] 그러나 연속 X 도..
-
[백준/BOJ] 2133번 타일 채우기 (C++)알고리즘 문제풀이/백준 2020. 12. 19. 00:03
www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net DP 유형으로 이전에 풀었던 타일링 문제와 비슷한데, 살짝 어려워진 유형의 문제였습니다. 맨 오른쪽 끝에 하나를 놓는 경우 2*d[n - 1], 맨 오른쪽 끝에 두개를 놓는 경우 3*d[n - 2]로 다음과 같은 점화식을 도출해낼 수 있습니다. d[n] = 2*d[n - 1] + 3*d[n - 2] 그러나 주의할 점이 있는데 n = 4일 때 다음과 같이 새로운 모양이 생깁니다. 이러한 새로운 모양이 n이 4부터 짝수일 때마다 2개씩 생기는게, 이러한 경우를 고려하면 다음과 같은 점화식을 도출해낼 수 있습니다. d[n] =..
-
[백준/BOJ] 11727번 2×n 타일링 2 (C++)알고리즘 문제풀이/백준 2020. 12. 19. 00:02
www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 11726번과 거의 비슷한 DP 문제입니다. 맨 오른쪽 끝에 하나를 놓는 경우 d[n - 1], 맨 오른쪽 끝에 두개를 놓는 경우 2*d[n - 2]로 다음과 같은 점화식을 도출해낼 수 있습니다. d[n] = d[n - 1] + 2*d[n - 2] /* Bottom-Up */ #include using namespace std; int dp[1001]; int main(void) { ios_base::sync_with_stdio(false)..