405 [C++] Leetcode - Two sum (Hash Map) 프로그래머스보다 Leetcode 에 더 양질의, 좋은 자료가 많은 것 같아서 옮겨탔습니다. 특히 해외 빅테크 기업들의 코딩 인터뷰 문제들도 있다고하는데, 대부분 유료라... 무료 위주의 탑 100개 알고리즘을 풀어보는 게 목표입니다. 문제 정의 벡터 리스트가 주어졌을 때, 두 원소의 합이 target이 되는 인덱스 값을 반환하는 문제입니다. 완전 탐색으로 쉽게 풀 수도 있지만, 그렇게하면 시간복잡도가 O(n^2)이 되기 때문에 많이 느리더라구요. 본 문제는 구글 코딩 테스트 관련, 구글에서 공식적으로 제공하는 유튜브 영상에도 수록된 문제입니다. 접근 방법 Hash map의 key, value 형태를 활용합니다. Map은 순서가 있는 해시인데, 사실 꼭 순서가 중요하진 않습니다. 공부해볼 겸 Map을 가져.. 2022. 1. 6. [C++] 프로그래머스 - 더 맵게 (힙) 이번 포스팅은 프로그래머스의 힙 문제 중 하나인 더 맵게를 풀어봤습니다. 풀기에 앞서 힙에 대해 간단히 설명하자면 다음과 같습니다. 스택: LIFO (Last in, first out) 구조 큐: FIFO (First in, first out) 구조 힙: 우선순위 큐 (Priority Queue) 구조 스택과 큐는 쉽게 구분이 갑니다. 스택은 바구니가 있으면, 물건을 바구니 안에 차곡차곡 쌓아올린다고 생각하면 됩니다. 물건을 꺼낼때는, 가장 최근에 넣은 물건이 꺼내집니다. 반면 큐는, 같은 바구니긴한데 물건을 꺼낼 때 밑에서 꺼낸다고 이해할 수 있습니다. 즉, 넣은지 가장 오래된, 가장 먼저 넣은 물건을 먼저 빼내는 식인 셈입니다. 큐는 어떤 일처리를 하는데 있어서 순서대로 진행해야할 때 많이 사용하곤 .. 2022. 1. 5. [C++] 프로그래머스 - 주식가격 (스택/큐) 프로그래머스 - 주식가격 (스택/큐) 풀이입니다. 스택/큐에 대한 마지막 문제네요. 마지막 문제가 제일 쉬운 것 같습니다. 문제 설명 접근 방법 이중 for 문을 통해 주식 가격이 떨어지는 지를 관찰합니다. 일단 바로 다음 인덱스에서 값이 떨어지더라도, 1초 간은 유지한다는 점에 유의했습니다. (이중 for 문 안에, 조건문 없이 카운터를 +1함.) 코드 123456789101112131415161718192021#include #include using namespace std; vector solution(vector prices) { vector answer; int cnt=0; for (int i=0; i 2022. 1. 4. [C++] 프로그래머스 - 다리를 지나는 트럭 (스택/큐) 프로그래머스 - 다리를 지나는 트럭 (스택/큐)를 풀어봤습니다. 역시나 다른 풀이에는 정말 간단히 푼 사람들이 많더군요. 저는 저만의 방식대로 일단 풀었다는데 의의를... 문제 설명 접근 방법 해시를 통해 다리를 지나는 트럭이 몇 초 간 운행했는지를 기록. key는 트럭의 index 값, value는 경과 시간 (초). 다리를 지나지 않은 트럭을 나타내는 큐를 2개 생성. 각각 트럭의 중량과, 트럭의 idx를 의미함. while loop를 돌려서 매 초 카운트가 되게 한다. 현재 다리 위에 있는 트럭들을 해시를 통해 찾고, 1초를 더한다. 만약 운행 시간이 다리의 길이와 같다면, 해시값을 수정해서 다 건넜다고 표시한다. 만약 현재 다리 위에 있는 트럭의 무게와, 대기 중인 트럭 큐의 첫번째 트럭 중량의 .. 2022. 1. 3. [C++] 프로그래머스 - 프린터 (스택/큐) 이번 포스팅에서는 프로그래머스 - 프린터(스택/큐)에 대해 다뤄보겠습니다. 문제 정의 접근 방법 다른 사람들의 풀이를 보면 큐를 정말 잘쓰는 것 같습니다.. 지난학기에 OS 과목을 수강하면서, 멀티 스레딩을 지원하는 IPC 통신에서 큐의 필요성에 대해 공감할 수 있었는데요! 이번에도 큐를 이용해서 코드를 짜봤습니다. 현재 프린터의 MAX 값과 인덱스를 찾습니다. 큐의 front 값을 보면서, 최대값과 다를 경우 pop 한 뒤, 다시 큐의 가장 뒤로 push 합니다. 큐는 FIFO 의 특성을 가지기 때문에, pop을 하면 맨 앞의 값이 떨어져나오는 구조입니다. 만약 최대값과 같다면, pop 하고 인덱스를 벡터에 저장합니다. MAX 값도 수정이 필요합니다. 이미 pop이 완료된 맥스 값은 -10으로 설정하여.. 2022. 1. 2. [C++] 프로그래머스 - 기능개발 (스택/큐) 프로그래머스 기능개발 문제입니다. 딱히 스택 큐의 기능을 썼다보기다는.. 단순히 벡터 어레이를 어떻게 처리하는지에 초점을 맞췄습니다. 문제 정의 접근방법 각각의 작업들이 며칠내에 완료가 되는지에 대한 벡터를 구합니다. 첫 작업보다 빨리 완료되는 작업이 뒤에 나오는지를 확인해서, 카운터에 더합니다. 만약 첫 작업보다 늦게 완료되는 작업이 나오면, 카운터를 answer 벡터에 push_back합니다. 코드 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include using namespace std; vector solution(vector progresses, vector speeds) .. 2022. 1. 1. 이전 1 2 3 4 5 ··· 68 다음
