본문 바로가기

분류 전체보기

 (386)
[pro] 프로그래머스 level3 84021 퍼즐 조각 채우기 (Java) - BFS [문제] https://school.programmers.co.kr/learn/courses/30/lessons/84021 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 시나리오 1. board의 빈 공간과 table의 블록을 모두 추출한다. BFS를 이용하며, 좌표를 추출해서 list에 넣어준다. 2. 추출한 table의 블록들을 board의 빈공간과 하나씩 비교해주면서 딱 맞아들어가면 visited 배열을 true로 바꿔주고(중복 방지) 블록 개수만큼 answer에 더해준다. table 블록 좌표 개수와 board 빈공간 좌표 개수가 맞지않거..
[운영체제] 7. Deadlocks 더보기 kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다. 1. Deadlock (교착상태) Deadlock: 일련의 프로세스들이 서로가 가진 자원을 기다리며 block된 상태 Resource(자원): 하드웨어, 소프트웨어 등을 모두 포함하는 개념. ex) I/O device, CPU cycle, memory space, semaphore 등. 프로세스가 자원을 사용하는 절차: Request -> Allocate -> Use -> Release Deadlock example 1) 하드웨어 자원에 대한 deadlock - 시스템에 2개의 tape drive가 있고, 프로세스 P1과 P2 각각이 하나의 tape drive를 보유한 채 다른 하나를 기다리고 있는 경우 Deadlock examp..
[pro] 프로그래머스 level3 87694 아이템 줍기 - BFS [문제] https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 문제를 푸는 핵심은 좌표를 2배로 확장하는 것이다. 테두리로만 이동하도록 하기 위해서, 먼저 테두리를 포함한 모든 사각형을 1로 채운 후, 테두리를 제외한 안쪽을 0으로 다시 바꿔 채워주었다. 이때 bfs를 돌리려고 하면 컴퓨터가 좌표로 길을 판단하기 때문에 테두리를 구분하지 못하는 문제가 발생한다. 예를 들어, 위 그림에서 (3, 5), (4, 5), (3, 6), (4, 6)..
[pro] 프로그래머스 level3 92343 양과 늑대 (Java) - DFS [문제] https://school.programmers.co.kr/learn/courses/30/lessons/92343 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 완전 탐색 dfs로 풀 수 있다. 주의할 점은, 이미 지났던 노드를 다시 지나서 왼쪽, 오른쪽 경로로 이동할 수 있는데 이를 고려해줄 필요가 없다는 것이다. 이미 지난 노드에서 양이나 늑대를 얻었기 때문에 다시 지나는 경우는 변화하는게 없다. 따라서 그래프 역시 양방향이 아닌 단방향으로만 만들어줬다. 0에서 1로 이동했다고 가정해보자. 이후 이동할 수 있는 노드는 2, 4, 8 ..
[pro] 프로그래머스 level3 92344 파괴되지 않은 건물 - dp, 배열 누적합 [문제] https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 문제 자체는 풀기 쉽지만 단순하게 풀면 O(NM)의 시간복잡도를 가져 효율성 테스트를 절대 통과할 수 없다. 효율성을 따지는 문제의 경우 그래프가 아니라면 dp나 이분탐색으로 풀 수 있는지를 떠올리는데, 이 문제같은 경우 2차원 배열에 균일한 변화량을 똑같이 더해주거나 빼주기 때문에 dp를 이용한 이차원 배열 누적합 문제임을 알 수 있다. 2차원 배열 누적합을 구하는 방법은 다음..
[운영체제] 6. Process Synchronization (4) 더보기 kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다. 1. Monitor Semaphore의 문제점 - 코딩하기 힘들다. - 정확성의 입증이 어렵다. - 자발적 협력이 필요하다. - 한번의 실수가 모든 시스템에 치명적 영향을 미친다. 예) V(mutex); critical section P(mutex); P, V 순서가 뒤바뀜 → Mutual exclusion이 깨지는 문제 발생 P(mutex); critical section P(mutex); 공유데이터를 반납하는 코드 없음 → Deadlock Monitor 동시 수행중인 프로세스 사이에서 abstract data type의 안전한 공유를 보장하기 위한 high-level synchronization contruct. 모니터 내의 ..
[pro] 프로그래머스 level3 131703 2차원 동전 뒤집기 (Java) - DFS [문제] https://school.programmers.co.kr/learn/courses/30/lessons/131703 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr [풀이] 할 수 있는 행동은 행을 뒤집거나, 열을 뒤집는 것 2가지이다. 만약 모든 경우의 수를 따진다면, (n개의 행을 뒤집거나 뒤집지 않는 경우의 수) 2^n × 2^m (m개의 열을 뒤집거나 뒤집지 않는 경우의 수) 이 될 것이다. 그러나, 모든 행을 뒤집거나 뒤집지 않는 경우를 구한 이후, 열에 대해서는 모든 경우를 다 살펴보지 않아도 되기 때문에 2^n 만으로 해결 가능하다. ..
[운영체제] 6. Process Synchronization (=Concurrency Control) (3) 더보기 kocw 반효경 교수님의 운영체제 강의를 수강 후 작성한 글입니다. 1. Synchronization Hardware 하드웨어적으로 Test & Modify를 atomic하게 수행할 수 있도록 지원함으로써 not progress 문제를 해결할 수 있다. Test & Set 명령어를 따로 수행한다면, Set 이후 context switch가 발생하여 Algorithm2와 동일한 문제가 발생할 수 있다. Test_and_Set 회로를 만들면 하나의 operation처럼 수행함으로써(atomic) 문제를 해결한다. Mutual Exclusion with Test & Set Synchronization variable : boolean lock = false; Process Pi do { while(Te..

티스토리툴바