분류 전체보기166 [Baekjoon] 16234번: 인구 이동 https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제 해결 과정 착안 너비 우선 탐색(breadth-first search, BFS) 알고리즘을 응용하여 날짜 별로 연합이 존재할 수 있는지 탐색해보고, 연합이 존재한다면 각 연합 별로 연합에 속하는 나라들의 인구를 산술평균 값으로 갱신하는 과정을 통해 문제를 해결하고자 하였다. 연합이 존재할 수 있는지 판단하는 과정에서, 인접한 나라와 직접적으로 국경선이 개방되어 연결되지 않더라도.. 2023. 7. 26. [Baekjoon] 11404번: 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 해결 과정 착안 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)에 따라 문제에서 요구하는 도시 간 거리를 계산하고자 하였다. 음수 가중치 간선이 없기 때문에 일반적인 방법으로 문제를 해결하고자 하였다. 구현 알고리즘을 구현함에 있어서, 삼중 반복문의 루프 변수 배치 순서 및 시작 도시와 도착 도시 사이의 연결이 없는 경우를 0으로 표시하는 부분에 유의하여 프로그래밍 하였.. 2023. 7. 25. [Baekjoon] 2293번: 동전 1 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 과정 착안 주어지는 $n$개의 동전의 가치를 편의상 각각 $c_i \space (1 \leq i \leq n)$라고 하면, 종류가 다른 동전이 하나하나 주어질 때마다 아래와 같은 원리에 의해 단계별로 사용하는 동전의 수를 늘려가면서 가치의 총 합이 $k$ 이하의 자연수가 되도록 만드는 경우의 수를 귀납적으로 구할 수 있다. [전제조건] 1) 동전들을 사용하여 만들 수 있는 가치의 총 합은.. 2023. 7. 24. [Baekjoon] 2447번: 별 찍기 - 10 https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 문제 해결 과정 착안 메모리를 절약할 수 있는 더 좋은 방법이 있을 수 있지만, 간편한 방법으로 문제를 해결하고자 하였다. 프랙탈(fractal) 형태를 먼저 재귀적으로 구하여 저장한 다음, 한 행씩 문자열로 변환하여 출력해 문제를 해결하고자 하였다. 구현 프랙탈 모양의 형태를 최대한 적은 메모리를 사용해 저장해보려고 bool 형 배열을 이용해보았다. 별이 찍히는 부분을.. 2023. 7. 24. [Programmers] 정수 삼각형 https://school.programmers.co.kr/learn/courses/30/lessons/43105 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 해결 과정 착안 동적계획법(dynamic programming)을 통해 가장 아래 층의 숫자들부터 인접한 두 개씩 비교하여 위의 숫자로 더해나가는 방식으로 문제를 해결하고자 하였다. 구현 [스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~ 더보기 #include #include using namespace std; int solution(vector triangle) { for.. 2023. 7. 21. [Baekjoon] 18405번: 경쟁적 전염 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 문제 해결 과정 착안 우선순위 큐(priority queue) 자료 구조를 활용하여, 바이러스 번호가 낮은 순으로 먼저 너비 우선 탐색(breadth-first search, BFS)을 수행함으로써 문제를 해결하고자 하였다. * 우선순위 큐 대신, 배열 및 정렬 알고리즘을 사용하여 해결하면 속도 측면에서 더 유리한 것 같다. 구현 좌표를 나타내기 위한 구조체 Coor.. 2023. 7. 21. 이전 1 ··· 8 9 10 11 12 13 14 ··· 28 다음
