본문 바로가기

전체 글

 (386)
백준 3079번 입국심사(C++) https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 처음 문제를 봤을 때 우선순위큐 문제라고 생각했다. 그러나 몇 초 쉬고 다른 심사대로 이동하는 것을 생각해보면 아무래도 우선순위 큐로는 풀어낼 수 없다. 그러다가 분류를 보니 이분탐색 파라메트리 서치가 보였다. ? 아니 이걸 어떻게 파라메트리로 ? 라고 생각해서 기다렸다가 가는 시간초를 파라메트릭으로 판단하나? 생각했는데 그걸리가 없지. 파라메트릭은 보통 "정답" 을 반환한다. an..
프로그래머스 - 거리두기 확인하기 (C++) https://school.programmers.co.kr/learn/courses/30/lessons/81302 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 접근법 - 처음 봤을 때는 bfs 한번으로 해결하기 위해 고민했으나 각 P 별로 bfs를 돌아도 N이 워낙 작아서 시간초과가 나지 않는 문제이다. 플로이드-워셜도 생각이 났는데 플로이드 워셜은 행렬에서 사용해본적이 없고 간선의 비용이 주어지면 행렬로 표현하는 것이라 결이 다르다고 생각이 된다. 각 대기실은 5x5크기이기 때문에 bfs의 시간복잡도는 25이고, 모든 칸에 P가 존재하는 경우의 수를 ..
백준 23843번 콘센트 (C++) https://www.acmicpc.net/problem/23843 23843번: 콘센트 광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한 www.acmicpc.net - 접근법 - 먼저 콘센트의 개수가 최대 10개이기 때문에 시간복잡도에 큰 영향을 받지 않는 문제이다. 중요한 것은 콘센트들에 기기가 충전중 일 때 가장 오래걸리는 것을 꽂아놔야한다는 것이다. 만약 작은것 부터 꽂았다면 예제 1 1 4 4 8 에서 콘센트 1 - 1 4 콘센트 2 - 1 4 이런식으로 꽂히게 될 것이고 이후 8이 들어오면 답이 아니다. 그러므로 먼저 큰 놈이 들어와서 자리를 잡아야한다. 그..
백준 1339번 단어 수학 (C++) https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net ------------- 접근법 처음 보면 Backtracking 인가? 최적의 해를 어떻게 구할 수 있지? 라는 고민을 먼저 하게 된다. PS를 하면서 느끼는 건 "이렇게 하면 답이 나오는데 증명이 안됐다" 라는 해는 사용하면 안된다 맞는 경우도 있겠지만 매우 위험하다. 이 문제도 마찬가지다. ABCDE FCG 에서 AB까지는 9 8 을 하고 나머지는 번갈아가며 7 6 5 4.. 를 주니 ..
전통적인 동기화 문제 은행동기화 문제 같이 우리 실생활에서 사용되는 문제들도 있지만 예전부터 전통적으로 문제가 되는 문제들이 있다. 이를 전통적 동기화 문제라고 한다. Producer and Consumer Problem 생산자 소비자 문제 생산자는 데이터를 생성하고 소비자는 그 데이터를 소비한다. 예를들어 컴파일러가 데이터를 컴파일하면 어샘블리 코드가 되고 어셈블리어를 번역하여 기계어가 된다. 생산자는 데이터를 생성하고서 바로 소비자에게 넘기지 않는다. I/O차이, 연산차이 등 속도를 맞추기 위해 먼저 buffer에 데이터를 삽입하고 이후 소비자가 버퍼에 접근해 take 하는 식으로 처리된다. 즉, 버퍼는 생산자와 소비자가 모두 접근하는 Critical Section이 되는 것이다. 이를 해결하기 위해 상호배재를 위한 세마..
백준 20208번 진우의 민트초코우유 (C++) https://www.acmicpc.net/problem/20208 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 이전에 풀어본 문제들을 다시 풀어보는 프로젝트(?)를 진행중이다. 문제 양치기보다 각 문제들을 더 잘 파악하는게 좋을 것 같다는 생각이 들었다. 모든 문제를 내 힘으로 푼 것도 아니기 때문이다. 1. 문제 조건 - 가능한 많은 초코우유를 마시고 돌아올 수 있는 최대 민트초코우유 개수를 찾아낸다. 2. 접근법 - 먼저 보고 생각나는 건 DFS 완전탐색이다. 그리고 이것은 틀린 생..
백준 2533번 사회방 서비스(SNS) C++ https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 트리에서 다이나믹 프로그래밍 문제이다. 진짜 너무 어렵다 이런거 어떻게 풀어야하는 걸까. 계속 하면 할 수 있겠지라 생각하며 계속 하는 수 밖에 없다. * 트리에서 다이나믹 프로그래밍을 적용할 때는 보통 이번 노드에서의 dp값 다음 노드까지 포함했을 때 dp값으로 이어지는 top Down방식이거나 leaf까지 도달한 후 올라오며 값을 갱신하는 Bottom Up 방..
OS - 임계구역과 세마포어 Critical Section 공통 자원을 건드릴 수 있는 공간이다. 멀티 프로세싱에 의한 오류는 보통 여기서 발생한다. 해결 방안이 갖춰야하는 것 Mutual exclusion - 오직 한 쓰레드만 진입 Progress - 진입 결정은 유한 시간 내 Bounded waiting - 어느 스레드라도 유한 시간 내에 해결해야함. 프로세스/쓰레드 동기화 임계구역 문제 해결 (틀린 답 X) 프로세스 실행 순서 제어 비효율성 제거 세마포어 유명한 동기화 해결 도구 acquire() release() 세마포어는 상호베타를 위해 사용한다. void acquire(){ value--; if(value < 0){ add this process/thread to list block } } void release(){ v..

티스토리툴바