달리는 개발자

[BOJ 17142] 연구소3 (C++)

연구소3 Gold 4 문제 전체 문제 보기 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 접근법 이번문제는 전체 바이러스 개수(M개 이하) 중 최적의 M개의 바이러스를 선택했을 때 전파시간의 최솟값을 구하는 문제입니다. 임의의 M개를 뽑았을 때 전파시간을 계산하기 위해서는 BFS를 사용할 수 있으며, M개를 뽑기 위해서는 백트레킹을 통한 완전 탐색을 사용할 수 있습니다. 최대 바이러스 개수는 10개이므로 최악의 경우에도 \(_{10}\mathrm{C}_{5} = 252\) 가지의 경우의 수가 존재합니다. 따라서 최악의..

Algorithms/Backtracking 2021. 11. 10. 14:17

[프로그래머스] 오픈채팅방(C++)

오픈채팅방(Level 2) 문제 전체 문제 보기 코딩테스트 연습 - 오픈채팅방 오픈채팅방 카카오톡 오픈채팅방에서는 친구가 아닌 사람들과 대화를 할 수 있는데, 본래 닉네임이 아닌 가상의 닉네임을 사용하여 채팅방에 들어갈 수 있다. 신입사원인 김크루는 카카오톡 오 programmers.co.kr 접근법 이번 문제는 주어진 문자열 배열(record)을 공백을 기준으로 분할한 뒤 해시 테이블에 id, name으로 등록한 후 출력하여 풀 수 있습니다. 분할할 문자열의 기준이 공백이라면 stringstream 라이브러리로 쉽게 분할 가능합니다. 따라서 다음과 같이 문제를 해결할 수 있습니다. stringstream을 활용하여 입력받은 명령어 문장을 3개의 문자열(command, id, name)로 나눕니다. co..

Algorithms/Implementation 2021. 11. 9. 10:09

[BOJ 14719] 빗물 (C++)

빗물 (Gold 5) 문제 전체 문제 보기 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 접근법 이번 문제는 가장 왼쪽에서 → 가장 큰 블록 까지, 그리고 가장 오른쪽 → 가장 큰 블록까지 탐색을 통해서 빗물의 양을 구할 수 있습니다. 따라서 전체 가로의 크기 \(W\)일 때 \(O(W)\) 시간 안에 계산을 마칠 수 있습니다. 탐색방법은 복잡하지 않기 때문에 코드를 통해서 참고해 주세요. 전체 코드 #include #include #include #define endl '\n' using ..

Algorithms/Implementation 2021. 11. 4. 13:54

[BOJ 2616] 소형기관차 (C++)

소형 기관차 (Gold 4) 문제 전체 문제 보기 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있 www.acmicpc.net 접근법 문제를 보고 처음 접근할 때는 완전 탐색이 가능한지를 먼저 살펴보는 것이 좋을 때가 많습니다. 완전 탐색으로도 쉽게 풀릴 수 있는 문제를 어렵게 고민하는 경우가 생길 수도 있기 때문입니다. 그리고 완전 탐색으로 답을 구할 수 없더라도, 완전 탐색으로 접근한 방법을 최적화하여 문제를 해결하는 경우도 많습니다. 이번 문제도 완전 탐색으로 먼저 접근해 보았습니다. 소형 기차는 총 3대입니다. 기차의 전체 ..

Algorithms/DP 2021. 11. 4. 12:25