분류 전체보기
[백준/1003/파이썬] 피보나치 함수
https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net Problem N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오. 조건 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다. SOL 피보나치 함수의 Flow chart를 그려보면, 어렵지 않게 규칙을 발견해낼 수 있다. F(N) = N번쨰 피보나치 수 일때, 0과 1의 호출횟수. F(N) = ( zero ,one ) 이라..
[알고리즘,개념] DP(Dynamic Programming)
DP(Dynamic Programming) Dynamic Programming , 컴퓨터에서 이야기하는 Static/Dynamic할 때, 정적/동적의 개념이 아니다. 일반적이지 않게 풀기, 멋있는 방법으로 풀기라고 생각해서, Dynamic Programming이라고 지었다고 한다. 개념은, 문제의 Scale(size)가 너무 커서, 작은 문제의 답을 구하고, 그 답을 통해서, 최종적인 답을 구할 수 있게 되는 형태의 문제들을 DP문제라고 한다. 부분 문제 반복(Overlapping subproblem)과 최적 부분 구조(Optimal Substrcture)를 가지고 있다. DP는 말로 정의내리기가 참 애매한거 같다. 그래서, 난 DP가 나오게된 배경을 알아봤고, 도움이 된 부분이 있어서 , DP의 등장배..
[백준/1987/파이썬] 알파벳
https://www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net Problem (0,0)에서 시작해서 조건에 맞게 말을 움직여보자. 조건 같은 알파벳을 2번 지날 수 없다. SOL) 간단한 경로찾기 문제이다. BFS/DFS 어느것이든 가능할거 같다. DFS로 풀어보았다. DFS는 pypyp3로 통과가 되었고, BFS는 python3로도 통과가 되었다. import sys input= sys.stdin.readline R,C = map(int,input(..
[백준/17136/파이썬] 색종이 붙이기
https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net Problem 정사각형 모양을 한 다섯 종류의 색종이(1*1,2*2,3*3,4*4,5*5)를 10*10 종이 위에 붙이려고 한다. 1이 적힌 모든 칸을 붙이는데 필요한 색종이 최소 개수를 구해보자. 조건 색종이를 붙일 때는 종이의 경계 밖으로 나가서는 안되고, 겹쳐서 붙일 수 없다. 또, 칸의 경계와 일치하게 붙여야한다. SOL) 처음에 그리디로 접근해볼까? 라는 생각이 드는 문제였다. ..
[알고리즘,개념] Backtracking
Backtracking 정의 : 모든 조합의 수(경우의 수)를 살펴본다. 단, 특정 조건이 만족할 때(Promising)만, 그 조합을 본다. - "the algorithm design manual" (1997.스티븐 스키에나) 모든 경우의 수를 찾는 것보다, 경우에 따라, 훨씬 빠를 수 있다(pruning). Promising,Pruning(가지치기) 기법을 이용한다. Promising: 해당 루트가 조건에 맞는지를 검사하는 기법. Pruning : 조건에 맞지 않으면, 포기하고, 다른 루트로 바로 돌아서서, 탐색의 시간을 절약하는 기법. 너무나도 유명한 예제 중 하나인, N-Queen 문제를 살펴보면서, Promising의 개념이 뭔지, Pruning의 개념이 뭔지 구체화 시켜보자. N-Queen N..
[백준/1039/파이썬] 교환
https://www.acmicpc.net/problem/1039 1039번: 교환 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. www.acmicpc.net Problem 0으로 시작하지 않는 정수 N이 주어진다. i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다. 위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오. 조건 첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다. SOL 자릿수를 K번 바꿨을때,만들 수 있는 가장 큰 수를 출력하면 되는 시뮬레이션 문제. 하지만,..
[백준/2580/파이썬] 스도쿠
https://www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net Problem 스도쿠의 빈칸을 채워라! 조건 스도쿠의 규칙이랑 같다. 단, 스도쿠를 완성 시키는 방법이 여러가지라면, 그 중에 아무거나 1개만 출력해라. SOL) 우리가 잘 아는 스도쿠이다. 일단, 0인 곳을 기준으로, 행/렬/3*3 작은 직사각형을 확인해보면 된다. 하지만, 숫자를 넣어봤을때, 완성되지 않는다면,그 이전에 넣었던 곳이 잘못넣어진거이므로, 다른 숫자를 넣어봐야함. 즉, backtr..
[백준/1525/파이썬] 퍼즐
https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net Problem 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 조건 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다. 어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. SOL) 보기에는 엄청 간단해 보였던 문제였다. ..