https://school.programmers.co.kr/learn/courses/30/lessons/43238 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 이분탐색 문제이다. 다만 이 문제가 좀 까다로운 점은, 도대체 뭘 탐색해야 할까? 에 대한 물음일 것이다. 최악의 경우를 따져보았을 때, 걸리는 시간이 너무 커서 탐색할 엄두도 안나겠지만, 이분탐색은 log n의 시간 복잡도를 가지므로 충분히 해결할 수 있다. 다른 이분탐색 코드와 다른 점이 있다면, 1. 개인의 심사원이 주어진 시간(mid)동안 처리할 수 있는 손님의 수를 구하는 코드 2. 예를..
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 최소신장트리(MST)를 만드는 알고리즘을 약간 응용한 문제이다. 우선 주어진 입력을 바탕으로 MST를 생성한다.(프림 또는 크루스칼 이용) 문제에서 요구하는 조건을 만족하기 위해서는, 생성된 최소신장트리에서 간선의 비용이 가장 큰 것을 하나 찾은 뒤 그곳을 기점으로 잘라주면(=간선을 제거하면) 문제의 조건을 충족시킬 수 있다. #include using nam..
https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 2467번 용액, 2470번 두 용액, 2473번 세 용액으로 이어지는 시리즈 문제이다. 전체적인 맥락은 비슷하므로 한 문제만 포스팅하겠다. 투포인터, 이분탐색의 활용문제이다. 총 3개의 포인터가 필요한데 약간의 테크닉이 필요하다. 우선 개략적인 방법은 흔한 투포인터를 이용한 이분탐색과 동일하다. 여기에 하나의 포인터를 추가하는데, 포인터 하나를 고정해서 이용한다! 맨 앞을 ..
https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 소수 판별 알고리즘 + 투포인터 알고리즘의 조합이다. 우선, 에라토스테네스의 체를 이용하여 소수를 걸러준다. N의 범위가 4백만이므로 그냥 이중 for문을 사용하면 TLE다. (소수를 거른다는 것은, 소수끼리만 따로 모아준다는 것을 뜻한다. 그렇게 된다면 자연스레 소수들은 연속되게 된다.) 거른 소수를 따로 저장해준 뒤, 이를 이용해 투포인터 알고리즘을 작동시킬 것이다. 필요한 변수들을 선언 해준 뒤, left와 right 사이의 구간합을 구해준다. 이때 구간합이 n보다 작으면 right가 가리키는 소수를 더해준다...
https://www.acmicpc.net/problem/22354 22354번: 돌 가져가기 처음 위치 기준 왼쪽에서 $5,\ 6,\ 2,\ 3,\ 4,\ 7,\ 8,\ 1$번째 돌을 순서대로 가져가면 $3$번째 돌과 $5$번째 돌을 가져갈 때 점수를 얻어 $13$점이 된다. www.acmicpc.net 내가 푼 문제중 제일 티어가 높은 문제이다.. 게다가 그리디라 생각하기가 엄청 어려웠다 우선 돌을 최적으로 가져가는 방법에 대해 설명하겠다. 1. 연속된 돌은 반드시 1개만 가져갈 수 있다 (= 연속된 돌에서는 점수를 2번 이상 얻을 수 없다) -> 이 부분은 돌들을 그려놓고 한번 해보길 바란다. 이웃한 돌들이 색이 달라야 점수를 얻는데, 이웃한 돌이 같은 색이면 애초에 점수를 얻을 수 있는 환경이 아..
https://www.acmicpc.net/problem/4354 4354번: 문자열 제곱 알파벳 소문자로 이루어진 두 문자열 a와 b가 주어졌을 때, a*b는 두 문자열을 이어붙이는 것을 뜻한다. 예를 들어, a="abc", b="def"일 때, a*b="abcdef"이다. 이러한 이어 붙이는 것을 곱셈으로 생각한다 www.acmicpc.net 이 문제를 보고, '반복 가능한 최소 길이의 부분 문자열' 을 찾으면 될 것 같았다. 없으면 1 출력해주고 어떻게 찾을까 고민하던 중, 실패함수의 마지막 값은 문자열 전체를 봤을 때의 최장 부분 문자열을 구한 것이므로 내가 찾고자 하는 '반복 가능한 최소 길이의 부분 문자열'의 길이는 전체 문자열 - 실패함수의 마지막 값을 통해 구할 수 있다! 그래서 전체 문자..
