본문 바로가기

알고리즘/백준

 (263)
[백준] 15686번 : 치킨거리 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 집의 위치와 치킨집의 위치를 담는 리스트를 각각 생성합니다. 그리고 최대N개의 치킨 집을 선택해서 치킨거리의 최소값을 구해야 하기때문에 최대 N개를 선택할수 있는 경우의 수를 생성합니다. 치킨집의 위치를 담는 리스트의 조합(Combination) 을 이용하여 치킨집의 위치의 조합을 만들고 그 조합을 사용하여 각각의 치킨거리를 계산한뒤 최소값을 출력해냅니다. from itert..
[백준] 3109번 : 빵집 안녕하세요. 오늘은 그래프 탐색 알고리즘 문제를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 해당 문제는 깊이 우선탐색 + 그리디로 답을 도출 해낼 수 있습니다. 깊이우선탐색 : 한 위치에서 빵집까지를 갈 수 있는 경로를 탐색합니다. 1) 열이 위에서 아래 순서로 탐색해보는 조건 - 위에서 아래 순서로 탐색할때에는 우선순위를 오른쪽 대각선위 , 오른쪽, 오른쪽 대각선 아래 순서로 두어야 한다. R, C = map(int, input(..
[백준] 1700번 : 멀티탭 스케줄링 안녕하세요. 매일공부하는 개발자 빅광스입니다. 저번주는 다이나믹 프로그래밍 문제를 풀어보았는데요, 이번주는 그리디 알고리즘 문제를 풀어보려고 합니다. https://www.acmicpc.net/problem/1700 1700번: 멀티탭 스케줄링 기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전 www.acmicpc.net 오늘의 문제는 멀티탭 스케줄링 문제입니다. 문제의 내용은 위의 사이트에서 참고하시고 오세요. 저는 이 문제를 풀때 여러가지 테스트 케이스를 생각하면서 공책에 써가면서 최적해를 구하는 과정을 생각해보았습니다. 1) 현재 콘센트에 현재 넣으려는 아이템의..
[백준] 2579번 : 계단오르기 안녕하세요. 매일 공부하는 개발자 빅광스입니다. 제가 아직 다이나믹프로그래밍이 익숙치 않아서 오늘도 또한 다이나믹 프로그래밍 문제를 풀도록 하겠습니다. https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 계단오르기 문제인데요, 자세한 내용은 링크를 타고 들어가서 문제를 확인 해보시기 바랍니다. 우리는 이 문제를 해결하기위하여 Sub Problem을 정의하고 메모리제이션 기법을 활용하여 이전에 올라왔던 계단위치의 합을 활용하여 시간 복잡도를 줄일 것 입니다. 우..
[백준] 1149번 : RGB거리 안녕하세요. 매일공부하는 개발자 빅광스입니다. 오늘은 다이나믹 프로그래밍 문제를 풀어보겠습니다. https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 먼저 저는 다이나믹 사고 능력이 아직 부족하여 모든 경우의 수를 다 따져보는 계산을 해보았습니다. dfs 탐색을 통하여 모든 경우를 다 방문하고 방문한 값을 저장하고 그 저장한 값들중 min 값을 구하여 정답을 도출하였습니다. char = ['R', 'G', 'B'] r = [] ..
[백준] 11726번 : 2xn 타일링 안녕하세요. 매일공부하는 개발자 빅광스입니다. 오늘은 다이나믹 프로그래밍의 문제를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나..
[백준] 1339번 : 단어수학 안녕하세요. 개발자 빅광스 입니다. 오늘은 그리디 알고리즘 문제를 풀어보도록 하겠습니다. https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개..

티스토리툴바