개발을항해

1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net POINT Brute Force 모든 경우의 수를 탐색하여 정답을 찾는다. 전체 탐색을 사용한다. (순차 탐색, BFS, DFS 등) Backtracking + DFS = Combinations 백트래킹과 DFS를 함께 사용하여 조합을 구현한다. 풀이 Python은 조합을 구현한 내장 함수가 있기 때문에 풀이도 내장함수를 사용한 방법과 아닌 방법으로 두 가지이다. 방법1️⃣ 조합 내장 함수(combinations)를 사용한다...

1764번: 듣보잡 첫째 줄에 듣도 못한 사람의 수 N, 보도 못한 사람의 수 M이 주어진다. 이어서 둘째 줄부터 N개의 줄에 걸쳐 듣도 못한 사람의 이름과, N+2째 줄부터 보도 못한 사람의 이름이 순서대로 주어진다. www.acmicpc.net POINT 짧은 시간 안에 효율적으로 푸는 게 포인트 Python에서는 교집합을 사용하여 풀 수 있습니다(풀이1). 하지만 교집합을 사용하지 않고도 풀어 봤습니다(풀이2). 교집합 python에서 set은 합집합, 교집합, 차집합, 대칭 차집합을 사용할 수 있다. a = set([1, 2, 3]) b = set([2, 3, 4, 5, 6]) # 합집합 print(a | b) print(set().union(a, b)) # 교집합 print(a & b) prin..

11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net POINT 등비수열 재귀 함수 (Recursion function) 함수 안에서 함수 자신을 또 호출하여 사용하는 함수 하노이 탑 n개의 원반을 옮긴다면, 1단계. 제일 큰 원반을 제외한 나머지 (n-1)개의 원반을 2번으로 옮긴다. 이동 횟수: f(n-1) 번 2단계. 제일 큰 원반 1개를 3번으로 옮긴다. 이동 횟수: 1번 3단계. (n-1)개의 원반을 3번으로 옮긴다. 이동 횟수: f(n-1) 번 결론. 다음과 같은 식이 만들어지며, 등비수열로 ..

로그인 www.acmicpc.net POINT dfs (깊이 우선 탐색) 바이러스가 있는 곳(2)을 기준으로, 주변에 바이러스를 퍼뜨린다. → 바이러스 주변 칸의 값이 0이면 2로 바꾸고 주변을 계속 탐색한다. (방문 처리) 풀이 1. 새로운 벽을 3개 세운다. 2. 바이러스를 퍼뜨린다. 3. 안전 지역의 최댓값을 계산한다. 4. 모든 곳에 벽을 세워 볼 때까지 1 ~ 3을 반복한다. from itertools import combinations n, m = map(int, input().split()) graph = [[0] * m for _ in range(n)] new_graph =[[0] * m for _ in range(n)] # 복사한 그래프 blanks = [] # 빈칸 위치를 넣은 리스트 ..

** 백준 문제를 solution 타입 문제로 변형한 풀이입니다. ** 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5 ≤ N, M ≤ 100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 www.acmicpc.net POINT 내부와 외부 공간 분리하기 백준의 처럼 치즈가 외부에 노출되어도 다른 치즈 안에 있으면 녹지 않는다. 내부가 아닌 외부 공간에 두 곳 이상이 노출되면, 그 치즈는 1시간 뒤 녹는다. 치즈를 녹인 후 다시 내부와 외부를 분리해야 한다. 치즈 한번에 녹이기 1시간 뒤 녹는 치즈를 찾자마자 바로 녹이면 안된다. 그 치즈가 녹고 외부에 노출되는 치즈가 있다면 잘못 녹일 수 있..

2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net POINT DP 암호는 두 자리로 묶을 수 있는 수가 있으면 경우의 수가 증가한다. 자릿수가 늘어나면서 동일한 방법으로 가짓수를 구하고 앞 자리의 결과가 뒤의 자리에도 영향을 미치니까 DP(Dynamic Programing, 다이나믹 프로그래밍)으로 문제를 해결한다. index 0 1 (시작) 2 3 4 5 code 0 2 5 1 1 4 dp 1 1 2 2 4 6 현재 자리를 i라고 하면, 다음과 같은 규칙이 생긴다. 뒤의 두 자리가 암호 범위에 속할 경우 dp[i] = dp[i..