본문 바로가기

Algorithm

 (37)
[이분탐색] 릿코드 Medium 33 'Search in Rotated Sorted Array' (Python) https://leetcode.com/problems/search-in-rotated-sorted-array/ Search in Rotated Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. nums에서 target의 인덱스 값을 찾아라 2. target 값이 없으면 -1 class Solution: def search(self, nums: List[int], target: int) -> int: if target in nums: ..
[이분탐색] 릿코드 Medium 34 'Find First and Last Position of Element in Sorted Array' (Python) https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/ Find First and Last Position of Element in Sorted Array - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 1. 파이썬의 bisect 라이브러리를 활용 2. target이 nums에 있다면 정답을 반환하고 없으면 [-1,-1]을 반환함 from bisect impor..
[동적계획법] 릿코드 Easy 70 'Climbing Stairs' (Python) https://leetcode.com/problems/climbing-stairs/ Climbing Stairs - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 세번째 계단부터는 앞의 두 계단의 경우의 수를 합한 값이 된다. class Solution: def climbStairs(self, n: int) -> int: answer = [] answer.append(1) answer.append(2) for i in range(2,n): answer.appen..
[비트연산] 릿코드 Easy 190 'Reverse Bits' (Python) https://leetcode.com/problems/reverse-bits/ Reverse Bits - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com n은 정수형으로 들어오기 때문에 binary로 바꿔줌. binary로 바꾸면 맨 앞에 0b가 붙으므로 제거해줌 2진수는 32bit의 길이를 유지해야하므로 zfill함수를 이용해 맨 앞에 0을 붙여줌 1을 가진 자리는 2의 지수만큼 곱해줌 class Solution: def reverseBits(self, n: i..
[알고리즘] BFS(넓이 우선 탐색) / DFS(깊이 우선 탐색) 인접 행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 간선 정보를 저장하기 위해 O(V^2)만큼의 메모리 공간 필요 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용 : O(1) V : 노드 0 1 2 #노드 번호 0 0 7 5 #거리 1 7 0 ~ 2 5 ~ 0 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식 간선 정보를 저장하기 위해 O(E)만큼의 메모리 공간 필요 특정한 노드 A에서 다른 특정한 노드 B로 이어진 간선의 비용 : O(V) E : 간선 graph = [[] for _ in range(노드개수)] graph[0].append((노드번호, 노드거리)) graph[0].append((노드번호, 노드거리)) graph[1].append((노드번호, 노드거리..
[알고리즘] 소수의 판별 / 투 포인터 / 구간 합 계산 / 순열과 조합 소수의 판별 [특정 숫자 소수 판별] 제곱근 사용. 시간 복잡도 : O(X^1/2) import math def is_prime_number(x): for i in range(2,int(math.sqrt(x))+1): if x%i==0: return False #소수 아님 return True #소수 is_prime_number(숫자) [특정 범위 소수 판별 (에라토스테네스의 체)] 시간 복잡도 : O(NloglogN). 메모리를 많이 필요하기 때문에 N이 1,000,000 이내여야 함 2부터 N까지의 모든 자연수를 나열한다. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다 남은 수 중에서 i의 배수를 모두 제거한다(i는 제거하지 않는다) 더 이상 반복할 수 없을 때까지 2번과 3번의 과정..
[소수의 판별] 백준 1929번 '소수 구하기' (Python) https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net N과 M의 최댓값이 1,000,000이므로 에라토스테네스의 체 알고리즘으로 풀어야 함 '''입력 예제 3 16 ''' import math n,m = map(int,input().split()) array = [True for i in range(m+1)] array[0],array[1] = 0,0 #0,1은 소수 아님 주의 for i in range(2,int(math.sqrt(m))+1): if array[i]==True: ..
[기타] 백준 1459번 '걷기' (Python) https://www.acmicpc.net/problem/1459 1459번: 걷기 세준이는 학교에서 집으로 가려고 한다. 도시의 크기는 무한대이고, 도시의 세로 도로는 모든 정수 x좌표마다 있고, 가로 도로는 모든 정수 y좌표마다 있다. 세준이는 현재 (0, 0)에 있다. 그리고 ( www.acmicpc.net 한 블록의 2배 값이 대각선보다 작으면 최종 목적지(x+y) * 한 블록 대각선이 더 빠르다면, x와 y의 차가 짝수라면, {대각선*(x, y 중 작은 값)} + {(한 블록, 대각선 중 작은 값)*(x, y 차)} 홀수라면, {대각선*(x,y 중 작은 값)} + {(한 블록, 대각선 중 작은 값)*((x, y 차)-1)+한 블록} '''입력예제 4 2 3 10 4 2 3 5 2 0 12 10 ..
LIST

티스토리툴바