분류 전체보기(301)
-
[백준] 2252: 줄 세우기 (feat.위상정렬)
https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬(Topology Sort)는 순서(선후)가 정해져 있는 작업을 차례로 수행해야 할 때 그 순서를 사용하는 알고리즘이다. 위상 정렬은 여러 개의 답이 존재할 수 있다. 또한 위상 정렬은 DAG(Directed Acyclic Graph)에만 적용이 가능하다. 사이클이 발생하는 경우에는 위상 정렬을 수행할 수 없다. 위상 정렬은 시작점이 존재해야 하는..
2022.05.04 -
[백준] 5430: AC
https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 문제만 읽으면 아주 간단한 구현 문제로 보인다. 하지만 생각보다 정답율이 약 19%밖에 되지 않아 의문을 가졌는데 풀다보면 조금은 알게 된다. 여기서 주의해야하는 함정 포인트는 크게 2가지가 있다. 1) R, D로 뒤집고 지우라는 명령을 곧이 곧대로 받아들이면 안된다. 코드만 봅면 지우거나 뒤집는 게 쉬워보이지만, 메모리 상에서는 상당히 귀찮은 일이다. 시간복잡도가 O(N)이나 소요되는 일이다. 따라서 뒤집기(R) 처리는 하나의 변수를 지정하여 현재 배..
2022.05.03 -
C++로 코딩테스트를 풀 때 추가하는 구문의 목적
C++로 알고리즘을 풀 때 실행 속도를 높이기 위해 아래와 같은 구문을 추가한다. ios_base::sync_with_stdio(false); cin.tie(null); 첫 번째 코드 ios_base::sync_with_stdio는 c의 stdio와 cpp의 iostream을 동기화시켜주는 역할을 한다. 이 때 iostream과 stdio의 버퍼를 모두 사용하기 때문에 delay가 발생한다. ios_base::sync_with_stdio(false) 코드를 작성함으로써 동기화를 비활성화해준다. 이로 인해 C++(iostream)만의 독립적인 버퍼가 생성되어 C의 버퍼와 병행하여 사용할 수 없게 된다. 그러나 동기화를 하지 않기 때문에 실행속도는 빨라진다. 알고리즘 문제를 풀 때는 대부분 싱글 스레드이기 ..
2022.05.03 -
최단 경로 문제
최단 경로 문제 최단 경로 문제란 두 노드를 잇는 가장 짧은 경로를 찾는 문제다. 가중치가 있는 그래프(Weighted Graph)에서는 Edge의 가중치의 합이 최소가 되도록 하는 경로를 찾으려는 것이 목적이다. 최단 경로 문제에는 다음과 같은 유형이 있다. 단일 출발 최단 경로: 단일 노드 𝑣에서 출발하여 그래프 내의 모든 다른 노드에 도착하는 가장 짧은 경로를 찾는 문제 단일 도착 최단 경로: 모든 노드들로부터 출발하여 그래프 내의 단일 노드 𝑣로 도착하는 가장 짧은 경로를 찾는 문제. 단일 출발 최단 경로를 거꾸로 뒤집은 것과 같다. 단일 쌍 최단 경로: 주어진 꼭짓점 𝑢와 𝑣에 대해 𝑢에서 𝑣까지의 최단 경로를 찾는 문제 전체 쌍 최단 경로: 그래프 내 모든 노드 쌍들 사이의 최단 경로를 찾는 ..
2022.05.02 -
[백준] 1931: 회의실 배정
https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 정말 전형적인 Greedy Algorithm 문제이다. 그러면 어떤 내용을 기준으로 잡아야하는지 고민해보아야 한다. 회의가 시작한 순으로 정렬을 하면 최대 회의의 수를 구할 수 없다. 왜냐하면 회의는 일찍 시작했으나 늦게 끝나는 경우가 있기 때문이다. 따라서 회의가 끝나는 순대로 오름차순 정렬을 하고, 최대한 앞에서부터 채운다는 느낌으로 회의의 수를 세면 된다. 정렬 기준으로 회의의 종료 시간을 설정하기 위해서 회의에 대한 정보를 저장할 때 vector에 first에 종료 시간을, second에 시작 시간을 설정..
2022.05.02 -
[클린코드] 동시성
평소 부주의하게 다중 스레드를 사용했던 경험이 있어서 마침 클린코드에 언급된 동시성 내용을 정리해보았다. 동시성이 필요한 이유? 동시성은 결합을 없애는 전략이다. 결합을 풀어내면 애플리케이션의 구조와 효율이 극적으로 나아진다. 하지만 구조적 개선만을 위해 동시성을 채택하는 것은 아니다. 어떤 시스템은 응답 시간과 작업 처리량 개선이라는 요구사항으로 인해 직접적인 동시성 구현이 불가피하다. ex1. 단일 스레드 수집기는 웹 소켓에서 입출력을 기다리는 시간이 아주 많다. 한 번에 한 사이트를 방문하는 대신 다중 스레드 알고리즘을 이용하면 수집기 성능을 높일 수 있다. ex2. 한 번에 한 사용자를 처리하는 시스템이 있다고 하자. 한 사용자를 처리하는 시간은 1초다. 사용자가 소수라면 시스템이 아주 빨리 반응..
2022.05.02