문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12905? 1과 0으로 채워진 보드판이 존재한다. 표에서 1로 이루어진 가장 큰 정사각형의 넓이를 출력하는 것이 문제 이때, 보드의 크기는 최대 1000x1000까지 가능하다. 문제 핵심 및 풀이 최악의 경우 반복 횟수 보드의 최대 크기는 1000x1000이다. 그리고 구해야 하는 것은 정사각형의 크기이다. 만약 이를 직접 1의 개수를 세어가면서 구한다면 어느 좌표에서 시작해야 최대 정사각형인지 모르기 때문에 최악의 경우 1000x1000 배열을 전부 훑어야 할 수도 있다. 그런데 각 시작점부터 1의 개수를 세야 하기 때문에 1000 x 1000 x 1000 x 1000 = 10^12번 해..
문제 링크 ↓ ↓ ↓ https://school.programmers.co.kr/learn/courses/30/lessons/12900 세로 길이가 2이고, 가로길이가 n으로 주어진다. 타일은 2가지 방식 중 하나로만 배치할 수 있다. 1. (1x2) 타일을 가로로 배치하는 경우 2. (2x1) 타일을 세로로 배치하는 경우 가로길이가 n일 때 나올 수 있는 경우의 수를 1,000,000,007로 나눈 나머지를 구하는 문제 문제 핵심 및 풀이 일단 답을 구할 때 1,000,000,007로 나누라고 한 거 보니 경우의 수가 엄청나게 많이 나올 것이라는 것을 예측할 수 있다. 가로( n)가 1일 때부터 나올 수 있는 패턴을 나열해 보자. 1,2,3,5 순으로 개수가 많아진다. 답을 구할 때 1,000,000,..
동기화 도구들은 임계 구역 문제인 상호 배제를 보장하고 라이브니스 문제를 해결하는데 효과적 락 없는(lock-free) 알고리즘 락 없는 알고리즘의 구현 락 없는 알고리즘을 구현하는 이유? → 락 오버헤드 없이 경쟁 조건으로부터 보호하기 위해 락 없는 알고리즘을 구현하기 위해 CAS 명령을 사용하는데 중점을 둠 CAS → compare and swap의 약어 장점 : 락 없는 설루션은 오버헤드가 낮고 확장성이 있기 때문에 인기가 있음 단점 : 알고리즘 자체가 개발 및 테스트가 어려운 경우가 많음 CAS 기반 접근 방식 CAS 기반 접근 방식이 낙관적으로 접근하는 과정 우선 낙관적으로 변수를 갱신 충돌 감지를 사용하여 다른 스레드가 변수를 병행하게 갱신 중인지 확인 갱신 중이라면, 충돌 없이 성공적으로 갱..
라이브니스(Liveness) 임계구역 접근을 위해 동기화 도구를 사용할 때 문제 임계구역에 들어가려고 시도하는 프로세스가 무기한 대기할 가능성이 생김 무기한 대기는 진행 및 한정된 대기 2개의 기준을 위반한다. 라이브니스와 라이브니스 실패 프로세스가 실행 수명주기 동안 진행되는 것을 보장하기 위해 시스템이 충족해야 하는 일련의 속성 무기한 대기하는 프로세스는 라이브니스 실패의 한 예시 다양한 형태의 라이브니스 실패 → 결과적으로 성능과 응답성이 나쁜 것이 특징 예시 무한 루프 바쁜 대기 루프 → 라이브니스 실패의 가능성이 있음 특히 프로세스가 임의로 오래 시간 동안 루프 돌고 있는 경우 가능성 높아짐 도구를 통해 상호 배제를 제공하려는 노력이 병행 프로그래밍 환경에선 실패 가능성 존재 도구를 통한 상호 ..
모니터를 사용하는 이유 세마포 또는 mutex 락을 이용하여 임계구역 문제를 해결할 때 문제점 → 프로그래머가 세마포를 잘못 사용할 시, 다양한 유형의 오류가 쉽게 발생할 수 있음 이러한 오류 처리를 위해 모니터 사용 전략 : 간단한 동기화 도구를 통합하여 고급 언어 구조물로 제공하는 것 → 모니터 모니터는 근본적인 고급 언어 구조물 중 하나 Java, C# 등의 많은 프로그래밍 언어들이 모니터의 개념을 편입시킴 모니터 사용법(Usage) ADT와 모니터 ADT(추상화된 데이터 형) : 데이터와 해당 데이터를 조작하는 함수들의 집합을 하나의 단위로 묶어 보호 이때 함수의 구현은 ADT의 특정한 구현과는 독립적 모니터 형 : 모니터 내부에 프로그래머가 정의한 일련의 연산자 집합을 포함하는 ADT 이때 모니..
Mutex Locks 만들어진 이유? 임계구역 문제에 대한 하드웨어 기반 해결책은 복잡하고, 응용프로그래머가 사용 불가능 → 임계구역 문제 해결을 간단하게 하기 위해 만들어진 소프트웨어 도구를 개발 Mutex Locks : 상위 수준 소프트웨어 도구 중 하나로, 가장 간단한 도구 임계 구역 보호를 통해 경쟁 조건 방지를 위해 mutex 락 사용 임계 구역에 들어갈 때 락을 획득하고, 빠져나올 때 락을 반환해야 한다. acquire() : 락 획득 release() : 락 반환 Mutex Lock의 구성 available이라는 boolean 변수를 가짐 → 이 변수 값이 락의 가용 여부를 표시 락이 사용 가능하면 acquire() 호출은 성공하고, 락은 사용 불가 상태가 됨 사용 불가 상태의 락을 획득하려..
https://school.programmers.co.kr/learn/courses/30/lessons/1835?language=cpp [A, C, F, J, M, N, R, T] 8개의 알파벳을 나열하는 것을 베이스로 한다. 입력으로 있는 data의 모든 조건에 부합하여 나열할 수 있는 경우의 수가 총 몇 가지가 나오는지 구하는 문제 문제 핵심 및 풀이 해당 문제 풀이의 핵심은 조건의 개수 n이 최대 100개까지라는 점. 그리고 8개의 알파벳을 나열할 때 나올 수 있는 모든 경우의 수는 8! = 40320밖에 되지 않는다는 점이다. 그래서 일단 나올 수 있는 경우의 수는 백트래킹을 구하는 것이 적절하다. 그렇게 줄을 다 세우면, 그다음부터 data에 따라 필터링을 해주면 된다. 필터링 방법은 간단하다...
문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/138475 1억 x 1억 크기의 행렬이 존재하고, 그 정수 s~e 사이 범위에서 가장 많이 나오는 정수가 뭔지를 알아내는 문제 문제 핵심 및 풀이 제한 사항을 보면 1억 x 1억짜리 행렬은 아니더라도, 최댓값 e가 5,000,000까지 가능하기 때문에 O(n^2) 연산만 해도 바로 시간초과 그리고 O(N) 짜리 연산을 하더라도 모든 starts 값에 대해서 답을 구해준다면, starts의 최대 길이는 100,000이니까, 10^5 * 10^6 이어서 역시 시간초과다. 결국 모든 starts의 범위에 대한 값을 미리 구해놓을 수밖에 없다. 즉, 메모라이징 기법을 이용하는 DP 문제라고 대놓고..