python

문제https://www.acmicpc.net/problem/11726백준 문제집 - BOJ 길라잡이 베타 (1)풀이2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. DP(동적 프로그래밍)로 분류되어있으니 점화식을 사용하는건 당연하고, 대강 체크해본결과 피보나치일거란 예감이 들었다.일단 n = 1, 2, 3...일때를 가정하며 계산해보니 역시 피보나치 수열과 비슷한 결과가 나왔다.n = 1일때 👉 1n = 2일때 👉 2n = 3일때 👉 3n = 4일때 👉 5... 기존의 피보나치 수열은 f(0) = 0, f(1) = 1를 베이스로 f(2) = 1, f(3) = 2...이므로 한칸씩 땡겨주기만 하면 된다.즉 f(1) = 1, f(2) = 2...로 진..

문제https://www.acmicpc.net/problem/10819백준 문제집 - 대학생 기본반알고리즘 분류: 브루트포스, 백트래킹풀이N개의 정수로 이루어진 배열 A가 주어진다.이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|  처음엔 문제를 |A[0] - A[1]| + |A[2] - A[3]| + ... + |A[N-2] - A[N-1]| 로 봤었다.그래서 한 시도 👉 A 정렬 후 (1번째로 큰 값 - 1번째로 작은 값, 2번째로 큰 값 - 2번째로 작은 값...) 반복하기.물론 문제 자체를 잘못 봤기때문에 제대로 된 답이 나오지 않았고^^;;간단하..

문제https://www.acmicpc.net/problem/2589백준 문제집 - 대학생 기본반풀이사실 보물이고 나발이고, 이 문제의 핵심은 "육지-육지 간의 거리중 가장 최댓값"을 구하는것이다.보물섬 지도에서 L은 육지, W는 바다를 나타낸다.육지는 모두 붙어있는것이 아닌 몇개의 섬으로 이루어져있는 형태다.가장 먼 거리를 D라고 했을때, 어느 L이 시작점/끝점 인지 불분명하다.따라서 L을 발견할때마다 bfs를 실행해줘야 한다. 전체 코드# 문제집 - 대학생 기본반# 문제: https://www.acmicpc.net/problem/2589# 메모리: 34072KB / 시간: 4264msfrom sys import stdinfrom collections import dequeinput = stdin.re..

문제https://www.acmicpc.net/problem/2606백준 단계별로 풀어보기 - 그래프와 순회풀이어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오. 컴퓨터 == 노드로 생각하고, 1번 노드와 연결되어 있는 노드의 갯수를 구한다.DFS, BFS 모두 선택 가능한 문제다. 먼저 빈 리스트가 포함된 2차원 리스트를 생성한다음, 주어진 노드들을 양방향으로 저장한다.직접 연결된 컴퓨터끼리만 영향을 주는게 아니고, 1번 컴퓨터로부터 파생된 모든 컴퓨터들은 모두 감염되는것이기 때문이다.network = [[] for _ in range(N+1)]f..

문제https://www.acmicpc.net/problem/1086백준 단계별로 풀어보기 - 동적 계획법 3풀이비트마스킹 + DP 를 고려하지 않고 풀었을땐 쉬웠는데, 이 둘을 적용하려니 어려웠던 문제다...생각해보면 당연하다. 단순히 permutations 모듈을 사용해서 풀면 메모리&시간이 엄청나게 소요된다.그래서 시도했는데...DP도 어려운데 비트마스킹까지 적용하려니 힘들었다... 결국 다른 풀이를 참고해서 공부했다^^;; 다른 풀이들을 찾아보니 단순히 저 둘을 접목시킨다고 해결되는 문제가 아닌듯했다. (시간초과)더 효율적인 방법을 생각해내야하는 문제다.  어떠한 수를 K로 나누었을때 나머지값의 범위는 0 ~ K-1이다.이걸 이용해서 주어진 집합의 각 숫자 S[i]에 대해 가능한 나머지값들을 저장..

문제https://www.acmicpc.net/problem/1311백준 단계별로 풀어보기 - 동적 계획법 3풀이N명의 사람과 N개의 일이 있다. 각 사람은 일을 하나 담당해야 하고, 각 일을 담당하는 사람은 한 명 이어야 한다. 또한, 모든 사람은 모든 일을 할 능력이 있다.사람은 1번부터 N번까지 번호가 매겨져 있으며, 일도 1번부터 N번까지 번호가 매겨져 있다.Dij를 i번 사람이 j번 일을 할 때 필요한 비용이라고 했을 때, 모든 일을 하는데 필요한 비용의 최솟값을 구하는 프로그램을 작성하시오. 동적 계획법 3 문제는 모두 비트마스킹을 통해 풀어야 한다. 예시 입력값대로 N = 3이라고 가정해보자.우리는 3개의 비트를 사용하여 일의 진행 상황을 나타내야 한다.000 => 아무 일도 선택되지 않은 ..