Problem Solving/자료구조 및 구현 썸네일형 리스트형 BOJ 9322- 철벽 보안 알고리즘 문제 링크(Link)https://www.acmicpc.net/problem/9322 문제 해결(Solution) 1. 제 1 공개키와 제 2 공개키의 순서를 저장하고 처리하는 자료구조에 관한 문제. 2. ① 문자열을 인덱스로 저장하면서 동시에 자동 정렬이 되지 않는 자료구조인 'unordered_map'을 사용.② 제 1 공개키의 순서를 저장하는 배열(order)을 사용.③ 제 2 공개키가 주어지면, ②에서 사용한 배열의 값을 인덱스로 사용해서 답을 저장하는 배열(answer)을 사용. ex) 제 1 공개키 : "I AM HAPPY" 제 2 공개키 : "AM HAPPY I" 암호문 : "LOVES HER HE" - unordered_map(first==string, second==order) : { {.. 더보기 BOJ 2174 - 로봇 시뮬레이션 문제 링크(Link)https://www.acmicpc.net/problem/2174 문제 해결(Solution) 1. 기본적인 구현 가능 여부를 물어보는 문제. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. iteration 과정에서 갱신시켜주는 코드를 잊으면 안된다. 2. IT 기업 입사 시험에서(코딩테스트를 요구하는 기업) 기본적으로 요구하는 문제 수준이다. 반드시 풀어봐야한다. 참고(Reference) - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 6549 - 히스토그램에서 가장 큰 직사각형 문제 링크(Link)https://www.acmicpc.net/problem/6549 문제 해결 (Solution) 1. 여러가지 풀이 방법이 있지만, 분할 정복(divide & conquer)과 구간 트리(segment tree)를 이용해서 문제를 해결. 2. 가장 큰 직사각형은 일정한 구간 내에서 가장 낮은 높이에 의해 결정된다. 3. tree[node] = 일정한 구간 (i, j)에서의 가장 낮은 높이의 인덱스. 주의할 점 || 생각해볼 점(Caution || Consideration) 1. 2로 나누고 곱하는 과정을 쉬프트 연산을 이용하면 조금 더 빠르게 해결할 수 있다. 참고(Reference) - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 14729 - 칠무해 문제 링크https://www.acmicpc.net/problem/14729 문제 해결 1. 7개까지 vector로 입력 받아서 정렬한다. 2. 그 이후에는 lower_bound를 통해서 vector에 삽입할 지 결정한다. 3. 만약 iterator가 7보다 작다면(vector안에 들어오는 범위의 값이라면), 그 자리에 삽입하고 나머지는 뒤로 밀어낸다. 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2696 - 중앙값 구하기 문제 링크https://www.acmicpc.net/problem/2696 문제 해결 1. 중앙 값을 구하기 위해서 우선 순위 큐(Priority Queue) 2개를 사용한다. 2. 중앙 값을 변수 val에 저장한다. 그리고 val과 새로 주어진 값의 크기를 비교한다. 주의할 점 || 생각해볼 점 - 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 5675 - 음주 코딩 문제 링크https://www.acmicpc.net/problem/5676 문제 해결 1. 수열의 크기, 쿼리 모두 최대 이므로, segment tree를 이용한다. 2. segment tree를 initialize할 때, 양수면 1, 음수면 -1, 0이면 0을 tree[node]에 넣어준다. 주의할 점 || 생각해볼 점 1. 값을 구하는 쿼리에서 범위를 넘어가게되면 1을 출력한다. 왜냐면 1은 양, 음, 0 에 영향을 끼치지 않기 때문이다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2605 - 줄 세우기 문제 링크https://www.acmicpc.net/problem/2605 문제 해결 1. 매 번 뽑기가 진행될 때, 중간에 삽입이 될 수 있다. → 자료구조 List를 사용하는 것이 좋다. 주의할 점 || 생각해볼 점 1. iterator사용하는 C++ 문법을 조금 신경쓰면 될 거 같다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 2504 - 괄호의 값 문제 링크https://www.acmicpc.net/problem/2504 문제 해결1. 여는 괄호문자들은 스택(이 문제에선 Deque를이용했다)에 삽입한다. 이 때, 문자와 Boolean값을 Pair의 형태로 유지한다. 그 이유는 여는 괄호문자가 중복이 되었을 때, 곱하는 데에 사용되었는 지 체크하기 위해서다. 2. 만약 닫는 괄호문자 이 나오면, ① 스택이 비어있거나, 제일 최근에 쌓인 문자가 닫는 괄호문자와 쌍을 이루지 않는다 → 잘못된 괄호열② ①번이 아니고, 답에 괄호 값을 곱했다 → 값에 영향을 주지 않고 되돌아간다.③ ①, ②번이 아니다 → 스택의 처음 괄호문자부터 최근에 쌓인 괄호문자까지의 괄호 값을 곱해서 답(ans)에 더 해준다. 3. 모든 괄호 문자열을 체크했는데 스택에 문자가 남아있.. 더보기 이전 1 다음