본문 바로가기

분류 전체보기

 (336)
백준 25634번 - 전구 상태 뒤집기 (C++) https://www.acmicpc.net/problem/25634 25634번: 전구 상태 뒤집기 $N$개의 전구가 일렬로 세워져 있다. 전구는 켜져 있을 수도 있고 꺼져 있을 수도 있다. 만약 $i$번째 전구가 켜져 있다면 그 전구의 밝기는 $a_i$이다. 연우는 $N$개의 전구 중 연속한 전구를 한 개 www.acmicpc.net 문제 조건 - 한 시퀀스가 모두 바뀌었을 때를 가정한다. 길이가 3이면 1,2,3,1~2, 3~4, 1~3 이렇게 모든 전구를 바꾸어야한다. 반드시 단 1번은 바꾸어야한다. 내 접근 - dp로풀어야한다. 그리고 누적합으로 구하는 것인데 어떻게 하는지 모르겠어서 일단 dp로 생각해보기로 했다. 그러나 dp[index] = index까지의 최적합 으로 구하기에는 따져야할 것이..
OS - 프로세스 동기화 개념 프로세스 동기화 프로세스 병행 (Concurrency) OS는 아주 빠른 시간에 프로세스를 스위칭한다. 때문에 사실은 하나의 프로세스만 화면에서 실행중이지만 마치 함께 실행중인 것 처럼 보인다. 이것을 프로세스 병행, 동시성이라 한다. 독립 프로세스와 협력 프로세스 독립 프로세스 단일 처리 시스템에서 수행하는 병행 프로세스, 다른 프로세스와 영향을 받지 않으며 독립적으로 실행된다. 협력 프로세스 우리가 사용하는 많은 프로그램은 협력 프로세스이다. 두 프로세스가 동일한 파일을 사용할 수도 있고 프로세스 하나가 파일을 읽는 동안 다른 프로세스가 쓰기를 실행하려 할 수도 있다. 프로세스 동기화 위 처럼 프로그램들이 하나의 자원에 접근하려하면 어떤 일이 발생할까. 가장 유명한 예제는 바로 은행 예제이다. A씨의..
백준 14226번 - 이모티콘 (C++) https://www.acmicpc.net/problem/14226 14226번: 이모티콘 영선이는 매우 기쁘기 때문에, 효빈이에게 스마일 이모티콘을 S개 보내려고 한다. 영선이는 이미 화면에 이모티콘 1개를 입력했다. 이제, 다음과 같은 3가지 연산만 사용해서 이모티콘을 S개 만 www.acmicpc.net 문제조건 - 이모티콘의 개수를 늘리는 방법은 오직 붙여넣기 뿐이다. 화면의 이모티콘은 임의로 늘릴 수 없으나 삭제는 가능하다. 그리고 각 행동은 1초의 작업시간을 가진다. 내 접근 - 당연히 BFS 문제라고 생각했다. 최소,최단거리 문제이고 할 수 있는 행동이 3가지이다. 그러므로 BFS문제라 생각하는 것이 타당하다. 그러나 문제는 방문처리이다. 한 번 갔던 이모티콘 개수라 해도 담고있는 클립보드의..
OS - CPU 스케줄링(3), 프로세스의 생성과 소멸, 쓰레드 MultiLevel Queue 스케줄링 다단계 큐 스케줄링은 이전에 봤던 것 처럼 하나의 큐를 사용하는 것이 아닌 여러개의 큐를 사용하는 방법이다. 앞어 많은 프로세스들이 있었는데 운영체제 단계에서 인터럽트를 처리하는 프로세스도 있고 사용자와 인터랙티브하는 프로세스, 배치 프로세스, 컴파일러 등 많은 프로세스가 있는데 이들을 같은 큐로 관리하기 어렵기 때문에 나온 개념이다.' 위의 순서대로 우선순위가 매겨져 각 큐는 절대적인 우선순위를 가진다. 아래의 프로세스 큐가 실행되려면 위의 프로세스 큐가 모두 비어있어야한다. 만약 Interactive Processes가 실행되고 있던 중 System Processes작업이 큐에 들어오면 바로 프로세서를 반납해야한다. 각각의 큐는 독립된 스케줄링 기법을 사용한다...
백준 14658번 - 하늘에서 별똥별이 빗발친다. (C++) https://www.acmicpc.net/problem/14658 14658번: 하늘에서 별똥별이 빗발친다 첫째 줄에 네 정수 N, M, L, K가 주어진다. (1 ≤ N, M ≤ 500,000, 1 ≤ L ≤ 100,000, 1 ≤ K ≤ 100) N은 별똥별이 떨어지는 구역의 가로길이, M은 세로길이, L은 트램펄린의 한 변의 길이, K는 별똥별의 수를 www.acmicpc.net 문제조건 - 별똥별의 좌표가 주어지고 천을 펼쳤을 때 최대한 좌표가 천에 포함되어야한다. 내 접근 - 일단 N,M이 50만이라 절~~~대 O(N * M)으로는 풀어낼 수 없다. 그런데 아무리 봐도 문제가 브루트포스가 아니면 풀수가 없다고 생각됐다. 그래서 일단 풀 수 있는대로 해보니 당연히 시간초과가 났다. 어떻게 풀어야..
OS - CPU 스케줄링(2) CPU 스케줄링은 Ready Queue의 프로세스들 중 무엇을 우선으로 cpu에 할당할지 정하는 스케줄링 기법이다. Shortest-Job-First First Come First Service (FCFS)는 들어온 순서부터 서비스하는 기법이었다. SJF는 가장 작업시간이 빠른 작업부터 서비스하는 것이다. 선점 vs 비선점 SJF는 선점과 비선점 방법 둘 다 구현할 수 있다. 선점: cpu가 일단 작업을 시작하면 프로세스가 종료되기 전 까지는 서비스 하는 프로세스를 변경하지 않는 방법이다. 비선점: cpu가 작업을 하고 있어도 작업을 빨리 끝낼 수 있는 프로세스가 들어온다면 그것 부터 처리한다. 이 방법은 최소 잔여 시간 방법으로도 불린다. 단, 이 방법은 우리의 컴퓨터에 실제로 적용하기는 힘들다. Pr..
프로그래머스 - 피로도 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/87946 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 순서를 1 2 3, 2 1 3, 3 1 2 등 어떤식으로 진행해야할지 정하는 문제. 그리디하게 생각할 수 없고 모든 것을 해보는 것이 정답인 경우이다. 겨우 N이 8까지 밖에 없는 경우라서 가능하지만 숫자가 더 커지면 다른 방법을 찾아야한다. 이 문제는 dfs로 순열을 만드는 문제와 유사하다. dfs로 순열 조합을 다룰 줄 알아야한다. #include #include #include using n..
백준 14267번 회사 문화1 (C++) https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 문제조건 - 각 노드들은 부하를 자식으로 갖는다. 그리고 각 노드가 칭찬을 받으면 부하에게 전달되는 식으로 코드를 전개하면 된다. 내 접근 - 그래서 한 직원이 칭찬을 받으면 내리칭찬으로 dfs를 하고 칭찬을 받으면 dfs하는 식으로 구성했다. 그러나 이것은 dfs를 계속 반복하게 되어 좋지 않은 풀이가 된다. 그래서 시간초과에 걸렸다. 올바른 접근법 - 올바른 접근법은 칭찬을 받고 이전의 정보..

티스토리툴바