전체 글
-
[OS] 6-2. Process SynchronizationComputer Science/운영체제 2021. 2. 10. 16:33
# 3가지의 고전적인 Synchronization 문제 1. Bounded-Buffer Problem (Producer-Consumer Problem) - Bounded-Buffer Problem이란? 유한한 크기(그림은 circular 형태)를 가진 버퍼(임시로 데이터를 저장하는 공간)의 환경에서 발생하는 문제들을 의미한다. 이 문제는 생산자-소비자 문제(Producer-Consumer Problem)라고도 불리며, 이러한 상황을 가정 할 때는 여러 개의 생산자 프로세스와 여러 개의 소비자 프로세스가 존재한다. 생산자 프로세스들은 데이터를 생성해 빈 공유 버퍼에 삽입한다. 위 그림에서는 주황색으로 칠해져 있는 동그라미가 생산자 프로세스가 데이터를 저장해 둔 공유 버퍼이고, 색이 없는 동그라미가 비어 있..
-
[백준 9251번] LCSCoding Test/백준 2021. 2. 8. 21:12
# 문제 내 풀이 - 문제 풀이 실패, 수정 답안 str1 = input() str2 = input() dp = [[0] * 1001 for _ in range(1001)] # 최장 공통 부분 수열(LCS) 찾기 for i in range(1, len(str1) + 1): for j in range(1, len(str2) + 1): if str1[i - 1] == str2[j - 1]: # 가장 최근에 추가된 글자가 서로 같을 때 dp[i][j] = dp[i - 1][j - 1] + 1 else: # 추가된 글자가 서로 다를 때 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # 결과 출력 print(dp[len(str1)][len(str2)]) 생각해볼 점 아직도 완전히 이..
-
[백준 2565번] 전깃줄Coding Test/백준 2021. 2. 7. 23:19
# 문제 내 풀이 n = int(input()) # 전깃줄의 위치 정보 입력 받음 lines = [] for _ in range(n): a, b = map(int, input().split()) lines.append((a, b)) # A의 위치를 기준으로 전깃줄 위치 정보를 오름차순 정렬 lines.sort(key=lambda x: x[0]) # DP 테이블 생성 및 초기화 dp = [1] * n # B의 수열에서 가장 긴 증가하는 부분 수열(LIS) 찾기 for i in range(1, n): for j in range(0, i): if lines[i][1] > lines[j][1]: dp[i] = max(dp[i], dp[j] + 1) # 없애야 하는 전깃줄의 최소 개수 구하기 print(n - m..
-
[백준 11054번] 가장 긴 바이토닉 부분 수열Coding Test/백준 2021. 2. 6. 04:40
# 문제 내 풀이 n = int(input()) nums = list(map(int, input().split())) # 수열 입력 받기 # 가장 긴 증가하는 부분 수열과 감소하는 부분 수열 각각을 위한 DP 테이블 생성 및 초기화 dp_asc = [1] * 1000 dp_desc = [1] * 1000 # 가장 긴 증가하는 부분 수열 (LIS) 알고리즘 수행 for i in range(1, n): for j in range(0, i): if nums[i] > nums[j]: dp_asc[i] = max(dp_asc[i], dp_asc[j] + 1) # 가장 긴 감소하는 부분 수열 알고리즘 수행 for i in range(n - 2, -1, -1): for j in range(n - 1, i, -1): ..
-
[OS] 6-1. Process SynchronizationComputer Science/운영체제 2021. 2. 6. 04:32
# Process Synchronization 문제 위 그림처럼 S-box(Storage-Box)에 담긴 데이터에 여러 E-box(Execution-Box)가 접근하는 경우, 복수의 E-box(여러 프로세스)들이 동시에 데이터에 접근하는 Race Condition이 발생한다. 이러한 상황에서 데이터의 최종 연산 결과가 마지막에 해당 데이터를 다룬 프로세스에 의해 원치 않는 결과로 이어질 수 있는데, 이처럼 공유 데이터에 동시 접근이 일어나 데이터의 불일치가 생기는 문제를 Process Synchronization이라고 한다. # OS에서 Race Condition이 발생하는 3가지 경우 1. kernel 수행 중 인터럽트 발생 시 Process Synchronization은 인터럽트로 인해 발생하기도 한..
-
[백준 11053번] 가장 긴 증가하는 부분 수열Coding Test/백준 2021. 1. 30. 14:08
# 문제 내 풀이 # 내 풀이 n = int(input()) nums = list(map(int, input().split())) # 수열 입력 받기 # DP 테이블 생성 및 초기화 dp = [1] * 1000 # 가장 긴 증가하는 부분 수열(LIS) 알고리즘 수행 for i in range(1, n): for j in range(0, i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) # 결과 출력 print(max(dp))
-
[백준 2156번] 포도주 시식Coding Test/백준 2021. 1. 30. 01:53
# 문제 내 풀이 - 문제 풀이 실패, 수정 답안 n = int(input()) wine = [0] # 인덱스를 맞추기 위해 0 추가 # 와인 정보 입력 받기 for _ in range(n): wine.append(int(input())) # DP 테이블 생성 및 초기화 dp = [0] * 10001 dp[1] = wine[1] if n > 1: dp[2] = wine[1] + wine[2] for i in range(3, n + 1): # 3가지 경우를 고려 # 1. i 번째 와인을 마시지 않는 경우 # 2. i 번째 외인을 마시는 경우 # - 2-1. i - 1 번째 와인을 마시는 경우 # - 2-2. i - 1 번째 와인을 마시지 않는 경우 dp[i] = max(dp[i - 1], dp[i - 3]..