전체 글243
[프로그래머스💯] 코딩테스트 연습 > 스택/큐 > 탐욕법
풀이) 이 문제는 '()' 가 나왔을 때 레이저를 쏜다. 레이저를 쏘는 시점에 쌓여있던 막대기 수 만큼 부분 막대기가 생성될 것이고, '()' 가 아닌 '))' (이전 문자가 '(' 인 경우) 이라면 막대기 층이 하나 낮아지므로 막대기가 1개 의 부분막대기가 생성된다. 요약하자면 ')' 가 나왔을 때 case A : 쌓여있던 막대기 수-1 만큼 블럭 result를 늘려준다. - 막대기 수 - 1 인 이유는 '()' 에서 나오는 '(' 도 쌓인 막대기로 계산한다고 가정 때문. case B : result 를 1만큼만 늘려주고 막대기를 하나 줄인다. def solution(arrangement): stk = [] count = 0 # 스택에 들어가있는 ( 수 recent = 0 # 이전 문자가 '(' = 0..
[알고리즘] Approximation Algorithm 이란 / NP 문제 알고리즘
Approximation Algorithm 이란 세상에는 무수한 문제들이 있고, 그 만큼 어려운 문제도 무수히 많다. (ex. NP문제) 알고리즘적으로 보통 어려운 문제는 polynomial 시간 안에 풀 수 없는 문제들을 말한다. 이들을 프로그래밍 적으로 사용하기에는 과부하가 너무 크다. 따라서, 완벽한 답을 구하는 것에는 살짝 내려놓고, 조금은 틀릴 수 있는 가능성이 있더라 하더라도 근접한 답을 구해낼 수 있는 빠른 알고리즘(polynomial 시간안에 해결이 가능한)을 택하는 것이다. 예를들자면, 우리가 인터넷으로 성능대비 가격이 좋은 컴퓨터를 사려고한다. 가장 좋은 방법은 온라인 상에 있는 모든 웹 사이트에 판매중인 컴퓨터 제품들을 하나하나 다 비교하고, 최고 가성비의 제품을 사는 것이다. 하지만..
[Python] 파이썬 Heapq 모듈 사용하기 / 힙(Heap) 구조
Heap 이란Heap 이란 자료구조 형태 중 하나로서 우선순위 큐를 위해 만들어진 구조이다. (자세한 Heap에 대해 : https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html 참고) 코딩 테스트 문제 중 최솟값 , 혹은 최댓값을 계속해서 호출해야 하는 상황인 경우 Heap 구조를 이용하여 구현하면 시간측면에서 굉장히 효율적인 구현이 가능하다. import heapqheapq 모듈을 이용하여 힙 자료구조를 사용할 수 있다. heapq 는 내장 모듈이므로 따로 설치가 필요하지 않는다. 기본적으로 Min-priority-queue 구조를 가지고 있다.import heapq 기존 배열을 Heap 구조로 - heapify() testheap = [1,..
[컴퓨터구조] Locality 란 / Locality 종류
Locality 란Locality를 한국어로 직역하면 '지역성' 이라는 뜻이다. 프로그램적으로 생각해보자. 우리의 프로그램은 항상 메모리의 특정 주소를 찾아가서 데이터를 읽어오고 특정 주소로 찾아가서 데이터를 쓰는 행위들이 기본이다. 여기서 '특정주소' 가 어떻게 될지, 실행해보기 전의 우리는 아직 잘 모른다. 하지만! 이 Loaclity 라는 특성을 이용하면 이를 예상하고 접근 시간을 줄일 수 있다는 것이다! (또한, 이 접근 시간은 프로세서의 성능에 직접적인 연관이 있다.) Temporal Locality 와 Spartial LocalityTemporal Loaclity : 최근에 접근했던 주소값을 다시 접근하는 경향 - 한번 사용한 주소의 메모리 영역은 자주 접하게 된다. - 예시) Loop문 안의..
[MIPS] Pipeline Hazard 종류 / Structure / Data / Control
Hazard 란pipeline 형식에서 어떠한 문제가 발생해서 다음 사이클의 다음 명령을 실행할 수 없는 경우를 뜻한다. Structure Hazard 물리적인 원인에 의하여 발생하는 hazard 로, 메모리를 1개만 쓴다던지 포트가 하나라던지 하는 이유로 발생한다. 1개의 메모리로 읽고 쓰는 게 동시에 진행되려할 때 발생한다. 해결방법 : 1. 메모리 수를 늘린다. (물리적으로 하드웨어를 추가해준다.) 2. 해당 기능 사용 가능한 시점까지 지연시킨다. Data Hazard Instruction 의 식 실행을 위해 필요한 데이터가 아직 만들어지지 않은 경우!해결방법 : 1. 계산되자마자 MEM 과 WB를 거지 않고 바로 결과값을 넘겨준다. (Forwarding or Bypassing)2. 소프트웨어적으로..
[DB] 데이터베이스 Evaluation / PipeLining 과 Materialization
쿼리 실행의 단계 1. Parsing and Translation 2. Optimization 3. Evaluation Evaluation - 엔진이 1,2 단계를 거친 쿼리를 보고 어떻게 실행할건지 실행 계획을 세우고 행하는 것. 대표적으로 Pipelining 방식과 Materialization 방식이 있다. Pipelining 한 연산의 실행이 끝나서 결과 값을 내기 전에, 다른 연산도 실행하는 방법 ( 동시에 계산 이라 생각해도 됨) - Materialization 보다 저렴하다. (따로 릴레이션을 메모리에 저장할 필요가 없음) - 정렬이나 해쉬 조인에는 적용 불가. - demand driven 과 producer driven 으로 나뉜다. demand driven(lazy driven) : 현재 ..
[프로그래머스💯] 코딩테스트 연습 > 탐욕법(Greedy) > 체육복
해답) def solution(n, lost, reserve): # 그리디한 알고리즘 이므로 소트를 해줘야한다. reserve.sort() # 여벌이 있는 친구가 도난당한 경우 for i in reserve: if i in lost: lost.remove(i) reserve[reserve.index(i)] = -5 # 체육복을 빌려주는 경우 for i in reserve: if i-1 in lost: lost.remove(i-1) elif i+1 in lost: lost.remove(i+1) return n-len(lost) * 알고리즘 순서 여벌이 있는 친구들을 기준으로 (정렬이 되어있음을 가정) 빌려줄수있는 앞번호 부터 쭈욱 빌려준다. 1. 자신이 잃어버린경우 2. 자신의 앞번호가 잃어버린 경우 3...
[프로그래머스💯] 코딩테스트 연습 > 탐욕법(Greedy) > 조이스틱
해답) def solution(st): res = 0 A_Count =0 A_Max = 0 # 가장 긴 A묶음의 A 수 A_StartIndex = 0 A_EndIndex = 0 vertical_count = 0 start = True for i,v in enumerate(st): # 연속해서 나온 A 횟수 검사 if v == 'A' and start == False : A_Count += 1 if A_Count > A_Max: A_Max = A_Count A_EndIndex = i else: A_Count = 0 # 알파벳이 N보다 크면 위로넘기는게 빠르다 if ord(v) > ord('N'): count = ord('Z')-ord(v)+1 else: count = ord(v) - ord('A') res..