내 맴

문제 ) https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net [ 풀이 ] 문제를 읽어보고 그냥 재귀함수를 사용해서 문제를 풀되 fib(0)과 fib(1)이 얼마나 호출되는지 알아내게끔 코드를 변경하라는 건줄 알았다. 문제를 풀고 제출해보니 시간초과가 되어버렸다. 그래서 시간초과를 하지 않는 새로운 방법으로 문제를 풀어보았다. 바로 0과 1 호출 횟수에 대한 List를 만들어 Dynamic Programming으로 문제를 푸는 것이다 예를 들어 , fib(3)= fib(2)+fib(1) = fib(0) + fib(1) + fib(1) 로 fib(..

문제 ) https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 문제 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)�� www.acmicpc.net [ 풀이 ] 피보나치 수열의 경우 재귀함수를 사용하면 안되는 대표적인 문제이다. 재귀함수를 사용하게 되면 중복호출이 매우 많아지기 때문이다. 재귀 알고리즘을 이용해 피보나치 수를 구하려면 의사코드는 이런식으로 작성된다 이때, Fib함수가 얼마나 호출되는지 보기 위해서 그래프로 그려보았다. 재귀함수를 이용해 피보나치 수를 구하면 그래프의 분홍색 동그..

문제 ) https://www.acmicpc.net/problem/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net [ 풀이 ] 산술평균, 중앙값, 범위를 구하는 방법은 매우 쉬웠다. 최빈값을 구하기 위해서 Collections모듈의 Counter class를 이용해주었다. 우선, 입력한 N개의 숫자 list를 정렬해주고 시작 ✔ 산술평균 : list의 전체합을 N으로 나눠준 값이다. 소수점 이하 첫째 자리에서 반올림 해야하므로 round함수를 이용해준다. ✔ 중앙값 : list를 정렬했으므로 list의 중간 index..

문제 ) https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net [ 풀이 ] 이 문제는 브루트 포스 (Brute Force) Algorithm을 이용해서 풀어주었다. 1~N번까지의 사람들을 2개의 팀으로 나눠야하는데 itertools library의 combinations 함수를 이용하여 N개를 2개의 group으로 만들어주는 순열을 구해 문제를 푼다. 우선, 두팀의 능력치의 차를 구해주는 함수인 teamsub function을 만들어 주었다. ✔ startteam의 능력..

문제 ) https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net [ 풀이 ] Baekjoon 사이트에는 이 문제가 Backtracking Algorithm이라고 분류되어있길래 Backtracking방법으로 풀어야 하나 했는데, promising한 node들을 추려줘야하는데 그 기준이 없는거 같았다. Maximum과 Minimum값을 둘 다 구해줘야하기 때문에 그냥 모든 경우의 수를 확인해야만..

문제 ) https://www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [ 풀이 ] Backtracking Algorithm을 사용하여 문제를 풀어주었다 - Backtracking Algorithm 이란? ✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법 ✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다 - Node가 Promising한지 ..

문제 ) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net [ 풀이 ] Backtracking Algorithm을 사용하여 문제를 풀어주었다 - Backtracking Algorithm 이란? ✔ 해를 찾는도중에 해가 아니면 되돌아가서 다시 해를 찾는 기법 ✔ DFS (깊이 우선 탐색 ) 으로 모든 Node를 검색한뒤 Node의 유망성을 점검하여 유망하지않으면 부모노드로 돌아간 후 다른 자손 노드를 탐색한다 - Node가 Promising한지 ..

문제 ) https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net [ 설명 ] N개의 Queen을 서로 상대를 공격하지 않도록 NxN 체스판에 위치 시키는 문제 → 상대를 공격하지 않으려면 같은 행,열,대각선 상에 위치하면 안된다 예를들어 4 Queen의 경우 , 첫번째 queen을 (1,1)에 둔다면 2번째 queen은 노란색으로 표시한 자리에는 올 수 없다. [ 풀이 ] Backtracking Algorithm으로 풀 수 있는 대표적인 문제다. - Backtrack..