DMLab 알고리즘 스터디 (FDA) 2주차
포스트
취소

DMLab 알고리즘 스터디 (FDA) 2주차

개요

저번 주 모임을 못 해서, 이번주까진 그냥 내가 뽑았다.

A번: 한 줄로 서기

1138

문제 요약

키가 1~N인 사람들이 있고, 각자 자기보다 왼쪽에 몇 명이 있었는지만 기억할 때 줄 세우기

설명

뭔가 와닿지 않아 생각보다 헷갈렸다.
풀이 자체는 간단한 편이다.

  1. 키 기준 정렬
  2. 돌면서, 왼쪽에 자신보다 큰 사람이 다 채워졌다면 선택

제한이 넉넉해 $N^2$로 그냥 구현하면 된다.

B번: 가장 가까운 세 사람의 심리적 거리

20529

문제 요약

사람들의 MBTI들이 주어질 때, 해밍 거리의 총합이 가장 작은 세 명을 구하면 된다.

설명

사람의 수 N은 100000까지이므로 $N^3$은 못한다.
그래서 $16^3$으로 거리를 계산해두고, [(거리, 조합)] 꼴로 만들어 거리순 정렬해둔다.
사람마다의 mbti는 count 배열을 만들어 관리한다.
그럼 정렬된 조합마다 가능한지 여부를 확인할 수 있다.

C번: 트리와 쿼리

15681

문제 요약

루티드 트리에서, 어떤 정점 U의 서브트리 내의 정점 수를 묻는 질의를 처리한다.

설명

업데이트 같은 게 없으므로 그냥 dfs로 그래프->루티드트리 진행할 때 같이 세 주면 된다.

D번, E번: 용액 / 두 용액

2467

문제 요약

두 문제는 같은 문제라서 솔브드 점수 복사하라고 넣어뒀다.

수열에서 합이 가장 작은 쌍 찾기

설명

N개의 아이템마다 돌며 이분 탐색으로 찾으면서 최소값 갱신하기.
즉 $N \log{N}$이다.

F번: 뉴스 전하기

1135

문제 요약

트리에서 소식을 전파한다. 전파는 자식 하나마다 1초가 걸린다.
가장 빠르게 전파할 때 걸리는 시간를 구하기
설명하기 애매하므로 문제를 읽어보자.

설명

자식 중 가장 오래 걸리는 자식에게 먼저 전파해야 한다는 것만 캐치하면, C번 문제와 별로 다를 게 없다.
DFS 한 번으로 풀 수 있다.

G번: 약 팔기

15311

문제 요약

1~1000000 중 어떤 값이든 구간합으로 만들 수 있도록 하는 배열을 구성하는 문제

설명

꽤 오래 걸렸고, 답을 알게 되고 어이가 없었다.
처음엔, 구간합 배열로 치환하여서
임의의 정렬된 배열 A에서, 모든 x에 대해 $A[j] - A[i] = x$, $(i<j)$ 인 경우가 존재하게 만드는 것으로 생각했다.
하지만 거기서 딱히 발전이 되지 않았다.

그 다음엔 진법으로 생각해봤는데, 연속된 구간이라는 점에서 막혔다.
1 1 2 2 4 4 같은 식으로 중복을 시키는 경우도 생각해봤지만 마찬가지였다.
그러다가 한 가지 아이디어를 캐치했는데, 연속된 부분이라면 $A \cdot P + B \cdot Q$ 같은 형태로 나타낼 수 있다는 것이다. A,B가 값이고, P,Q가 개수와 같은 형태이다.

K=2000, N=1000000이라는 값이 작위적이므로, 위 아이디어를 적용해 조금 생각해봤더니 바로 풀렸다.
A, B를 1, 1000으로 하면 된다…

후기

G번 문제만 한참 걸렸는데, 답을 알고 나니 너무 허무했다.

This post is licensed under CC BY 4.0 by the author.