yeony's story

1. 특수 문자 출력하기 He says "It's really good life!"를 출력하려면 \를 이용해야 합니다. 출력하고 하는 문자 앞에 \를 붙여주면 됩니다. print("He says \"It\'s really good life!\""); 2. 두 줄 출력하기 (1) \n 이용하기 print("Hello\nWorld!") (2) print문 이용하기 print("Hello") print("World") 3. 공백 또는 구분자 사용하여 출력하기 (1) 공백을 사이에 두고 출력하기 : 쉼표 이용 print(3,5) (2) 구분자 사용하기 : sep 이용 print(3,5,sep=":") 4. 출력 형식 (1) 변수 포맷 (%d, %s, ..)과 %를 사용한다. %s : 문자열 %c : 문자 %d ..

https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net 시간 복잡도를 생각하지 못하고 bfs로 탐색을 진행했다가 메모리초과 뜸.. 아래 코드의 시간복잡도는 O(N^2) 1초에 N의 범위가 2000 이하여야 쓸 수 있는 코드! 하지만 주어진 데이터 개수는 10만 시간 복잡도를 계산하면 10만 *. 10만 =. 100만 결국 O(N)으로 작성을 해야 함! 시간 제한은 2초 # import sys # from collection..

https://www.acmicpc.net/problem/9095 dp[1] = 1가지 dp[2] = 2 , 1+1 = 2가지 dp[3] = 3, 2+1, 1+2, 1+1+1 = 4가지 dp[4] = 3+1, 2+1+1, 1+2+1, 2+2, 1+3, 1+1+2, 1+1+1+1 = 7가지 (1+2+4) dp[5] = 13가지 (2+4+7) t=int(input()) dp=[0 for _ in range(11)] dp[1]=1 dp[2]=2 dp[3]=4 for _ in range(t): n=int(input()) if n < 4: print(dp[n]) else: for i in range(4,n+1): dp[i]=dp[i-1]+dp[i-2]+dp[i-3] print(dp[i])

https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net > dp i%2로 나눠지고 i%3으로 나눠지면 min함수를 이용해서 어떤 경우를 선택해야 최솟값으로 나오는 지 확인해야한다. 위에서 구한 값과 -1을 뺀 값중에서도 어떤 경우를 선택해야 최솟값으로 나오는 지 확인해야 한다. import sys n = int(sys.stdin.readline()) dp = [0 for _ in range(n + 1)] dp[0],..

> dp https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 총 4개 이하의 자연수 제곱수들의 합으로 모든 자연수를 정의내릴 수 있다. N = a^2 + b^2 + c^2 + d^2 dp를 푸는 문제는 항상 규칙이 존재한다. n이 6일때를 생각해보자. i가 1일땐 1이라고 초기화 진행 i=2일때, 2는 1의 제곱수들의 합으로 정의할 수 있음. 2 = 1^2 + 1^2 2 - 1^2 = 1이다. 따라서 dp[1]과..

> 유클리드 호제법 최대 공약수를 구할 땐 유클리드 호제법을 이용해야 한다. * 유클리드 알고리즘 * : a, b의 최대 공약수는 (a-b),b의 최대공약수와 같다. 1. 임의의 두 자연수 a,b가 주어졌다. 2. 두 자연수 중에 큰 값을 a라고 가정한다. 3. 큰 수 a 자리에는 a-b와 b값 중에 큰 값을 넣는다. 작은 수 b 자리에는 a-b와 b값 중에 작은 값을 넣는다. 그리고 재귀함수를 호출한다. import sys sys.setrecursionlimit(100000) def gcd(a, b): if b == 0: return a return gcd(max(a - b, b), min(a - b, b)) c1, p1 = map(int, input().split()) c2, p2 = map(int,..

> 다이나믹 > 조합 일단 조합으로 먼저 푼 문제 해당 문제는 서로 다리가 교차되는 일은 허용되지 않으므로 순열(중복허용)대신 조합(중복불허)을 사용함. 조합은 팩토리얼 함수를 이용해서 구할 수도 있고, permutation 함수를 이용할 수도 있음. 해당 문제에서는 팩토리얼을 재귀함수로 구현 ex) 6C3 = 6 * 5 * 4 // 3! 8C3 = 8 * 7 * 6 // (3!) -> ( factorial(8) // factorial(8-3) ) // factorial(3) t=int(input()) def factorial(n): if n==0 or n==1: return 1 return factorial(n-1)*n for _ in range(t): w,e=map(int,input().split()..

https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 이분 탐색으로 풀려다 실패하고 결국 다이나믹 프로그래밍으로 푼 문제다 ^0^ 사실 이것도 구글링...해서 겨우 이해한 문제ㅜㅜㅜ power=max(a,b) 이 부분이 이해가 되지 않아서 애를 먹었다. a에 들어가는 건 j번째 -> i번째로 이동할 때 쓰여지는 힘 b에 들어갈 건 j번째까지 탐색을 진행했을 때 구해진 최소의 힘이다. 앞에서..

> 이분 탐색 https://www.acmicpc.net/problem/11663 11663번: 선분 위의 점 첫째 줄에 점의 개수 N과 선분의 개수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 둘째 줄에는 점의 좌표가 주어진다. 두 점이 같은 좌표를 가지는 경우는 없다. 셋째 줄부터 M개의 줄에는 선분의 시작점과 www.acmicpc.net 이분 탐색 문제를 풀 때마다 헷갈렸던 거! left, right 값에 인덱스를 넣어야할 때도 있고, 0,max(array)처럼 0과 배열의 최댓값을 넣어줘야 풀리는 문제도 있었다. 근데 언제 인덱스를 넣어야하는지, 최댓값을 넣어줘야하는지 기준이 잡히지 않아서 헤맸던 문제다. 1. 문제에서 값을 구하라고 하는 문제 > 배열의 최댓값을 right에 넣어줌. l..

> 이분탐색 https://www.acmicpc.net/problem/1654 k, n = map(int, input().split()) array = [int(input()) for _ in range(k)] left = 1 right = max(array) result=0 while left [2792] 보석상자 in python > 이분탐색 평소에는 이분탐색을 풀 때 cnt==n일때, cnt cnt>n일때 각각 조건을 나눠 계산을 진행해줬다. 그러나 이번 문제처럼 최솟값이나 혹은 최댓값을 구할 땐 위 방식보다는 아래 코드와 같이 eboong.tistory.com