[백준] 7579번 - 앱 (한줄평) 전에 풀었던 냅색 문제를 잘 이해했다면 어렵지 않게 해결핧 수 있었던 문제. 하지만 더 좋은 풀이를 생각해봐야할 문제로 다음에 다시 한번 풀어보면 좋을 것 같다. 유사 문제: 12865 https://hseungyeon.tistory.com/search/%EB%83%85%EC%83%89 공부 hseungyeon.tistory.com 앱의 개수가 N, 필요한 메모리가 M일 때, 둘째 줄의 N개의 정수는 현재 활성화 되어 있는 앱 A1, ..., AN이 사용 중인 메모리의 바이트 수인 m1, ..., mN을 의미하며, 셋째 줄의 정수는 각 앱을 비활성화 했을 경우의 비용 c1, ..., cN을 의미한다 (단, 1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000,000이며,..
[백준] 2629번 - 양팔 저울 (한줄평) 생각보다 머리가 복잡했던 문제.. 점화식을 만들기가 어려웠다.. 무조건 복습필수다 풀이 시간: 90분 이내 1) 문제 해결 아이디어 추의 개수 n(30 이하), n개의 추의 무게(500이하의 자연수)가 오름차순으로 주어지고 구슬의 개수 m(7이하), m개의 구슬의 무게(40000 이하의 자연수)가 주어진다. 양팔 저울에 추를 사용하여(올리거나 올리지 않을 수 있음) 주어진 m개의 각 구슬의 무게를 확인할 수 있는지 여부를 구하는 문제다. 각 추를 사용할 때 3가지 경우의 수가 있다. 즉, 추의 개수가 n이면 추를 이용하여 구할 수 있는 모든 경우의 수는 3**n이 된다. n의 값이 최대 30이므로 단순하게 완전 탐색을 한다면 이 문제는 시간초과로 풀 수 없게된..
[백준] 11049번 - 행렬 곱셈 순서 (한줄평) 이전에 풀었던 문제와 풀이 방식이 비슷해서 풀 수 있었지만 다음에 다시 풀면 못 풀 것 같기도 한 문제.. 복습이 꼭 필요하다! 유사 문제: 11066 https://hseungyeon.tistory.com/313 [다이나믹 프로그래밍] ★★ 11066번 - 파일 합치기 [백준] 11066번 - 파일 합치기 (한줄평) 풀릴듯 하면서 풀리지 않아서 풀이를 보니 생각보다 더 복잡한 문제였다. 풀이를 봐도 쉽게 이해가 가지 않았기때문에 꼭 복습이 필요하다! 풀이 시간: 3 hseungyeon.tistory.com 풀이 시간: 60분 이내 1) 문제 해결 아이디어 n개의 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 구하는 문제다. 이 문제의 핵심은 대각선방향으..
[백준] 11066번 - 파일 합치기 (한줄평) 풀릴듯 하면서 풀리지 않아서 풀이를 보니 생각보다 더 복잡한 문제였다. 풀이를 봐도 쉽게 이해가 가지 않았기때문에 꼭 복습이 필요하다! 풀이 시간: 3시간 이내 1) 문제 해결 아이디어 소설을 구성하는 장의 수(k)와 k개의 파일의 크기(f)가 주어졌을 때 모든 장을 합치는데 필요한 최소 비용을 구하는 문제다. 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산해야한다...
[백준] 10971번 - 외판원 순회 2 (한줄평) 설계자체는 단 시간에 했지만 시간초과를 해결하는데 시간이 오래걸렸던 문제로 꼭 복습 필요한 문제!! 이 문제는 외판원 순회 문제(TSP)로 N과 비용행렬이 주어졌을 때 외판원 순회에 필요하 최소 비용을 구하는 것이다. 1 ~ N 번호가 매겨진 도시들을 모두 거쳐 원래의 도시로 돌아오는 순회 여행을 말한다. 완전탐색(백트래킹)문제로 DFS를 이용하여 풀 수 있다. 풀이 시간: 90분 이내 1) 문제 해결 아이디어 1. 비용(graph) 입력 및 이동 경로(temp), 방문 여부(visited)를 저장할 리스트 생성 2. dfs(0, 0) 호출 -> 깊이= 0, 비용= 0으로 시작 3. n개 도시를 다 선택했고 마지막 도시→처음 도시로 가는 비용이 0이 아..
[백준] 14889번 - 스타트와 링크 (한줄평) 아이디어를 떠올리고 구현하는 것은 어렵지 않았으나 시간단축을 위한 방법을 고민해봐야했던 문제! 1 ~ N 번호를 가진 사람들이 있을 때 두 팀으로 나누었을 때 각 팀의 능력치(팀에 속한 모든 쌍의 능력치의 합)의 차이의 최솟값을 구하는 문제였다. 두 팀으로 나눌 수 있는 모든 경우의 수를 따져봐야하는 완전 탐색(백트래킹)문제로 DFS를 이용하여 풀 수 있다. 물론 조합을 구할 때 combinations 라이브러리를 사용할 수도 있다. 여기서 풀이 1, 2 둘다 DFS를 이용하여 구현했고 설계방식에 조금 차이가 있는데 풀이2가 메모리, 시간 측면에서 더 효율적이므로 풀이2를 추천한다. (풀이1) 내 풀이 풀이 시간: 30분 이내 1) 문제 해결 아이디어 이..
[백준] 15683번 - 감시 풀이 시간: 2시간 이내 1) 문제 해결 아이디어 사각 지대의 최소 크기를 출력하는 문제다. 처음에는 아무생각없이 BFS로 풀어도 되나하는 문제였지만 cctv들의 방향을 설정하는 모든 경우의 수를 고려하여 풀어야 하는 완전탐색 문제로 DFS를 이용하여 풀어야했다. 지금까지 풀었던 문제는 되게 단순하고 정형화된 문제였기때문에 새로운 방식으로 풀려고 아이디어를 떠올리는데 시간이 많이 걸렸다. 추후 꼭 복습이 필요한 문제!! 나는 북, 동, 남, 서 방향을 차례대로 0, 1, 2, 3 으로 설정하였다. CCTV 번호에 따른 방법(방향 경우의 수)수는 다음과 같다. 첫번째 오류. 틀렸습니다 nx, ny를 x, y로 초기화해야 하는데, dx를 1번 더해준 값으로 초기화해서 문제가 생..
[백준] 2503번 - 숫자 야구 굉장히 익숙한 소재라 문제를 이해하고 설계를 하는데 어려움이 없었으나 오류를 고치느라 시간이 좀 걸렸다. 서로 다른 숫자로 구성된 세자리수를 영수가 생각하고 있을 때, (민혁이가 질문한 세자리수, 스트라이크 개수, 볼 개수)를 보고 가능성이 있는 답의 총 개수를 구하는 문제로 전형적인 완전탐색 문제다. 영수가 생각할 수 있는 수의 모든 경우의 수는 순서가 상관이 있기 때문에 순열로 풀 수 있는데 DFS를 이용하거나 permutations를 이용한 방식 2가지가 있다. (풀이1) DFS 이용 풀이 시간: 40분 이내 1) 문제 해결 아이디어 1. 깊이가 3일 때 종료 num이 세자리수가 되었으므로 종료 1-1. 각 질문(세자리수)에 대해 스트라이크, 볼 개수에 모순이 생기..
