문제 신규 아이디 추천 접근 그냥 문제에서 주어진 7단계를 순서대로 나열해서 풀었다. 코드 파이썬 코드 import re def solution(new_id): new_id = new_id.lower() new_id = re.findall('[a-z0-9\.\-\_]',new_id) new_id = '...

문제 순위 접근 얼핏보고 위상 정렬인줄 알았다. 위상 정렬로 풀려고 하다보니 쉽게 풀리지 않아서, 처음부터 다시 생각해보게된 문제. 핵심은 A가 B를 이겼고, B가 C를 이겼다면 A도 C를 이긴셈이다. 이 연결관계를 표현할 수 있어야한다. 모든 연결 관계를 포함했을 때 A에게 진사람과 이긴 사람의 수가 n-1이면 순위를 표현할 수 있다....

문제 섬 연결하기 접근 최소신장트리를 찾는 문제이다. 주어진 그래프에서 최소 비용으로 트리를 만들면 된다. 최소신장트리 알고리즘은 크루스칼, 프림 알고리즘이 있다. 크루스칼 알고리즘의 경우 탐욕적으로 가장 가중치가 작은 간선들을 선택하며, 선택된 간선들만을 이용하여 노드들을 연결한다. 이 때 사이클이 형성되는 것을 막기위해 연결된 노드들...

문제 거스름돈 접근 DP 문제이다. n의 크기만큼, 그리고 화폐 종류만큼 미리 배열을 할당해준다. DP(x,y) 는 x번째 화폐까지 사용하여 y원을 만들 수 있는 경우의 수라하자. 예제처럼 화폐 종류가 1,2,5가 있을 때, DP(2, 10)은 1,2원을 사용하여 10원을 만들 수 있는 경우의 수이다. 이제 그럼 DP를 어떻게 계산해 ...

문제 단어 변환 접근 변환 가능한 단어의 경로를 따라가면서 target에 가장 빨리 도달하는 방법을 찾는 문제이다. BFS 알고리즘을 이용하면 쉽게 탐색 가능하다. 아예 전처리해서 그래프 형식으로 만들어놓고 탐색할까 하다가 그렇게까지 안해도 될거같아서, 그냥 단어 전체를 보며 다음 경우의 수를 탐색했다. isConvertPossible ...

문제 입국심사 접근 이 문제도 이분탐색 문제이다. 제한 사항을 보면 범위가 매우 큰 걸 볼 수 있는데, 이런 경우 일반적으로 완전탐색처럼 전체를 본다는 생각을 버려야 한다. 이 경우에는 특정 시간이 t가 있을 때, 해당 시간에 모든 심사자가 심사를 받을 수 있는지 판단할 수 있으면 된다. 그럼 모두 심사를 받을 수 있는 t 중에 최소값을...

문제 기지국 설치 접근 station의 위치가 정렬된 채로 들어오기 때문에 따로 전처리 해줄 필요는 없다. 우선 전파의 거리 range를 구해놓자. 자기 자신과 좌, 우로 전달되므로 range = w * 2 + 1 이 될 것이다. 이제 정렬된 스테이션을 하나씩 보면, station의 위치를 x라고 하면 처음은 1번 아파트부터 x-w 아파트...

문제 이중우선순위큐 접근 heap을 이용하는게 정석이겠지만, 그냥 리스트를 이용해도 괜찮다. 코드 파이썬 코드 def solution(operations): pq = [] for operation in operations: command, num = operation.split(' ') ...

문제 최고의 집합 접근 원소들의 곱의 최대는 각 원소의 크기를 고르게 키워줘야 한다. 즉 주어지는 수 s를 n으로 나눈 몫 이상을 모든 원소가 가졌을 때가 가장 크다. 따라서, 기본적으로 몫을 모든 원소가 가진채로 나머지를 각 원소에 한개씩 더해준다. 코드 파이썬 코드 def solution(n, s): answer ...

문제 단속카메라 접근 진입 지점 혹은 진출 지점 중 하나를 기준으로 놓고 문제를 풀면된다. 나는 진입 지점을 기준으로 잡고 진입 지점으로 정렬해주었다. 가장 늦게 진입한 차의 진입점에 카메라를 설치하고, 해당 카메라와 만나는 차들을 모두 제거한다. 남는 차중 가장 늦게 진입한 차의 진입점에 또 카메라를 설치하고, 차가 안남을 때까지 반복해...