Algorithms 검색 결과

해당 글 123건

[BOJ 11066] 파일 합치기(C++)

파일 합치기(Gold3) 문제 전체 문제 보기 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 접근법 이번 문제는 동적 계획법으로 풀 수 있는 문제입니다. 동적 계획법의 주요한 두 가지 개념은 다음과 같습니다. 큰 문제를 작은 문제로 나눠서 문제를 해결한다. 한번 푼 문제를 저장하여 불필요한 연산을 줄인다. 우선 큰 문제를 작은 문제로 나눠 봅시다. 문제의 첫 번째 예시 (40 30 30 50) 인경우를 살펴보겠습니다. 장의 수가 총 4개일 때 마지막으로 파일을 합쳐서 하나로 만들 때는 다음과 같이 3..
Algorithms/DP 2021. 10. 20. 10:31

[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

[프로그래머스] 다단계 칫솔 판매(C++)

다단계 칫솔 판매(Level 3) 문제 전체 문제 보기 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 접근법 문제를 정확하게 이해하는 것이 중요합니다. 아래와 같은 상황에서 sam이 칫솔을 하나 판매했다면 mary의 소득은 1이 됩니다. 그리고 sam 이 칫솔을 10개 판매했다면 mary의 소득은 9가 됩니다. 문제는 여기서 mary가 칫솔을 5개씩 두 번 판매했다면 mary의 소득은 9가 아니라 5 + 5 = 10이 됩니다. 판매 건당 추천인들의 수익이 결정되는 것이지 판매인의 전체 수익으로 추천인의..
Algorithms/Hash 2021. 10. 15. 18:11

[프로그래머스] 행렬 테두리 회전(C++)

행렬 테두리 회전(Level 2) 문제 전체 문제 보기 코딩테스트 연습 - 행렬 테두리 회전하기 6 6 [[2,2,5,4],[3,3,6,6],[5,1,6,3]] [8, 10, 25] 3 3 [[1,1,2,2],[1,2,2,3],[2,1,3,2],[2,2,3,3]] [1, 1, 5, 3] programmers.co.kr 접근법 문제에서 주어진 기능을 정확히 구현만 하면 되는 간단한 문제입니다. 이 문제의 가장 중요한 기능인 행렬의 회전은 시작 값을 temp에 저장한 후 한칸씩 shift 하여 계산 할 수 있습니다. 이때 회전에서 사용되는 수들 중 가장 작은 값을 함께 계산할 수 있습니다. 전체 구현 #include #include using namespace std; vector table; const i..
Algorithms/Implementation 2021. 10. 15. 15:12