본문 바로가기

Coding test

 (123)
[백준/1309/파이썬] 동물원 - DP 소스코드 n = int(input()) dp =[1,3,7] for i in range (2,100001): dp.append((dp[i]*2 + dp[i-1])%9901) print(dp[n]%9901) 알고리즘 점화식 (dp[i]*2 + dp[i-1])만 찾으면 쉽게 풀리는 문제였다. 다만 처음에 메모리초과 에러가 났는데 찾아보니 계산할때마다 9901의 나머지를 추가해줘야 했다. 나머지로 계산을 해도 전체 결과에서 나머지 계산을 한게 같게 되는걸 알게 되었다.
[백준/14889/파이썬] 스타트와 링크 소스코드 from itertools import combinations N = int(input()) startlink = [list(map(int, input().split())) for _ in range(N)] answer = int(1e9) num = [i for i in range(N)] team = list(combinations(num,N//2)) for start_player in team: start_total = 0 link_total = 0 link_player = list(set(num)-set(start_player)) for i,j in list(combinations(start_player,2)): start_total += startlink[i][j] start_total +..
[백준/11726/파이썬] 2×n 타일링 소스코드 n = int(input()) dp = [0]*(1001) dp[1] = 1 dp[2] = 2 for i in range (3,1001): dp[i] = dp[i-1]+dp[i-2] print(dp[n]%10007) 알고리즘 dp라는걸 알고 풀면 정말 쉬운 문제입니다. 2 - 2 3 - 3 4 - 5 5 - 8 6 - 13 7 - 21 8 - 34 9 - 55 이렇게 n번째 숫자를 구할때는 (n-1번째) + (n-2번째)를 해주면 됩니다. 이제 백준 실버 난이도는 손쉽게 풀 수 있을 것 같다는 자신감을 얻었습니다.
[백준/1182/파이썬] 부분수열의 합 소스코드 from itertools import combinations N,S = map(int,input().split()) seq = list(map(int,input().split())) result = [] cnt = 0 for i in range(len(seq)+1): result = result+list(combinations(seq,i)) del result[0] for i in result: if (sum(i)) == S: cnt += 1 print(cnt) 알고리즘 파이썬의 itertools에 있는 combinations를 이용하여 부분 순열을 구한다. 공집합은 제거한다 합이 S인 개수를 구한다. 기본적인 문제라 시시했다.
[백준/6064/파이썬] 카잉 달력 소스코드 T = int(input()) def sol(m,n,x,y): while x
[백준/3085/파이썬] 사탕게임 - 브루트포스 소스코드 n = int(input()) board = [] ans =0 for _ in range(n): candy = list(map(str,input())) board.append((candy)) def count_candy(board): #개수세는 함수 N = len(board) max_candy = 1 for i in range(N): cnt = 1 for j in range(1,N): if board[i][j] == board[i][j-1]: cnt += 1 else : cnt = 1 if max_candy
[백준/1476/파이썬] 날짜계산 - 브루트포스 소스코드 E,S,M = map(int,input().split()) (ear,sun,moon) = (1,1,1) year = 1 while (ear,sun,moon) != (E,S,M): ear = ear + 1 sun = sun + 1 moon = moon +1 if ear > 15: ear = ear - 15 if sun > 28: sun = sun - 28 if moon > 19: moon = moon - 19 year += 1 print(year) 알고리즘 (1,1,1)에서 하나씩 증가하고 각각의 숫자가 최대치를 넘어가면 빼준다. 종료 조건은 입력값과 같아질때입니다
[백준/1339/파이썬] 단어수학 - 그리디 소스코드 n = int(input()) digit = [0]*26 for _ in range(n): num = list(input().rstrip()) for i in range(len(num)): digit[ord(num[i])-65] += 10 ** (len(num)-i-1) digit.sort(reverse=True) ans = 0 dig = 9 for i in digit: if not i: break ans += i*dig dig -= 1 print(ans) 알고리즘 이 문제는 그리디를 이용하여 풀 수 있는 문제이다. 찾아보니 딕셔너리를 이용한 풀이가 많았는데 입력이 대문자 알파벳이란 특성을 가지고 푸는 풀이가 있어서 힌트를 얻어 풀 수 있었다. ord('A')는 A의 아스키 코드 65를 나타내어..

티스토리툴바