나의 공부 기록

사용 언어 파이썬 1. deque의 rotate 메소드 사용 from collections import deque 데큐명.rotate(정수) 음수 : 반시계 양수 : 시계 정수만큼 회전 2. zip 이용 def rotate90(arr) : return list(zip(*arr[::-1])) 3. 2중 for문 def rotated(a): n = len(a)# 행 길이 m = len(a[0])# 열 길이 result = [[0]* n for _ in range(m)] for i in range(n): for j in range(m): result[j][n-i-1] = a[i][j] return result 시계방향 회전 3. 좌우 반전 def reversal(arr) : result = [] for x i..

정렬된 배열에서 특정한 값을 찾는 알고리즘 시간 복잡도는 O(logN) mid=(start+end)/2가 찾고있는 값이 될때까지 실행한다. 찾을 값 k > mid start=mid+1은 범위를 늘리는 것 찾을 값 k < mid end=mid-1은 범위를 줄이는 것 🐝 예제 // 배열에서 이동 int start=0; int end=max_num-min_num; int mid; // 차이값 int answer=200; while(start

첫 번째 방법 def solution(s) : reversed_s=''.join(reversed(s)) if reversed_s == s : return 1 else : return -1 두 번째 방법 def solution(s) : length=len(s) for i in range(len(s)//2) : end=length-1-i if s[i] != s[end] : return -1 return 1

r=4 c=4 matrix=[ [1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15,16] ] # 우 하 좌 상 dx=[0, 1, 0, -1] dy=[1, 0, -1, 0] x=0 y=0 pos=0 visited=[[0]*c for _ in range(r)] visited[0][0]=1 cnt=1 print(1, end=" ") while cnt < r*c : nx = x + dx[pos] ny = y + dy[pos] if 0

# 백준 '2661. 좋은수열' 문제 중에서 for i in range(1, (idx//2)+1) : if s[-i:] == s[-2*i : -i] : return -1 뒤에서부터 길이가 i인 두 문자열을 비교 # 백준 '2661. 좋은수열' 문제 중에서 def check(s) : for i in range(1, (len(s)//2)+1) : leng=i# 길이 start=0 start2=start+i for j in range(len(s)-(leng*2)+1) :# 시작 인덱스 증가 if s[start+j : start+j+leng] == s[start2+j : start2+j+leng] : return False return True 1부터 문자열의 절반까지 반복하며 두 문자열을 비교 start와 s..

Sliding window algorithm은 하나의 포인터, 윈도우 사이즈 변수가 필요하다. 윈도우 사이즈는 리스트 안에서 범위다. 아래는 길이가 5(n)인 리스트에서 길이가 3(k)인 연속된 최대 부분합을 구하는 코드다. 윈도우 사이즈(k)가 3을 채운 이후로 start번째 값을 빼주고 새로운 i번째 값을 더한다. arr=[5, 2, -1, 0, 3] n=5 k=3# 윈도우 사이즈 start=0 ans=0 window_sum=0 for i in range(n) : window_sum+=arr[i] if i >= k-1 : ans=max(window_sum, ans) window_sum-=arr[start] start+=1 print(ans) Two pointer algorithm은 두 포인터 star..

비트의 위치가 1이면 켜져 있는 것, 0이면 꺼져 있는 것 🍟 비트마스크를 사용하면 얻는 장점 더 빠른 수행 시간 : O(1) 더 간결한 코드 더 작은 메모리 사용량 연관 배열을 배열로 대체 : map를 int[]로 대체 🦘 비트마스크를 이용한 집합의 구현 N비트 정수 변수는 0부터 N-1까지의 정수 원소를 가질 수 있는 집합이 된다. 원소 i가 집합에 속해 있다면 2^i 비트가 1이다. 상수 0은 공집합 int num=(1

LRU 알고리즘은 정해진 size만큼 cache가 가득 차고, cache에 없는 페이지가 들어왔을 때 가장 오래된 페이지를 제거하는 알고리즘 운영체제에서 어떤 페이지로 교체할지 결정하는 페이징 기법 중 하나다. Page-hit : 현재 페이지(삽입하려는 페이지)가 메모리에 이미 있을 때 왼쪽에 있을수록 최근에 사용한 페이지다. 다음 두가지를 고려해야한다. 1. 삽입하려는 페이지가 이미 cache에 있다. 이 경우 기존에 있던 페이지를 삭제하고 최신 페이지로 만들어준다. 기존 페이지를 삭제한다. 가장 왼쪽에 신규 페이지를 추가한다. 2. 삽입하려는 페이지가 cache에 없다. cache에 페이지를 추가한다. 정해진 사이즈만큼 캐시가 가득 찼을 경우에는 캐시에서 가장 마지막 페이지를 제거 후 신규 페이지를 ..

n개의 원소 중 m개를 선택하는 모든 조합을 찾는 알고리즘을 구현 def make_combination(n, combinations, will_pick) : if will_pick == 0 : print(combinations) return start = combinations[-1] + 1 if combinations else 0 for i in range(start, n) : combinations.append(i) make_combination(n, combinations, will_pick - 1) combinations.pop() n = 4, will_pick=2라면(4개 중에서 2개를 고르기) 결과는 다음과 같다. [0, 1], [0, 2], [0, 3], [1, 2], [1, 3], [2, ..

유니온 파인드 알고리즘은 상호 배타적 집합(Disjoint-set)이라고도 한다. 아래 세 가지 연산으로 이루어짐 1. 초기화 parent=[i for i in range(5)] 1차원 배열을 사용해서 n개의 원소가 서로 다른 집합에 속하도록 한다. i의 부모 노드는 parent[i] 2. Find def find(x) : if x == parent[x] : return x else : return find[parent[x]] 노드 x가 어느 집합에 속하는지 찾는 연산(=x의 루트 찾기) x==parent[x]면 x가 부모 노드 그렇지 않다면 재귀 호출을 사용해 루트를 찾아 반환 아래는 find 함수를 최적화한 코드 def find(a) : if a == parent[a] : return a parent..