본문 바로가기

Algorithm/자료구조

 (110)
(C++) - 프로그래머스(2018 KAKAO BLIND RECRUITMENT[1차]) : 캐시 programmers.co.kr/learn/courses/30/lessons/17680#qna
(C++) - 백준(BOJ) 5639번 : 이진 검색 트리 www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 재귀를 활용해 이진 검색 트리를 구현 한 뒤 후위순회를 하는 문제였습니다. 풀이방법 배열로는 풀 수 없습니다. 이진 트리의 구조상 자식이 최대 2개이므로 극단적인 경우에서 만약 노드의 수가 10,000개이고 한쪽 자식이 계속 없는 식으로 구성된다면 비어있는 자식을 표현하기 위한 배열공간도 필요합니다. 따라서 2^10,000의 배열 크기를 선언해야하는데 파일 크기 제한으로 seg fault를 맛볼 수..
(C++) - 프로그래머스(연습문제) : 올바른 괄호 programmers.co.kr/learn/courses/30/lessons/12909 코딩테스트 연습 - 올바른 괄호 괄호가 바르게 짝지어졌다는 것은 '(' 문자로 열렸으면 반드시 짝지어서 ')' 문자로 닫혀야 한다는 뜻입니다. 예를 들어 "()()" 또는 "(())()" 는 올바른 괄호입니다. ")()(" 또는 "(()(" 는 올바르지 않은 programmers.co.kr stack을 이용한 문제였습니다. 풀이방법 올바른 괄호가 나오면 '('와 ')' 가 만나 터져 없어지는 생각을 했습니다. 1. '('문자를 stack에 push합니다. 2. stack에 원소가 있고 stack.top()이 '('인데 s[i]가 ')'라면 올바른 괄호이므로 stack을 pop()해줍니다. 3. stack에 원소가 남아..
(C++) - 프로그래머스(고득점 kit - 스택) : 기능개발 programmers.co.kr/learn/courses/30/lessons/42586 코딩테스트 연습 - 기능개발 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 programmers.co.kr stack에 분류되어있지만 그렇게 풀지 않았습니다. 풀이방법 1. 앞 기능을 pivot으로 잡고 이보다 큰 남은 일 수가 있다면 pivot을 해당 인덱스로 옮겨줍니다. 그리고 셌던 기능 개수를 answer에 push 해줍니다. 2. 작거나 같다면 같은날에 배포되므로 cnt를 1씩 증가시켜줍니다. Code #include using namespace std; vector..
(C++) - 백준(BOJ) 17178번 : 줄서기 www.acmicpc.net/problem/17178 17178번: 줄서기 아이즈원의 팬인 시온이는 드디어 티켓팅에 성공하여 콘서트를 갔다. 콘서트장에 일찍 도착한 시온이는 기대하며 입장을 위해 줄을 섰다. 하지만 아이즈원의 인기대로 시온이를 포함한 많은 www.acmicpc.net stack으로 구현한 문제였습니다. 풀이방법 1. 입장 순서 정렬 먼저 입장해야하는 순서를 티켓정보를 정렬함으로써 알아낼 수 있습니다. 정렬시 주의해야할 점은 티켓의 정보 중 앞 알파벳이 같은 티켓이라면 -다음 숫자가 적은 것이 앞으로 와야합니다. 함수로 정렬 기준을 마련하지 않고 그냥 sort하게 된다면 A-102가 A-4보다 뒤로가게 됩니다. string으로는 A-102가 A-4보다 큰 값이기 때문입니다. 따라서 subs..
(C++) - 프로그래머스(고득점 kit - 힙(heap)) : 이중우선순위큐 답 programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr heap을 사용할 때 구현이 너무 복잡하고 자꾸 틀려서 deque로 O(100만log100만)로 풀게 되었습니다.. 풀이방법 1. I일 경우에는 넣을 때마다 deque를 오름차순으로 sort해줍니다. 2. D일 경우 deque가 차 있다면 1일 때는 dq의 마지막을, -1일 때는 dq의 처음을 pop해주면 됩니다. Code #include using namespace std; vector solution(vector operations){ deque dq; vector answer; for(int i = 0; i < operations.size(); i..
(C++) - 프로그래머스(고득점 kit - 스택/큐) : 프린터 답 programmers.co.kr/learn/courses/30/lessons/42587 코딩테스트 연습 - 프린터 일반적인 프린터는 인쇄 요청이 들어온 순서대로 인쇄합니다. 그렇기 때문에 중요한 문서가 나중에 인쇄될 수 있습니다. 이런 문제를 보완하기 위해 중요도가 높은 문서를 먼저 인쇄하는 프린 programmers.co.kr 우선순위 큐와 큐를 사용해 푼 문제였습니다. 풀이방법 1. 우선순위 큐와 큐에 우선순위 정보를 push합니다. 2. 우선순위가 같다면 프린트 하고, 문서번호까지 같으면 정답입니다. Code #include using namespace std; int solution(vector priorities, int location) { int answer = 0, cnt = 0; queu..
(C++) - 프로그래머스(고득점 kit - Hash) : 베스트앨범 답 programmers.co.kr/learn/courses/30/lessons/42579 코딩테스트 연습 - 베스트앨범 스트리밍 사이트에서 장르 별로 가장 많이 재생된 노래를 두 개씩 모아 베스트 앨범을 출시하려 합니다. 노래는 고유 번호로 구분하며, 노래를 수록하는 기준은 다음과 같습니다. 속한 노래가 programmers.co.kr map과 vector를 이용해 풀었던 문제입니다. 풀이방법 1. record맵을 선언해 한 장르에 해당하는 vector {플레이 수,index} 부분을 push해 줍니다. 2. 각 장르별 곡들의 총합 플레이 수를 구해 map변수 played에 저장합니다. 3. played가 각 장르별을 key로 하여 해당 장르의 총 플레이 수를 구했으므로 이번에는 totalPlayed ma..

티스토리툴바