본문 바로가기
728x90

정글 2기/알고리즘26

javascript 알고리즘을 위한 기본 문법 javascript 알고리즘을 위한 기본 문법 달려보자... push( ), pop( ): 배열 뒤에 추가, 삭제 # 배열 뒤 'hi'추가 arr.push('hi') # 배열 뒤 삭제 (중간값 x) arr.pop() shift( ), unshift( ): 배열 앞에 추가, 삭제 # 배열 앞 'hi'추가 arr.unshift('hi') # 배열 앞 삭제 arr.shift() splice(): 배열 원소 자르기, 제거 - 원래 배열에도 영향 arr = ["hot", "dot", "dog", "lot", "log"]; # 배열 중간 값 제거 (splice(i,length) : i번째부터 length 만큼 제거) arr.splice(1,2); console.log(arr); => [ 'hot', 'lot', '.. 2021. 12. 28.
[알고리즘] LRU (Least Recently Used) 알고리즘_ [1차] 캐시 [알고리즘] LRU (Least Recently Used) 알고리즘 페이지 교체 알고리즘 중 가장 대표적인 것이 LRU 알고리즘이다. 이 알고리즘을 파이썬으로 구현해보고 문제도 풀어보자 ! 페이지 교체 알고리즘 Page fault가 발생하여 새로운 페이지를 할당해야 할 때, Allocated page 중 어느 것과 교체할지를 결정하는 알고리즘이다. 각각 서비스에 맞게 사용하여야 한다. LRU(Least Recently Used) Page fault가 발생했을 때, 가장 오랫동안 사용되지 않은 페이지를 제거하는 알고리즘이다. 이 것은 가장 오랫동안 사용되지 않은 페이지는 앞으로도 사용할 확률이 적다는 가정이 존재한다. 마치 locality ! 기본 파이썬 코드 cacheSize = 3 reference =.. 2021. 12. 26.
[알고리즘_카카오] 표 편집_연결 리스트 [알고리즘_카카오] 표 편집_연결 리스트 이 문제는 linked list로 풀 수 있는 문제이다. 처음에는 dictionary로 풀려고 했는데 실패했다. 첫 번째 풀이 - 실패 구현 끝 단계까지 다 한다고 했는데, 결국 dic는 순서가 없어 dict에서 index로 검색하는 것이 불가능해 실패했다.. 뒤 늦게 깨달아 버렸다.. def solution(n, k, cmd): answer = '' dict = {} stack = [] for z in range(n): dict[z] = 1 for x in cmd: print(x, k, dict) if len(x) == 1: if x == "C": # 제거인 경우 if k == len(dict)-1: dict.pop(k) stack.append(k) # 딕셔너리.. 2021. 12. 26.
[알고리즘_카카오] 다익스트라 - 합승 택시 요금 [알고리즘_카카오] 다익스트라 - 합승 택시 요금 다익스트라 최단 경로 알고리즘 동작 과정 1. 출발 노드 설정 2. 최단 거리 테이블을 초기화 3. 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드를 선택 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블 갱신 5. 3, 4번 과정 반복 처음에 이해가 안갔던 포인트가 방문한 노드는 그 노드까지의 최소 비용이 이미 결정된 상태라는 것이었다. '다른 길로 둘러서 왔을 때 더 비용이 적으면 어떡하지?' 라는 생각을 했는데, 다시 생각해보면 새롭게 방문하게 되는 노드는 방문하지 않은 노드 중 가장 비용이 적은 노드라는 사실에서 그 명제가 참이 된다. 즉 다른 길로 돌아가는 것 자체의 첫발(첫 간선)부터 비용이 새롭게 방문하게 되는 노.. 2021. 12. 26.
[알고리즘_카카오 인턴] 거리두기 확인하기_bfs [알고리즘_카카오 인턴] 거리두기 확인하기_bfs 정말 오랜 시간이 걸렸다..... bfs로 풀었는데 내 방식대로 해서 답을 맞히는데 오랜시간이 걸렸다. 처음에 for문을 두 번 돌면서 place[i][j] =="P" 즉 사람일 때를 찾아 bfs를 실행하고나서 for문 둘 다 break하고 나머지 for문을 돌지 않는 방법이 떠오르지 않았다. 결국 이를 check라는 함수로 따로 빼서 해결했다. 그랬더니 반쯤 맞았다. # 첫 시도 def solution(places): answer = [] visited = [[0] * (5) for _ in range(5)] for place in places: # 5번 for i in range(5): for j in range(5): if place[i][j] ==.. 2021. 12. 21.
[백준_1987] 알파벳(bfs, set, bactracking) [백준_1987] 알파벳(bfs, set, bactracking) 고생한 문제다..... 처음에 dfs로 시도했다가 시간 초과가 떴다. 첫 풀이 passed는 지나간 알파벳을 문자열로 저장했고 visited는 전체 행렬에 trace를 알 수 있도록 했었다. 둘 다 시간초과 import sys input = sys.stdin.readline dx = [1,-1,0,0] dy = [0,0,1,-1] def bt(x,y,lengg): global leng leng = max(leng, lengg) for i in range(4): nx, ny = x+dx[i], y+dy[i] if 0 2021. 12. 20.
728x90

티스토리툴바