문제 링크 11967번: 불켜기 풀이 BFS 문제 먼저 각 위치에서 스위치를 통해 켤 수 있는 위치는 인접 리스트와 같이 구현하였다. 방문한 자리를 표시하기 위한 visited와 불이 켜져있는 것을 표시하기 위한 room을 만들었다. 여느 BFS와 같이 queue를 이용해 구현한다. 현재 위치인 tx, ty에서 연결되어 있는 자리가 불이 꺼져있으면 불을 켜주면서 answer++해주고, 해당 위치가 방문했던 위치라면 queue에 push해준다. 상하좌우 진출하면서, 범위를 벗어나거나 방문했던 곳이라면 continue, 불만 꺼져있으면 visited 처리해준 뒤에, queue에 넣지는 않는다.(진출하지는 않음) 1번에서 불이 켜진다면 진출할 것이다. answer를 return한 뒤 출력한다. 코드 #incl..
인프런의 운영체제 공룡책 강의를 듣고 정리한 포스팅입니다. CPU 스케줄링 CPU 스케줄링은 멀티 프로그래밍 운영체제에서 기본 멀티 프로그래밍의 목적 CPU 효율을 극대화 여러 프로세스를 동시에 돌릴 수 있음 CPU bound(CPU를 많이 쓰는) 보다 I/O bound가 더 많으면 ⇒ 스케줄링을 통한 time sharing이 필요 CPU 스케줄러 CPU 스케줄러는 메모리에 로드된 프로세스 중 누구를 CPU에 할당할 것인지 선택해야 함 ⇒ ready 상태에 있는 프로세스 중 선택 프로세스 선택 ready 상태에 있는 프로세스들 중 선택하기 위해 queue를 만들 필요가 있음 FIFO Queue : First In, First Out Prority Queue : 우선순위가 높은 순으로 결정 선점형 / 비선..
문제 링크 9657번: 돌 게임 3 풀이 DP 문제 일단 돌을 1개, 3개, 4개 주을 수 있으니 dp[1] ~ dp[4]까지는 초기화해준다. dp에는 게임이 몇 번만에 끝나는지가 들어있다. 1개면 상근이가 1개를 줍고 끝나서 1, 2개면 상근이가 1개, 창영이가 1개 주워서 두 번만에 끝나니 2인 식이다. n까지 dp를 구하는데, 상근이가 1개를 주웠을 때 dp[i-1], 그니까 i-1개 남았을 때에서 상근이가 한 번 주운 1을 더해서 홀수가 되면 상근이가 이기는 거고, 아니면 창영이가 이기는 것이다. 첫빠따는 상근이기 때문에 dp[i-1], dp[i-3], dp[i-4]를 다 확인해보면서 홀수가 하나라도 나오면 상근이가 이길 것이다. 코드 #include using namespace std; int ..
문제 링크 전화번호 목록 풀이 해시 문제라고 했는데 정렬로 풀었다. a 번호가 b 번호의 접두어라고 한다면, 정렬을 했을 때 반드시 a 번호가 b 번호 앞에 나오게 된다. 임시 string인 tmp에는 접두어라고 가정할 번호를 넣는다. tmp가 비어있으면 tmp를 해당 번호로 갱신. 해당 번호에서 접두어를 뽑았는데 tmp와 같지 않아도 갱신. 같으면 해당 번호는 tmp를 접두어로 가진다는 것을 의미하므로 answer를 false로 한다. 코드 #include #include #include using namespace std; bool solution(vector phone_book) { bool answer = true; sort(phone_book.begin(), phone_book.end()); s..
객체 생성 방법 C++에서는 객체를 생성할 때 두가지 방법을 사용할 수 있다. 각 방법에 따라 객체가 할당되는 메모리 영역이 달라진다. 1. Stack에 할당 일반적인 변수와 같이 선언한다. Foo obj1 = Foo(5); Foo obj2(10); 2. Heap에 할당 new 키워드를 사용하여 선언한다. Foo* obj3 = new Foo(20); 운영체제 시간에 배웠듯이, Stack 메모리 영역은 변수를 선언한 스코프 영역을 벗어나면 자동으로 메모리가 해제되지만, Heap 메모리 영역은 프로그래머가 관리해야 하는 영역이므로 자동으로 해제가 되지 않는다. 위 코드의 obj3을 보면, new 키워드를 이용해 Heap 메모리에 객체를 할당하고 있다. 포인터는 Stack에 있고, 실제 객체의 데이터는 Hea..
문제 링크 11000번: 강의실 배정 풀이 이런 겹치는 구간 문제는 구간의 시작을 1, 끝을 -1로 잡은 다음에 정렬해서 푸는게 베스트인 것 같다. 왜 1과 -1이냐면 겹치는 구간의 개수를 잡기가 편함 강의 시간의 구간을 입력받으면서 v에 구간의 시작은 1, 끝을 -1로 해서 pair로 집어넣는다. v를 정렬하면, 구간의 시간 순으로 정렬될 것이다. 하나씩 살펴보며, 겹치는 구간의 개수인 cnt에 v[i].second를 구해주면 현재 시간에서 겹치는 강의의 개수가 나오게 될 것이다. 예제를 예로 2번까지 마치면 (1,1), (2,1), (3,-1), (3,1), (4,-1), (5,-1)가 될 것이다. 앞선 시간에서 강의를 시작했는데 (second가 1인데), 바로 뒤에서도 강의를 또 시작하면 (seco..
문제 링크 1644번: 소수의 연속합 풀이 투포인터랑 누적합 문제. 투포인터는 항상 헷갈리는게 각 포인터를 양 옆에 설정하느냐 아니냐 생각이 드는데 .. 그냥 같은 방향에서 시작하는 게 맞는 것 같다. 에라토스테네스의 체를 이용해서 n까지의 소수들을 구해준다. 여기서 팁은 i가 굳이 n까지 갈 필요 없이 제곱근까지만 구해주면 된다는 것 소수들의 누적합을 구해 sosuSum에 넣어준다. 투포인터를 이용해 연속합이 n인 구간의 경우의 수를 구해주는데, 여기서 투포인터를 사용한다. 각 포인터는 0과 1 인덱스로 설정한 뒤, en에서 st를 빼주면 구간의 합이 나온다. 이 합이 n과 같을 경우는 answer++ 2번과 상관없이 포인터를 재설정해줘야 하는데, n보다 큰 쪽에 넣든 작은 쪽에 넣든 상관없이 같을 때..
문제 링크 1368번: 물대기 풀이 최소 신장 트리인데 그래프 변형이 필요한 문제 어찌됐든 하나의 논에는 우물을 파야하기 때문에 노드를 하나 추가해서 (나같은 경우는 0번 노드) 각 우물을 파는 경우까지 최소 신장 트리로 구한다. 나머지는 크루스칼 알고리즘으로 union-find를 사용하면 여느 최소 신장 트리 문제와 비슷하다. 코드 #include #include #include #include #include using namespace std; int find(int node, vector& parent) { if (node == parent[node]) { return node; } else { return parent[node] = find(parent[node], parent); } } voi..
문제 링크 2531번: 회전 초밥 풀이 투 포인터 문제 보통 이런 종류 문제는 set을 먼저 생각하게 되는데, 이렇게 크지 않은 숫자로 있다면 그냥 배열로(index) 체크하는 게 나을 듯 함 0번째 인덱스부터 k개의 스시 종류를 체크해둔다. 초밥은 1번부터 d번까지 있기 때문에, 각 인덱스에 해당 인덱스 스시가 몇 개 들어가있는지 있게 된다. check 함수는 그 스시 배열에서 쿠폰을 사용할 무료 스시는 빼고 가짓수를 체크하게 된다. 이제 1번째 스시부터 하나씩 k개를 체크해보는데, 1번에서 구했던 종류에서 앞에 하나 빼고 뒤에 하나 추가하는 식으로 sushi 배열을 갱신하고 check한다. 이 때 인덱스를 넘어갈 경우, 해당 벨트는 원형 배열? 이기 때문에 인덱스 계산을 통해 앞의 인덱스를 구해준다...
문제 링크 18809번: Gaaaaaaaaaarden 풀이 백트래킹이라는데 BFS에 조합 문제인 것 같다. 입력을 받으면서 배양액을 뿌릴 수 있는 땅을 구해놓는다. 1번에서 구한 땅에 이제 배양액을 뿌릴 차례인데, 순열로 처리한다. 종류에 따라 상수로 정의했고 (EMPTY, GREEN, RED, FLOWER) 만약 뿌릴 수 있는 땅이 7개인데 초록색 배양액이 3개, 빨간색 배양액이 2개라면, water 배열은 {0,0,1,1,1,2,2}가 될 것이고 이를 순열처리해서 구하면 모든 조합대로 배양액을 뿌릴 수 있게 된다. BFS는 여느 BFS와 같이 queue를 이용해서 풀면 된다. 코드 #include #include #include #include #include #define INF 2501 using..
