관심이 가는 개발 보물창고

풀이 읽다 보니까 운영체제 프로세스 스케줄링이 생각나는 문제. 모든 소가 농장에 최소한의 시간으로 들어오려면 어떻게 해야 할까? 빨리 도착한 소부터 넣어주면 된다. 빨리 도착한 소부터 차례대로 하려면 도착시간을 기준으로 오름차순 정렬해주자. 처음 도착한 소는 도착 시간과 검문 시간을 모두 더해 정답에 넣어준다. 이유는 한 마리의 소만 존재한다면 그 소가 도착하고 들어간 시간이 정답이기 때문이다. 두 번째 소부터는 다음과 같은 규칙대로 시간을 계산한다. 이전에 들어온 소가 농장에 입장하기까지 걸린 시간을 ans라고 하자. 1. 두 번째 소가 ans보다 더 늦게 도착했다면, 즉 기다린 시간이 없다면 ans = 두 번째 소 도착 시간 + 검문 시간 2. 두 번째 소가 ans보다 빠르게 도착했거나 같다면 이 때..

multimap? multimap은 기본적으로 map과 비슷하지만 다른 부분들이 있다. 비슷한 부분은 [map]에서 확인하자. 1. Key의 중복을 허용한다. 2 [] 연산자를 지원하지 않기 때문에 insert() 멤버 함수로 삽입해야 한다. 연습해보기 #include #include using namespace std; int main() { // less < // left child key < parent key

map? 1. 연관 컨테이너이며 노드 기반 컨테이너 2. 특정 정렬 기준으로 원소(Key)가 자동으로 정렬된다. 3. 균형 이진트리의 장점을 가지고 있어 찾기, 삭제, 삽입의 성능 O(lgN)을 보장한다. 자주 사용하는 멤버 함수 기본적으로 연관 컨테이너 set과 똑같지만 차이점을 주자면 [] 연산자를 제공한다. [] 연산자를 이용해서 원소(key, value)를 삽입하거나, key에 매핑된 value를 갱신할 수 있다. 아래에는 자주 사용하는 부분들을 정리했다. insert(pair(key,value)) map에 pair 객체로 key와 value를 저장한다. map[key] = value map에 key에 해당하는 원소가 없다면 (key, value) 저장하고 key에 해당하는 원소가 있다면 valu..

풀이 지문이 엄청 길지만 확실하게 정리하면 다음과 같다. 전체 점수, 3점 투표수, 2점 투표수가 모두 같으면 회장을 결정할 수 없다. 전체 점수, 3점 투표수가 같으면 2점 투표수가 많은 학생이 회장이 된다. 전체 점수가 같으면 3점 투표수가 많은 학생이 회장이 된다. 이렇게 정렬 기준을 잡고 정렬한 다음에 첫 번째 학생과 두 번째 학생을 비교하면 해결할 수 있다. 비교하는 이유는 전체 점수, 3점 투표수, 2점 투표수가 모두 같은 경우가 존재할 수 있기 때문에 한 번 더 확인해주고 판단하기 위함이다. #include #include #include using namespace std; class Student { public: int idx; int total; int point3; int point..

정렬을 하다 보면 이런 문제들이 있다. www.acmicpc.net/problem/10814 10814번: 나이순 정렬 온라인 저지에 가입한 사람들의 나이와 이름이 가입한 순서대로 주어진다. 이때, 회원들을 나이가 증가하는 순으로, 나이가 같으면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 프로그램을 www.acmicpc.net 나이가 증가하는 순서로 정렬을 하지만 만약에 나이가 같다면 먼저 가입한 사람이 앞에 오는 순서로 정렬하는 문제 이러한 문제처럼 먼저 들어온 사람이 먼저 출력되는 것을 아래와 같이 정리할 수 있다. 정렬되지 않은 상태에서 같은 키(나이) 값을 가진 원소의 순서가 정렬 후에도 유지가 되는가? 이러한 개념이 바로 Stable Sort 이라고 하며 안정된 정렬이라고 불린다. Stabl..

문제 풀이 힙 2개를 이용하면 쉽게 해결할 수 있다. 각 각의 최대 힙과 최소 힙을 준비하자. 그리고 규칙에 따라 들어오는 input을 처리하면 된다. 1. max-heap 크기 > min-heap 크기 만족하면 min-heap에 넣는다. 아니라면 max-heap에 넣는다. 2. max-heap의 루트 노드 > min-heap의 루트 노드 만족하면 서로 swap 한다. 3. 홀수 번째 수를 읽을 때마다 중앙값을 처리해야 하므로, 홀수 번째이면 그때 max-heap의 루트 노드를 반환하면 된다. 문제의 예시를 보면 다음과 같이 흘러간다. 1이 들어오면 max-heap 1 min-heap 5가 들어오면 max-heap 1 min-heap 5 4가 들어오면 max-heap 4 1 min-heap 5 3이 들어..

풀이 생각보다 고생한 문제!! 주어진 문자열의 길이가 100만이기 때문에 여기서 빈번한 삭제와 삽입이 필요하므로 list 자료구조를 이용해야 한다. 문제는 list에 대해서 얄팍하게 알고 있다면 크게 디일 수 있다.. 문제에서는 커서를 이용해서 옮겨 다니며 리스트에 해당 문자를 삽입하거나 삭제하는 구조로 되어있다. 따라서 처음에 cursor를 list의 첫 번째 반복자로 할당해놓고 양방향 반복자이므로 뒤로 갔다 앞으로 갔다 하면서 주어진 문제에 맞게 동작을 처리하면 된다. '' cursor 오른쪽으로 else if (s[i] == '>') { if (cursor != lt.end()) cursor++; } '-' cursor 한 칸 왼쪽으로 당겨서 지워주고 cursor의 위치를 그 다음 위치로 옮겨야 한..

풀이 뱀이 이동할 때를 생각해보자. 이동할 때 머리를 쭉 늘려 전진하고 뒤의 꼬리를 땡겨온다. 자료구조 deque 를 사용하면 편하게 구현할 수 있다. (앞 뒤로 땡기거나 늘릴 수 있기 때문) 뱀이 이동하기 때문에 1초가 소요된다. 아래의 로직들은 1초 동안에 수행되는 행동들이다. 뱀이 움직이는 방향을 아래와 같이 정의할 수 있다. dir = 0 오른쪽 dir = 1 아래쪽 dir = 2 왼쪽 dir = 3 위쪽 int dx[] = { 0,1,0,-1 }; int dy[] = { 1,0,-1,0 }; dir 방향대로 움직인다고 했을 때 다음칸을 확인해보고 움직임을 결정하면 된다. 사과가 있는 칸인 경우 해당 칸을 먹었다고 표시해주고, 뱀의 머리를 늘려주면 된다. 이때 꼬리는 자르지 않는다. 사과가 없는 ..

풀이 처음에 시간 초과가 난 문제. 이유는 현재 가장 높은 중요도 문서를 찾는데 O(N)를 추가로 구하기 때문이다. 생각해보니까. 우선순위 큐를 이용하면 O(N)에 찾는 것이 아닌 가장 위에 있는 원소만 확인해보면 O(1)에 된다는 것을 알았다. 기본적으로 우선순위 큐는 삽입할 때 알아서 우선순위대로 만들어주기 때문이다. 자료구조 2개를 써서 풀었다. - 큐에는 (중요도, 문서 번호) - 우선순위 큐에는 (중요도) 문서를 하나씩 앞에서 보면서 현재의 문서보다 더 높은 중요도 문서가 있으면 해당 문서를 큐 뒤에 보낸다. 아니라면 현재의 문서를 큐에서 pop 하고, 우선순위 큐에서도 pop 한다. 이때 내가 찾는 문서의 번호라면 그 값을 출력하면 된다. #include #include #include usi..

한동안 엄청 고생했던 것을 바탕으로 작성한다. Unity 상에서 Button에 이벤트를 할당하는 방법은 2가지가 있다. 직접 Inspector 창에서 매핑하기 스크립트 상에서 할당하기 using UnityEngine.UI; GoPCBtn.onClick.AddListener(func); 보통은 매핑하기 힘들거나 코드를 한눈에 파악하기 힘들 때 사용하는 방법이 스크립트 상에서 할당하는 것이다. 가끔 Button 에 이벤트를 추가할 때 기존에 추가한 이벤트를 지우고 싶은 순간이 찾아오게 된다. 예를 들어 활성화될 때마다 리스너를 추가한다던가, 한 Popup 안에서 다양한 기능들을 스위칭해서 사용하는 경우 이때 사용하는 것이 바로 RemoveListener 혹은 RemoveAllListener이다. 알아둬야 할..