1.
문제 : 分 (Minutes)
2.
알고리즘 : 사칙연산
3.
성공 여부 : 성공 (1분)
4.
풀이 : 패스
5.
복기 : 일본어 문제라 당황했지만, 시간 H와 분 M이 주어졌을 때 총 몇 분인지 계산하는 간단한 문제
1.
2.
알고리즘 : 그리디, 비트마스킹
3.
성공 여부 : 실패
4.
5.
복기 : Sean과 Patrick이 캔디를 나누는 문제. Patrick은 이진법 연산을 잘하지만 두 수를 더했을 때 remainder를 다음 비트로 옮기는 걸 까먹는다. 이를 이용해 캔디를 두 부분으로 나눴을 때 Patrick이 느끼기에 같은 값이라고 느끼도록 Sean이 가장 많은 값의 캔디를 가져가는 방법을 구하는 문제. Patrick의 방식이 XOR연산이라는 것과, XOR연산은 교환 법칙을 만족하며 같은 숫자를 XOR하면 0이 된다는 아이디어를 알았어야 한다.
1.
문제 : 중력 큐
2.
알고리즘 : 구현, 자료 구조, 많은 조건 분기, 덱
3.
성공 여부 : 성공 (1시간)
4.
풀이 : 보류
5.
복기 : 네 방향으로 회전하는 큐에서 중력이 작용할 때, 공이나 가림막의 개수를 구하는 문제. Doubly Linked List로 구현했는데, 중력에 따른 조건을 하나 빼먹어서 여러 번 틀렸다. 문제를 풀 때는 완벽하게 구현할 목표를 세워놓고 풀자.
1.
문제 : 이중우선순위큐
2.
알고리즘 : 힙
3.
성공 여부 : 성공 (15분)
4.
풀이 : 이중우선순위큐
5.
복기 : 이중우선순위큐를 공부할 수 있는 기본 문제. Max-Heap, Min-Heap 두 개의 힙을 이용해 최댓값과 최솟값을 관리한다는 아이디어와 한쪽 힙에서 deleted된 노드를 다른 한쪽 힙에서 lazy하게 처리한다는 아이디어를 생각해야 한다.
1.
문제 : 덱 조작과 쿼리
2.
알고리즘 : 자료구조, 트리, 스택
3.
성공 여부 : 성공 (2시간)
4.
풀이 : 보류
5.
복기 : 덱을 조작하는 최대 500,000개의 쿼리가 있고 가장 위에 카드를 놓는 push, 가장 위의 카드를 제거하는 pop, i번째 행동 이후의 상태로 되돌리는 restore, 현재 덱에 있는 카드의 모든 수의 합을 출력하는 print가 주어질 때, 결과를 출력하는 문제. 상태를 되돌리는 restore를 위해 어떻게 상태를 최적화해서 저장해야 할 지 고민해야 하는 문제였다. 한 499,000개의 push가 있고 그 이후에 restore가 반복된다면 일반적인 Linked List로는 왔다갔다하다가 시간초과가 날 것으로 예상. log 클래스를 만들고 계속 이어붙이되, log 클래스에서 저장해야 하는 상태는, 이전 노드 prev와 그 때까지의 sum으로 만든다.
1.
문제 : 지수연산
2.
알고리즘 : 수학, 임의 정밀도/큰 수 연산
3.
성공 여부 : 성공 (10분)
4.
풀이 : 패스
5.
복기 : 1 / (2 ^ n) (1 ≤ n ≤ 250)을 구하는 문제. 자바에서 일반적인 double을 사용해서 구하면 부동소수점 방식이기 때문에 일정 소수점 이하로 길어지게 되면 지수를 이용해서 표현하므로 풀 수 없다. 그러므로 String으로 표현하고 각 자리수를 2로 나누는 수학 풀이의 일반적인 방식을 사용했다. 추후 다른 풀이를 보니 BigInteger.valueOf(2).pow(n)과 BigDecimal.ONE.divide(new BigDecimal(num), n, RoundingMode.UNNECESSARY)를 사용하는 풀이도 있었다.
1.
문제 : 화분 부수기
2.
알고리즘 : 그리디 알고리즘
3.
성공 여부 : 성공 (20분)
4.
풀이 : 패스
5.
복기 : 태완이가 화분을 직접 깨야 하는 개수를 구하는 문제. 화분에는 3개의 숫자가 각각 적혀있는데, 이 화분을 깨면 오른쪽에 있는 모든 화분 중 깬 화분에 적혀있는 숫자와 같은 숫자를 가진 화분이 모두 깨진다. 따라서 입력을 받으면서 불리언 배열에 이미 들어온 적 있는 숫자인지 확인 후 깨버리면 된다. 문제 예시를 애매하게 해놔서 이해하는 데 조금 어려움을 겪었다.
Loading comments...
