Algorithms/Implementation 검색 결과

해당 글 12건

[프로그래머스] 오픈채팅방(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 15684] 사다리 조작(C++)

사다리 조작(Gold 4) 문제 전체 문제 보기 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 접근법 이번 문제는 사다리를 놓을 수 있는 모든 경우의 수를 백트레킹으로 완전탐색해서 풀 수 있는 문제입니다. 문제에서는 최대 추가할 수 있는 사다리 개수를 3개로 제한하였습니다. 우리가 찾아야 할 값은 추가 사다리의 최소 개수이기 때문에 추가 사다리 개수가 0, 1, 2, 3인 경우를 각각 탐색하여 이전 탐색에서 해답을 찾은 경우 더 이상 탐색을 하지 않는 방식으로 최적화할 수 있습니다. 각 탐색에서는 목표 탐색..
Algorithms/Implementation 2021. 10. 29. 10:16

[BOJ 15683] 감시 (C++)

감시(Gold 5) 문제 전체 문제 보기 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 접근법 문제에서 주어지는 카메라는 최대 8대입니다. 모든 카메라가 4방향으로 회전할 수 있다고 하더라도 \(4^8 = 65,536\)경우의 수가 존재하고 각 경우의 수마다 전체 맵(64칸)에 존재하는 사각지대를 카운트하면 되기 때문에 백트래킹을 활용한 완전 탐색을 하더라도 충분히 시간 내에 풀 수 있는 문제입니다. 다만 카메라의 회전을 구현하는 부분이 조금 복잡한 문제였습니다. 카메라의 회전은 다음과 같이 구현하..
Algorithms/Implementation 2021. 10. 18. 21:04