https://www.acmicpc.net/problem/2295난이도: 골드4알고리즘: 이분탐색 풀이과정주어진 수열에서 `x + y + z = k`를 만족하는 x, y, z, k를 선택하는 문제이다. 여기서 x, y, z, k는 중복될 수 있다. 가장 먼저 생각했던 방식은 x, y, z를 전수조사를 통해 선택하고,` x + y + z`가 수열에 있는지를 이분탐색을 통해 확인하는 방법이었다.하지만 이 방법은 `N^3` x `log N` 의 시간 복잡도를 가지고, N = 1000이기 때문에 시간 초과가 발생한다. 따라서 y + z를 먼저 계산한 리스트를 만들었다.y + z를 계산한 리스트는 `N^2`의 시간 복잡도 내에서 만들 수 있다. 이제 `x + y + z = k`에서 x와 k를 먼저 선택하고, (k..
https://school.programmers.co.kr/learn/courses/30/lessons/68646 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr난이도: Lv3알고리즘: DP 풀이과정우선 입력으로 주어지는 a의 길이를 보면 `1,000,000`으로 매우 큰 크기의 배열이 들어온다. 그렇다면 우리는 a의 각 풍선을 순회하며 해당 풍선이 마지막에 남을 수 있는지의 여부를 O(1) 또는 O(log n) 시간에 판단해야 한다. DP를 사용하면 O(1) 시간에 각 풍선이 마지막에 남을 수 있는지를 알 수 있다. 입출력 예인 `[-16,27,65,-2,5..
https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr알고리즘 분류플로이드 워셜 풀이과정출발지점 s에서 a와 b로 가는 경로에서 동승하는 구간을 포함한 최솟값을 구하는 문제이다.시작점 s로부터 a와 b로의 최단거리를 구하는 방법은 `다익스트라` 또는 `플로이드 워셜` 알고리즘으로 쉽게 구할 수 있다. 그렇다면 동승 구간을 어떻게 처리할 지를 잘 생각해보면 된다.시작점 s로부터 x지점까지 동승을 한다고 가정하면 요금 합은 `s -> x` + `x -> a`..
https://www.acmicpc.net/problem/2531난이도: 실버 1알고리즘: 구현?풀이과정가장 많은 종류의 초밥을 먹을 수 있는 경우를 구하는 문제다. k개의 연속된 수열에서 서로 다른 숫자가 나오고, 쿠폰으로 받는 종류까지 고려해야 한다. for i in range(0, n + k - 1)0 ~ n + k - 1번까지 반복한다. n이 아닌 n + k - 1인 이유는 초밥의 마지막 줄에서 시작해서 초밥의 처음이 다음에 오는 경우까지 고려해야 하기 때문이다.cur = set()for x in range(k): cur.add(board[(i + x) % n])cur.add(c)현재 연속된 k개의 수열에서 곂치는 숫자가 없음을 보장하기 위해서 set 자료형을 사용한다. 또한 n + k - ..
![]()
https://www.acmicpc.net/problem/15685난이도: 골드3알고리즘: 구현 풀이과정현재까지의 점들로 드래곤 커브를 실행했을 때의 점들을 구하는 것을 구현만 하면 된다. 여기서 가장 마지막에 추가한 점을 기준으로 항상 시계방향으로 회전하는데, 잘 살펴보면 규칙을 찾을 수 있다.위 상황에서 가장 마지막에 추가된 점이 (1, -1)일때, 이 점들을 시계방향으로 회전시키는 것을 생각해 보자.먼저 (1, -1)은 고정점이기 때문에 움직이지 않는다. (1,0)은 (1, -1)에서 y축 방향으로 한 칸 아래에 있는 점이고, 아래쪽 방향으로 시계방향으로 회전하면 왼쪽이 된다. 따라서 (1, -1)에서 왼쪽으로 한 칸 이동한 (0, -1)이 추가된다.이제 (0, 0)을 시계방향으로 회전하면 어느 위..
https://www.acmicpc.net/problem/1655난이도: 골드2알고리즘: 우선순위 큐 풀이과정현재까지 입력받은 숫자들 중 중간 값을 출력하면 되는 간단한 문제다. 문제가 되는 부분은 역시 시간 복잡도 부분이다. 입력의 크기 N의 크기가 100,000이고 시간 제한은 0.1초이므로, N번의 반복문에서 O(log N) 시간 안에 중간 값을 찾아야 한다. 수열을 관리하기 위해 리스트 자료형을 사용할 경우, insert() 함수를 사용할 때 O(N)의 시간복잡도가 발생하므로 사용할 수 없고, 우선순위 큐를 사용해야 한다. 여기서는 중간값보다 작은 수들을 관리하는 우선순위 큐와, 보다 큰 수들을 관리하는 우선순위 큐 두 개를 사용했다. 맨 처음 숫자를 입력 받고 해당 숫자를 mid에 할당해 준다..
