SWLUG/파이썬 (코딩테스트) 썸네일형 리스트형 [파이썬/백준] 1012번 : 유기농배추 https://www.acmicpc.net/problem/1012 문제 설명 배추흰지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것-> 배추들이 모여있는 곳에는 배추흰지렁이가 한 마리만 있으면 되므로 서로 인접해있는 배추들이 몇 군데에 퍼져있는지 조사하면 총 몇 마리의 지렁이가 필요한지 알 수 있다. 예를 들어 배추밭이 아래와 같이 구성되어 있으면 최소 5마리의 배추흰지렁이가 필요하다. 0은 배추가 심어져 있지 않은 땅이고, 1은 배추가 심어져 있는 땅을 나타낸다. 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 첫째 줄 : 배추를 심은 배추밭의 가로길이 M(1 ≤ M ≤ 50)과 세로길이 N(1.. 더보기 [파이썬/백준] 1011번 : Fly me to the Alpha Centauri https://www.acmicpc.net/problem/1011 문제 설명 k광년을 이동하였을 때는 k-1 , k 혹은 k+1 광년만을 다시 이동할 수 있다. 예를 들어, 이 장치를 처음 작동시킬 경우 -1 , 0 , 1 광년을 이론상 이동할 수 있으나 사실상 음수 혹은 0 거리만큼의 이동은 의미가 없으므로 1 광년을 이동할 수 있으며, 그 다음에는 0 , 1 , 2 광년을 이동할 수 있는 것이다. ( 여기서 다시 2광년을 이동한다면 다음 시기엔 1, 2, 3 광년을 이동할 수 있다. ) x지점에서 y지점을 향해 최소한의 작동 횟수로 이동하려 한다. 하지만 y지점에 도착해서도 공간 이동장치의 안전성을 위하여 y지점에 도착하기 바로 직전의 이동거리는 반드시 1광년으로 하려 한다.김우현을 위해 x.. 더보기 [파이썬/백준] 9184번 : 신나는 함수 실행 9184번 : 신나는 함수 실행https://www.acmicpc.net/problem/9184 문제 설명 재귀 문제로 시간이 너무 오래 걸리는 것을 해결해야 한다. 메모이제이션을 통해 해결해야 하므로 간단히 개념을 살펴보자. (아래 글을 바탕으로 작성하였습니다.) 메모이제이션(Memoization) 개념 및 예시, 재귀(recursion)이번 포스팅에서 다루는 memoization 메모이제이션은 DP 동적 계획법 알고리즘에서 핵심이 되는 기술로 중복 계산을 제거함으로써 프로그램의 전체적인 실행 속도를 빠르게, 성능을 향상할 수 있는wondytyahng.tistory.com 메모이제이션(memoization)은 dp(dynamic programming, 동적 프로그래밍) 알고리즘에서 핵심이 되는 .. 더보기 [파이썬/백준] 1932번 정수 삼각형 1932번 : 정수 삼각형https://www.acmicpc.net/problem/1932 문제 설명 Dynamic programming 알고리즘을 이용하여 푸는 문제인데 개념을 다시 리마인드 하고자 정리가 잘 된 글을 가져와봤다.모두 참고하여 아래 글을 정리한 것이다. [Python] DP(Dynamic Programming) 알고리즘이 뭘까?/ 개미전사 풀이 / 백준 1463번 1로 만들기 풀이다이나믹 프로그래밍이란? 앞에서 계산한 식을 배열에 미리 저장하여 연산속도를 증가시키는 프로그래밍 계산한 건 다시 계산하지 않는 게 중요하다 DP의 예: 피보나치 수열 DP = [1, 1, 2, 3, 5, 8, 13kill-xxx.tistory.com dp란 앞에서 계산한 식을 배열에 미리 저장하여.. 더보기 [파이썬/백준] 2231번 분해합 2231번 분해합 https://www.acmicpc.net/problem/2231 문제 확인 예제# 입력216# 출력198 문제 분석 자연수 N의 가장 작은 생성자 구하기 (없는 경우/ 여러 개의 경우도 존재) - 없으면 0 출자연수 N = N과 N을 이루는 각 자리수의 합 (ex. 256 = 245 + 2 + 4 + 5 ) 1부터 입력받은 n까지 for문을 통해 분해합을 구해보고 그 합이 n과 같다면 출력 후 break해준다.같지 않을 시, 분해합이 없는 경우로 간주하여 0 출력하고 다음 반복을 진행한다. 분해합을 구하는 알고리즘이 관건인 것 같은데...! 범위 내의 모든 수에 접근하기 위해 반복 변수인 i를 이용해준다. i의 각 자리수를 우선 다 더해서 위의 예시에서는 (2 + .. 더보기 [파이썬/백준] 2798번 블랙잭 2798번 블랙잭https://www.acmicpc.net/problem/2798 문제 설명 예제 # 입력5 215 6 7 8 9# 출력21# 입력10 50093 181 245 214 315 36 185 138 216 295# 출력497 문제 분석 N장의 카드 중 3장을 뽑아 합이 M을 넘지 않으며 가장 가까운 수가 되도록 해야한다. -> 모든 방식을 탐색하는 브루트포스 1) n : 카드 개수 , m : 카드합의 최댓값을 입력받는다. int로 맵핑해준다. 합들을 저장해줄 empty list = lst 를 생성한다. 2) for문을 3번 중첩 사용하여 hap(합)을 구한 후 m보다 작거나 같다면, lst(리스트)에 저장해준다. (문제의 조건중 하나가 m 넘으면 안 되므로) .. 더보기 [파이썬/백준] 1 2 3 더하기 & 부녀회장이 될테야 9095번 : 1 2 3 더하기https://www.acmicpc.net/problem/9095 문제 확인 문제 분석 정수 n이 주어졌을 때, n을 1,2,3만 가지고 합의 방법으로 나타낼 수 있는 "방법의 수"를 구하는 프로그램을 작성해야 한다. 1,2,3만 가지고 나타내야 하므로 각각의 값에서 나타낼 수 있는 방법의 수를 계산해보도록 하자피보나치 수열과 비슷한 방식으로 동적 프로그래밍 방법을 이용하면 될 듯 하다. n이 1일 경우 : +1 n이 2일 경우: 1+1, +2 n이 3일 경우: 1+1+1, 1+2, 2+1, +3 n이 4 이상일 경우.... 예를 들어 n이 4라고 해보자 (1)+1+1+1-> n(1) +3 // 1가지 (1+1)+2(2+2)-> n(2) +2 // 2가지.. 더보기 [파이썬/백준] 내리막길, 양팔저울 1521번 : 내리막길https://www.acmicpc.net/problem/1520 문제 설명 우선 해당 프로그램을 작성하기 위해서는 ‘DP (동적 알고리즘, Dynamic Algorithm) ’와 DFS (깊이 우선 탐색, Depth-First Search)를 알아야 하므로 간단하게 개념을 짚고 넘어가도록 하겠다. 참고 알고리즘 - Dynamic Programming(동적 계획법)1. 개요 DP, 즉 다이나믹 프로그래밍(또는 동적 계획법)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로hongjw1938.tistory.com 문제 분석 간단한 로직 먼저 설명하자면, 우선 이 문제는 모든 경우의 수를.. 더보기 이전 1 2 다음
