분류 전체보기 검색 결과

해당 글 235건

[BOJ 16234] 인구 이동 (C++)

인구 이동 (Gold 5) 문제 전체 문제 보기 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 접근법 이번 문제는 DFS/BFS를 활용한 구현, 시뮬레이션 문제입니다. 여기서는 BFS를 활용해서 풀이를 진행합니다. 먼저 매일 한 번씩 BFS탐색을 통해서 각 국가들의 인구수 차이를 확인하여 국경을 열어서 연합을 만들 수 있는지 확인 만들어진 연합의 평균 인구수 반환 BFS로 반환받은 연합의 평균 인구수를 활용하여 각 연합별 인구 이동 결과 반영 위 작업을 더이상 인구가 이동하지 않을 때까지 반복하..
Algorithms/DFS & BFS 2021. 10. 28. 14:04

[BOJ 2229] 조 짜기 (C++)

조 짜기 (Gold 5) 문제 전체 문제 보기 2229번: 조 짜기 알고스팟 캠프에 N(1≤N≤1,000)명의 학생들이 참여하였다. 학생들은 열심히 공부를 하고 있었는데, 어느 날 조별 수업을 진행하기로 하였다. 조별 수업의 목적은 잘 하는 학생들과 덜 잘 하는 학 www.acmicpc.net 접근법 이번 문제는 동적 계획법을 활용하여 \(O(n)\) 시간 복잡도로 풀 수 있는 문제입니다. 동적 계획 법으로 문제를 풀기 위해서는 일반화하는 과정이 필요합니다. 먼저 동적 계획법에서 사용할 dp[i]은 i번째 사람까지 조를 짰을 경우 최댓값으로 정의할 수 있습니다. 그리고 초기값은 다음과 같이 설정할 수 있습니다. dp[0]은 0번 사람 한 명만 들어오기 때문에 최대 값은 0일 수밖에 없습니다. dp[1]은..
Algorithms/DP 2021. 10. 27. 10:12

Inheritance 의 이해 - ⑤ Virtual Inheritance

Inheritance 의 이해 - ⑤ Virtual Inheritance 앞서 다중 상속 글에서 아래와 같이 다이아몬드 상속이 이루어질 경우 조상 클래스인 animal 클래스가 두번 생성된다고 설명했다. 이 문제는 가상 상속(Virtaual Inheritance)으로 해결할 수 있다. 이번 글에서는 가상 상속이 메모리 레벨에서 어떻게 동작하는지 살펴본다. 먼저 가상 상속을 사용하는 방법은 다음과 같다. class Animal { public: virtual void Speak() { std::cout
Computer Science/C++ 2021. 10. 23. 09:40