전체 글 검색 결과

해당 글 226건

[BOJ 8980] 택배 (C++)

택배 Gold 3 문제 전체 문제 보기 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 접근법 이번 문제는 어떻게 접근할지 생각하기 다소 어려운 문제였습니다. 이번 문제 같은 경우 그리디로 풀 수 있지만 DP로 풀어야할지 그리디로 풀어야할지 여러 방향으로 오래 고민을 했습니다. 제가 풀었던 방법은 다음과 같습니다. 가장 많은 택배를 배송하기 위해서는 새로운 택배를 많이 받아야 합니다. 새로운 택배를 많이 받기 위해서는 빨리 내릴 수 있는 택배를 먼저 받고 바로 새로운 택배를 받아야 합니다...
Algorithms/Greedy 2021. 11. 12. 10:13

[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