본문 바로가기

분류 전체보기

 (328)
[백준] 2294번 : 동전 2 https://www.acmicpc.net/problem/2294 2294번: 동전 2 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어 www.acmicpc.net 다이나믹 프로그래밍으로 해당 문제를 해결 하였습니다. 가치가 같은 동전이 있을 수 있기때문에 집합 자료구조를 이용하여 중복을 입력을 방지하였고, 동전을 작은 순서부터 순회하기위하여 정렬하였습니다. 이후 동전을 작은 순서부터 dp테이블을 순회하며 dp 테이블을 초기화 합니다. dp 점화식은 아래와 같이 정의 할 수 있습니다. i 인덱스를 코인으로 나눈 나머지가 0인경..
[백준] 1987번 :알파벳 https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 해당 문제는 완전탐색 + 깊이우선탐색 + 백트래킹 문제로 해결 할 수 있다. 같은 알파벳을 지날 수 없는것이 백트래킹 조건이고 깊이우선탐색과 완전탐색으로 모든 경로를 다 방문해 보면서 갈 수 없는 경로를 백 트래킹 하면 된다. R, C = map(int, input().split()) board = [input() for _ in range(R)] max_count = 0 def dfs(i..
[백준] 2580번 : 스도쿠 https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 해당 문제는 완전탐색 문제로 비어있는 테이블을 확인하고 비어있는 테이블에서 넣을 수 있는 수를 구한뒤 넣어본다. 그리고 넣은 곳을 반드시 초기화 해 주어야 다른 깊이우선 탐색에서 다시 넣어 볼 수 있다. table = [] for i in range(9): new = list(map(int, input().split())) table.append(new) def get_vailed(table): ..
[백준] 2585번 : 경비행기 https://www.acmicpc.net/problem/2585 2585번: 경비행기 경비행기 독수리호가 출발지 S에서 목적지 T로 가능한 빠른 속도로 안전하게 이동하고자 한다. 이때, 경비행기의 연료통의 크기를 정하는 것이 중요한 문제가 된다. 큰 연료통을 장착하면 중간 www.acmicpc.net 해당 문제는 이분탐색 + 너비우선탐색으로 문제를 해결하였습니다. 이분탐색의 mid는 기름통의 크기로 선정 하였고 기름통이 크면 클수록 들러야 하는 수가 적어지게되나 속도가 느려진다. 기름통이 작아지면 들러야하는 수가 많아지나 속도가 빨라진다. 해당 문제를 최적화 하기위해서는 기름통을 이분탐색한다. 또한 들어야하는 수를 계산 할때에는 너비우선탐색을 이용하여 최단거리를 구한다. import sys import..
[백준] 23083번 : 꿀벌 승연이 https://www.acmicpc.net/problem/23083 23083번: 꿀벌 승연이 첫째 줄에 \(N\), \(M\)이 공백으로 구분되어 주어진다. 다음 줄에는 구멍 칸의 개수 \(K\)가 주어진다. 이어서 \(K\)개 줄에 구멍 칸의 정보 \(x_i\), \(y_i\)가 공백으로 구분되어 주어진다. 이는 \(i\)번째 www.acmicpc.net (1,1) 위치에서 N,M 위치까지 갈 수 있는 경우의 수를 모두 구하는 문제이다. 해당 문제는 깊이우선탐색 으로 이미 방문했던 곳을 다시 방문하지 않기 위하여 dp 테이블을 생성하여 메모리제이션 한다. 점화식은 짝수 일때와 홀수 일때 각각 다르다. 움직 일 수 있는 조건을 잘 나누어서 풀면 된다. import sys sys.setrecursionl..
[백준] 19942번 : 다이어트 https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 해당문제는 모든 경우의 수를 확인하여 최저 값을 찾아내는 완전탐색 + 백트래킹 문제이다. 재귀함수를 통하여 현재 아이템을 포함하는 경우와 포함하지 않은 경우로 나누어 경우의 수를 만들어 비용의 최소값을 초기화 한 후 다음 조합을 계산할때는 이전에 계산했던 최소비용보다 높을 경우 백트래킹(탐색중단) 한다. from copy import deepcopy N = int(input()) mp, mf, ..
[백준] 9205번 : 맥주 마시면서 걸어가기 https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 해당문제는 BFS탐색 문제로 현재 위치에서 갈 수 있는 최단경로를 구해야하는 문제이다. 해당 위치로 부터 갈 수 있는 거리를 구해서 탐색하면 된다. 맥주 1병을 마시면 50미터를 갈 수 있으니 상근이는 20병을 담을수 있는 상자를 들고 다니니 20*50 = 1000 의 거리까지 갈 수 있다. 따라서 현재 위치에서 1000미터 까지의 거리가 탐색 조건이다. 해당 문제를 처음에는 깊이우선 탐색으..
[백준] 1107번 : 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 리모컨의 버튼을 눌러야하는 횟수를 계산해야하는 문제이다. 고장난 버튼이 있는데 고장난 버튼을 누르지 못한다. 고장난 버튼을 누르지않고 100번에서 N번까지 리모컨을 눌러야하는 최소 횟수를 구하는 문제이다. 처음에는 그리디 방식으로 접근을 하였습니다. N과 최대한 가까운수를 구하는 방법을 찾기 시작하였고 다음 테스트 케이스 반례로 그리디 문제로 해결 할 수 없다는것을 알게 되었습니다..

티스토리툴바