알고리즘

[ Javascript ] 삽입정렬

개념 전체 배열을 돌면서 현재 인덱스를 진행시키는데, 이때 값은 key라고 한다면, key가 현재인덱스값보다 작을때까지, 현재 인덱스를 배열의 왼쪽끝까지 옮겨가며 값을 비교한 뒤에, 현재인덱스값을 현재인덱스-1의 값으로 바꾸고 인덱스를 줄인다. 이 과정이 끝나면, key를 현재 인덱스에 넣어준다. 구현 const insertSort = (inputArray) => { for (let index = 1; index 0 && inputArray[currentIndex - 1] > key) { inputArray[cu..

[ Javascript ] 알고리즘 테스트를 위한 jest 환경 세팅하기

javascript로 여러 알고리즘을 구현하고 jest를 통해서 결과를 확인해 볼 것이다. 프로젝트 폴더를 구성해주자. npm init npm init -y jest 설치 및 세팅 npm i jest npm test를 했을때, jest가 실행되게 하고싶으니깐 package.json에 이렇게 작성해줬다. { ... scripts:{ "test" : "jest" }, ... } 이러고 jest를 실행시키면... 실행이 안될꺼다. jest는 바벨이 필요하다. 기본적으로 es5 구문으로 해석하기 때문이라고 한다. https://gatsbybosungblogmain.gatsbyjs.io/tdd3/ Jest에서 왜 babel이 필요한가? Jest에서 왜 babel이 필요한가? gatsbybosungblogmain...

1715 백준 파이썬

힙 그자체인 문제 import heapq n=int(input()) 결과=0 힙=[] for _ in range(n): heapq.heappush(힙, int(input())) while len(힙)!=1: 임시=heapq.heappop(힙) if 힙: 임시=임시+heapq.heappop(힙) 결과+=임시 heapq.heappush(힙,임시) print(결과)

23254 백준 파이썬

괜히 힙 두개쓸려다가 개같이 멸망했던 문제 남은 숫자를 새 단위로 힙에 넣는걸 생각하지 못해서 굉장히 고민했다. 이번엔 특별히 한글 코드로 작성했다. 사랑해요 연예가중계 import heapq n,m=map(int,input().split()) # 24*n시간 후 시작 time=24*n # m과목 a=list(map(int,input().split())) b=list(map(int,input().split())) 결과=0 힙=[] for x in range(m): heapq.heappush(힙, [-b[x],a[x]]) while 힙: 힙에서뽑은거=heapq.heappop(힙) 단위,점수=-힙에서뽑은거[0],힙에서뽑은거[1] while 단위+점수0: 점수+=단위 time-=1 else: break if ..

3078 백준 파이썬

윈도우를 덱으로 구성해주었다. 윈도우 크기가 k+1미만이면 윈도우에 append하고, 이름길이 배열의 갯수를 더해준다. 윈도우 크기가 k+1(k등 이상 차이이므로)나게 되면 popleft하여, 해당 값의 이름 길이 배열의 갯수에서 빼준다. 마지막에는 window에는 k+1이하의 길이를 가진 값들이 남게 되는데 이 값들을 동일하게 큐느낌으로 처리해주었다. import sys input=sys.stdin.readline from collections import deque n,k=map(int,input().split()) count=[0 for x in range(21)] name=[] window=deque() ans=0 for x in range(n): name.append([x+1,len(input(..

17503 백준 파이썬

맥주파뤼~~ heap은 알콜이 낮은 순서로,. answer에는 prefer가 낮은대로 각각 두개의 heap을 사용했다. 입력된 값을 바로 heap에 넣어서 알콜도수가 낮은순대로 저장하고, 이들의 수가 n에 도달했을때, 만족도를 넘기지 못하면 answer의 값 중 가장 만족도가 낮은 것을 뺀다. 이때 만약 알콜이 가장 높은 것이면 두번째로 알콜값이 높은 값을 가장 높은 값으로 바꿔준다. 이걸 heap이 존재할때까지 반복하고, 없으면 -1를 출력하게 했다. 문제가 있었던 점은 second_alchol을 사용하지 않고, answer에서 반복문을 찾아서 maxalchol을 찾으려고 했더니 시간초과가 났다는 점이다. 시간초과가 난 코드 import heapq n,m,k=map(int,input().split())..

13335 백준 파이썬

처음에는 시간을 계산해서 구해주려고 했다. 실패한 코드 from collections import deque n,w,l=map(int,input().split()) truck=list(map(int,input().split())) d=deque() s=0 time=0 for x in truck: if x+sl: y=d.popleft() s-=y if d: time+=1 s+=x d.append(x) if d: time+=w while d: d.popleft() time+=1 print(time) 이 경우 5 2 2 1 1 1 1 1과 같은 경우를 생각하지 못했다. 정답은 무지성 덱 시뮬레이션 이다. 덱으로 다리를 만들어서 직접 트럭을 이동시켜주었다. from collections import deque ..

2841 백준 파이썬

간단해 보였지만 생각보다 생각할 것이 많았던 문제 무한 if else문으로 해결완료 import sys input=sys.stdin.readline n,p=map(int,input().split()) stack=[[] for _ in range(p+1)] cnt=0 for _ in range(n): a,b=map(int,input().split()) if stack[a]: if stack[a][-1]>b: x=0 while stack[a] and stack[a][-1]>=b: x=stack[a].pop() cnt+=1 if x==b: cnt-=1 stack[a].append(b) else: cnt+=1 stack[a].append(b) elif stack[a][-1]==b: continue else: s..