일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
- sql 기술면접
- 웹어플리케이션 서버
- 백준 19238
- java
- Spring
- 백준 16719
- springboot
- with recursive
- Spring Boot
- 백준 파이썬
- Coroutine
- spring oauth
- 백준 16235
- 프로그래머스
- Kotlin
- MySQL
- 백준 15685
- JVM
- re.split
- spring cloud
- spring security
- JPA
- java 기술면접
- MSA
- 백준
- 프로래머스
- 백준 17779
- 파이썬
- 백준 17626
- 백준 16236
- Today
- Total
목록파이썬 (92)
시작이 반
이진탐색 풀이 첫 풀이 방법은 이진탐색을 한뒤 찾으려는 숫자가 있으면 count + 1을 해주고 해당 숫자를 list에서 remove한뒤 다시 그 숫자를 이진탐색하는 방식으로 하였다. 당연하게 시간초과가 나왔다. 두번째 풀이 방법은 찾고자 하는 숫자의 index를 이진탐색으로 찾고 그 index에서 양쪽으로 찾으려는 숫자가 있는지 반복문으로 확인하는 방식으로 하였다. 이또한 시간초과가 나왔다 list에 모든 숫자가 찾고자 하는 숫자이면 반복문이 엄청나게 돌아간다. 최종 풀이방법은 mid에 찾고자 하는 숫자가 나와도 이진탐색을 끝내지 않고 계속 나눠주면서 찾고자 하는 숫자의 양쪽 마지막 index를 반환한다. 2번의 이진탐색을 한다 n = int(input()) cards = list(map(int, in..
탐색 문제이다. 파이썬의 in을 써서 풀 수 있지만 이분탐색을 이용하여 문제를 풀었다. index를 기준으로 left right를 나웠고 이분탐색의 탐색 종료 조건은 mid 값이 찾으려는 수랑 같으면 return 을 해주고 찾는 값이 없을때 left가 right보다 커질경우 종료한다. while left
A를 B번 곱한 수의 C로 나눈 나머지를 구하는 것이다. A, B, C는 모두 2,147,483,647 이하의 자연수다. 즉 반복문으로는 절대 풀수없다. 때문에 분할 정복을 선택하였다. 첫 풀이 a, b, c = map(int, input().split(' ')) def dnc(length): if length == 1: return a if length % 2 == 0: left = dnc(length // 2) return left * left else: left = dnc(length // 2) return left * left * a print(dnc(b)) 이렇게 푸니까 시간초과가 나왔다.. 검색해보니 오버플로우도 시간초과가 나온다고 한다.???음? 생각해보니 a, b모두 엄청 큰 숫자가 들어오..
사실 유클리드 호제법에 관련된 문제이다. 위의 그림을 보고 알 수 있는것은 1. 대각선이 꼭지점을 지나가지 않는 직사각형은 x + y -1 대각선이 꼭지점을 지나가는 직사각형은 x + y -1 - (점의 개수) 이다. 2. 점의 개수는 어떻게 구하냐 x, y의 최대공약수 - 1이다 즉 점이 없는 직사각형들은 (x, y의 최대공약수 - 1) 을하면 0이 나오기 때문에 이도 성립한다 1, 2를 종합해보면 x + y - gcd(x, y) 라는 식을 구할 수 있다. x, y = map(int, input().split(' ')) def gcd(a, b): if b > a: a, b = b, a while True: if b == 0: break a, b = b, a % b return a print(x + y ..
NTS 코테를 봤다.. 1번문제가 유클리드 호제법을 활용한 문제였다고한다..(생각도 못함..) 생각나서 gcd관련문제를 풀어봤다...ㅜ 분모들의 lcm과 분자들의 gcd를 구하는 문제이다. gcd를 구하는 방법은 유클리드 호제법을 이용하여 구할 수 있다. def gcd(a, b): if b > a: a, b = b, a while True: if b == 0: break a, b = b, a % b return a 이를 통해서 lcm또한 구할 수 있다. def lcm(a, b): return a * b // gcd(a, b) 전체 코드 기약분수는 fractions 함수를 통해서 쉽게 구할 수 있다. import fractions n = int(input()) ups = list() downs = list..
최단경로의 개수를 구하는 문제이다.. 문제를 잘못읽어서 최단경로를 구하는 문제인줄 알았다....(몇시간을 날린건지..) 오른쪽과 아래로만 이동할 수 있다. 중학교때 배운 경로의 수 구하는 문제를 알면 풀 수 있는 문제이다. 1, x 좌표를 1로 채운다 (-1이 하나라도 있으면 그 이후에는 -1로 채운다.) x, 1 좌표를 1로 채운다 (-1이 하나라도 있으면 그 이후에는 -1로 채운다.) 해당 좌표로 올 수 있는 경우의 수는 해당좌표의 위, 왼쪽을 더한 값이다. (-1이 있다면 -1이 아닌 값을 넣어준다.) m, n의 좌표가 답이다. 하지만 이렇게 풀면 학교에 도착하지 못하는 경우에는 m, n 좌표에 -1이 들어간다. 예외처리를 하여 -1일경우 0을 반환해준다. def solution(m, n, pudd..
N = 1 일때 나타낼 수 있는 값 5 N = 2 일때 나타낼 수 있는 값 55, 5+5, 5-5, 5*5, 5/5 즉 N = 1의 집합을 조합해서 만든 경우이다. N = 3 일때 555, 5+(5+5), 5-(5+5), (5+5)-5, (5+5)*5, (5+5)/5, 5/(5+5), 5+(5-5), 5-(5-5), (5-5)-5, (5-5)*5, (5-5)/5, 5/(5-5), .... 이런식이다 즉 N = 1, N = 2의 조합이다. N = 2, N =1( N = 1, N = 2와 중복임으로 생략) N = 4 일때 N = 1, N = 3 N = 2, N = 2 N = 3, N = 1 ( N = 1, N = 3과 중복임으로 생략) 즉, 절반까지 구하면된다. def solution(N, number): ..
간단한 DP문제이다. 삼각형의 꼭대기에서 바닥까지 이어지는 경로중 합이 가장 큰값을 구한다. n번째 줄의 i번째 숫자는 n-1번째 줄의 i-1, i 번째 숫자중 큰값과 해당 값을 더해서 구한다. def solution(triangle): answer = 0 l = len(triangle) dp = [[0] * l for _ in range(l)] dp[0][0] = triangle[0][0] for i in range(1, l): for j in range(0, i+1): if j == 0: dp[i][j] = dp[i-1][j] + triangle[i][j] elif j == i+1: dp[i][j] = dp[i-1][j] + triangle[i][j] else: dp[i][j] = max(dp[i-1..