Baekjoon

신나는 함수 실행(#9184) Problem 재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15) a, b, c가 ..

알고리즘이 무엇인지 백준이 무엇인지 뭐부터 공부해야되는지 알지 못한채 단계별 풀이를 처음부터 냅다 풀면서 파이썬을 공부한지 알게된지도 2달이 되었다. 그동안 에러가 발생하면 파이썬 ~~ 하는 방법 을 검색하거나 기술문서를 읽었고 시간을 투자하여 여러가지 방법으로 풀어보려 고민하였고 최대한 해답을 찾아보지 않으며 풀이를 하고자 했다. 좋게 표현하자면 열정과 깊은 사고를 통해서 공부를 한 것이었지만 오랜 시간과 정신의 소모가 꽤 있었다. 백트래킹까지 거의 130개 가량의 문제 풀이를 하면서 깨닫게 된 사실이 있다. 1. 직관적 사고를 통해서 간단하다고 느끼는 사고 방식이 알고리즘 풀이에 항상 최선의 결과인것이 아니다. - 메모리 할당, 반복 회수, 구조 분석 등 알고리즘적 지식과 그에 따른 사고가 필요하다...

숏코딩보다는 백트래킹, BackTracking 을 이용하여 문제가 원하는 목적에 맞게 풀이해보았다. 목차 N과 M (1)(#15649) Problem 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 Hint 일반적인 백트래킹 방법을 이용하였다. Solution 백트래킹을 이용한 풀이 n, m = map(int, input().split()) res = [] def BackT(depth): if depth == m: for i in res: print(i, end=' ') print() return for i in range(1, n + 1): if i not in res: res.appe..

문제 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간을 때우기 위해서 수학 게임을 하기로 했다. 먼저 근처에 보이는 숫자 N개를 종이에 적는다. 그 다음, 종이에 적은 수를 M으로 나누었을 때, 나머지가 모두 같게 되는 M을 모두 찾으려고 한다. M은 1보다 커야 한다. N개의 수가 주어졌을 때, 가능한 M을 모두 찾는 프로그램을 작성하시오. 입력 첫째 줄에 종이에 적은 수의 개수 N이 주어진다. (2 ≤ N ≤ 100) 다음 줄부터 N개 줄에는 종이에 적은 수가 하나씩 주어진다. 이 수는 모두 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. ..

목차 배수와 약수(#5086) Problem 4 × 3 = 12이다. 이 식을 통해 다음과 같은 사실을 알 수 있다. 3은 12의 약수이고, 12는 3의 배수이다. 4도 12의 약수이고, 12는 4의 배수이다. 두 수가 주어졌을 때, 다음 3가지 중 어떤 관계인지 구하는 프로그램을 작성하시오. 첫 번째 숫자가 두 번째 숫자의 약수이다. 첫 번째 숫자가 두 번째 숫자의 배수이다. 첫 번째 숫자가 두 번째 숫자의 약수와 배수 모두 아니다. Hint 나머지를 이용하여 약수인지 배수인지를 구별하자 Solution 나머지를 이용한 풀이 a=b=1 res=[] while a+b!=0: a,b=map(int,input().split()) if a>b and a%b==0: res.append('multiple') el..

목차 직사각형에서 탈출(#1085) Problem 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. Hint 2차원 좌표내 거리 = del x + del y 테두리까지의 거리를 어떻게 표현해야할까 생각해보자 Solution 기하를 이용한 풀이 x,y,w,h=map(int,input().split()) print(min(min(x,w-x),min(y,h-y))) 테두리까지의 최소값은 delx와 y 중에 최소값을 고르면 된다 네 번째 점(#3009) Problem 세 점이 주어졌을 때, 축에 평행한 직사각형을 만들기 위해서 필요한 네 번째..