목록알고리즘 (178)

시작이 반

[백준] 1920번 (python 파이썬)

탐색 문제이다. 파이썬의 in을 써서 풀 수 있지만 이분탐색을 이용하여 문제를 풀었다. index를 기준으로 left right를 나웠고 이분탐색의 탐색 종료 조건은 mid 값이 찾으려는 수랑 같으면 return 을 해주고 찾는 값이 없을때 left가 right보다 커질경우 종료한다. while left
알고리즘/백준 2021. 3. 16. 16:44
[백준] 1629번 (python 파이썬)

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모두 엄청 큰 숫자가 들어오..
알고리즘/백준 2021. 3. 15. 22:31
[백준] 2168번 (python 파이썬)

사실 유클리드 호제법에 관련된 문제이다. 위의 그림을 보고 알 수 있는것은 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 ..
알고리즘/백준 2021. 3. 15. 20:51
[백준] 20003번 (python 파이썬)

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..
알고리즘/백준 2021. 3. 14. 23:57
[프로그래머스] 등굣길(python 파이썬)

최단경로의 개수를 구하는 문제이다.. 문제를 잘못읽어서 최단경로를 구하는 문제인줄 알았다....(몇시간을 날린건지..) 오른쪽과 아래로만 이동할 수 있다. 중학교때 배운 경로의 수 구하는 문제를 알면 풀 수 있는 문제이다. 1, x 좌표를 1로 채운다 (-1이 하나라도 있으면 그 이후에는 -1로 채운다.) x, 1 좌표를 1로 채운다 (-1이 하나라도 있으면 그 이후에는 -1로 채운다.) 해당 좌표로 올 수 있는 경우의 수는 해당좌표의 위, 왼쪽을 더한 값이다. (-1이 있다면 -1이 아닌 값을 넣어준다.) m, n의 좌표가 답이다. 하지만 이렇게 풀면 학교에 도착하지 못하는 경우에는 m, n 좌표에 -1이 들어간다. 예외처리를 하여 -1일경우 0을 반환해준다. def solution(m, n, pudd..
알고리즘/Programmers 2021. 3. 12. 00:19
[프로그래머스] N으로 표현(python 파이썬)

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): ..
알고리즘/Programmers 2021. 3. 11. 21:03
[프로그래머스] 정수 삼각형(python 파이썬)

간단한 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..
알고리즘/Programmers 2021. 3. 11. 20:25
[프로그래머스] 입국심사(python 파이썬)

이분탐색 문젱이다. 최대로 걸리는 시간과 최소로 걸리는 시간을 기준으로 문제를 푼다. 심사관이 주어진 시간동안 모든 사람을 처리할 수 있으면 right값을 줄여주고 심사관이 주어진 시간동안 모든 사람을 처리할 수 없으면 left값을 줄여준다. def solution(n, times): answer = 0 left = 1 right = max(times) * n while left = n: # 종료되기 전에 answer을 바꿔줌 right = mid - 1 answer = mid else: # 종료 조건 바뀌는 부분 left = mid + 1 return answer solution(6, [7, 10])
알고리즘/Programmers 2021. 3. 11. 16:00
이전 Prev 1 ··· 12 13 14 15 16 17 18 ··· 23 Next 다음