본문 바로가기
반응형

Algorithm/프로그래머스131

[프로그래머스/C++] 선입 선출 스케줄링 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 core가 처리해야하는 작업이 있다면, 모든 작업을 처리할 경우 몇 번째 코어가 최종작업을 실행하는지를 찾는 문제다. 특정 시간에 각 core가 처리한 작업의 수를 찾는 방법은 나눗셈을 이용하면 쉽게 계산할 수 있다. 그렇기 때문에 n개의 작업을 처리할 수 있는 특정 시간을 찾으면 몇 번째 코어가 최종 작업을 실행하는지 알 수 있다. 여기서 특정 시간을 찾는 방법은 이분탐색으로 쉽게 찾을 수 있다. 이분탐색을 사용할 경우 log(N)의 시간 복잡도로 탐색을 할 수 있기 때문에 이 문제의 시간 복잡도는 코어의 수*log(N) 이 된다. 여기서 주의할 점은 특정 시간에 수행할 수 있는 작업은 0시간에는 c.. 2024. 3. 21.
[프로그래머스/C++] 동굴 탐험 (2020 카카오 인턴십) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제에서 중요한 점은 순서를 지켜서 방문하는 order의 제약사항에 있다. order에서 주어지는 데이터를 [선 방문할 방 : 후 방문할 방] 라고 하자 제약사항을 읽어보면 order에 한번이라도 나온 방인 경우 order의 다른 데이터에 나오지 않는다. 즉, 요약하면 하나의 방은 먼저 방문할 방 나중에 방문할 방 상관 없는 방 3가지 경우로 구분할 수 있다. 여기서 먼저 방문할 방이나 상관 없는 방은 언제 방문해도 상관이 없다. 중요한 방은 나중에 방문할 방이다. 나중에 방문해야하는 방은, 사전에 방문해야 하는 방이 있다는 뜻이므로 사전에 방문 해야하는 방을 먼저 방문하면 된다. 그림을 통해 더 쉽게 알아보.. 2024. 3. 20.
[프로그래머스/C++] 인사고과 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 특정 사원보다 근무 태도 점수와 동료 평가 점수가 낮은 사원을 등수에서 제외하는게 핵심인 문제다. 그렇기 때문에 정렬만 잘 하면 쉽게 해결할 수 있다. 먼저 인사고과 중 근무 태도 점수와 동료 평가 점수 중 하나를 기준으로 정렬을 한다. 예를 들어 근무 태도점수를 기준으로 내림차순으로 정렬을 한다고 가정하자. 위 그림과 같이 정렬이 됐다면, 탐색을 시작한다. 근무 태도 점수는 이미 정렬이 됐으므로 중요한 점수는 동료 평가 점수이다. 여기서 prevMax와 nowMax 두 변수를 사용하는 이유는 근무 평가 점수가 같을 수 있기 때문이다. A 직원이 B직원보다 동료 평가 점수가 높아도 A직원과 B직원의 근.. 2024. 3. 19.
[프로그래머스/C++] 매칭 점수 (2019 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 어려운 문제는 아니지만 주소를 찾거나 단어를 찾는 과정이 생각보다 까다로웠다. 단어를 구분해 주고, 어떤 부분부터 주소를 나타내는지 찾아주어야 하기 때문이다. 먼저 점수를 계산하기 위해 특정 단어가 몇번 나왔는지 찾는 방법을 알아보자 여기서 중요한 점은 특정 단어는 대소문자 구분을 하지 않는다는 점이다. 그래서 대소문자 구분을 하지 않도록 전부 소문자로 변경을 해주었다. 특정 단어의 경우 알파벳으로만 이루어져 있어야 한다. 만약 abc라는 글자가 찾는 단어일 경우 abcabc인 단어는 내가 찾는 글자가 아니다. abc@abc인 경우에는 중간에 @가 있으므로 구분된 단어라 abc가 두개 있으므로 2점이 .. 2024. 3. 18.
[프로그래머스/C++] 호텔 방 배정 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 Set과 Map을 이용해서 이미 배정된 적이 있는 방 번호라면 바로 다음 방을 찾도록 하면 해결될 것이라는 생각이 들었던 문제다. Set에는 이미 배정받은 방들의 수를 저장하고, Map에는 [배정받길 원하는 방 : 다음에 실제로 배정받을 방]의 구조로 저장한다. 처음에 특정 방을 배정받고 싶을 때, 그 방이 Map에 없으면 첫 방문이다. 그러므로 원하는 방에 해당하는 숫자를 가져온다. 만약 Map에 있다면 첫 방문이 아니므로 이미 Map에 저장된 수를 가져온다. 이후 가져온 숫자가 Set에 있으면, 이미 배정받은 방이므로 Map에서 그 숫자가 다음에 실제로 배정받을 방의 숫자를 가져온다. 이 과정을 W.. 2024. 3. 16.
[프로그래머스/C++] 공 이동 시뮬레이션 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을때 고민을 많이 했다. 좌표의 범위가 매우 크기 때문에 모든 좌표를 직접 검사하는 것은 불가능하다. 그래서 처음 했던 생각은 시작 좌표에서 거꾸로 쿼리를 진행하면, 더 빠르게 체크를 할 수 있겠다고 생각이 들었다. x좌표와 y좌표는 서로 영향을 미치지 않으므로 1차원 좌표를 그려 풀이를 생각해보자 위 그림과 같이 쿼리를 거꾸로 진행하는데 왼쪽으로 5번 이동하라는 쿼리가 나오는 경우를 생각해보자. 이때 도착점이 3이 되려면 이전에 E의 위치는 8이여야 하는데, 실제 좌표는 7까지이므로 불가능한 경우다. 그렇다면 항상 좌표의 범위를 벗어나면 불가능한 경우일까? 위 경우에서는 E가 -1로 범위 바깥.. 2024. 3. 15.
[프로그래머스/C++] 스티커 모으기 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 하나의 스티커를 떼면 양옆의 스티커를 사용할 수 없게 된다. 원으로 이어진 스티커를 위와 같이 직선으로 생각해 보자. 만약 첫번째 스티커를 뗀다면 마지막 스티커는 원형이므로 첫번째 스티커와 붙어있어 뗄 수 없게 된다. 하지만 첫번째 스티커를 그대로 둔다면 마지막 스티커를 뗄 수 있게 된다. 그러므로 2가지 경우를 생각해 각각 계산하고, 첫번째 스티커를 떼는 경우가 스티커 숫자의 합이 높은지 안떼는 경우가 스티커 숫자의 합이 높은지 계산하면 된다. 이제 어떤 스티커를 떼야하는지는 어떻게 알 수 있을까? 스티커가 위 그림처럼 나열되어 있을 때, i번째 스티커를 떼려면 i - 1번째 스티커는 떼지 않은 상태.. 2024. 3. 14.
[프로그래머스/C++] 미로 탈출 명령어 (2023 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 미로를 통과하기 위한 여러 경로 중 오름차순으로 가장 빠른 경로를 return하면 되는 문제다. 먼저 정확히 k번을 움직여 그 도착점에 도달해야하기 때문에 도달이 가능한지 판단하는 것도 중요하다. 만약 위 그림처럼 시작점과 목적지가 주어졌다면, 시작점에서 목적지로 도달하기 위해서는 짝수 번 움직여야한다. 왜냐하면 도착지점과 시작지점의 거리가 3+3 = 6으로 짝수이기 때문이다. 만약 k가 홀수라면 어떤 방법을 써도 도달할 수 없다. 이유는 쉽게 생각할 수도 있지만, 굳이 수식을 써서 증명을 해보면 먼저 s의 좌표를 sx, sy라고 하자 이제 상하좌우로 움직이는 횟수를 a, b, c, d로 표현하면 이동.. 2024. 3. 13.
[프로그래머스/C++] 지형 편집 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 봤을 때, 블록의 층에 해당하는 높이가 최댓값이라는 사실은 쉽게 추리할 수 있다. 예를 들어 블록의 층이 2층과 4층짜리만 있다고 가정하자. 이 경우 모든 블록을 2층으로 만들거나 4층으로 만들 경우에 답이 있다. 왜냐하면 3층에서 2층으로 만드는 비용을 a라고 하고, 3층에서 4층으로 만드는 비용을 b라고 하자. 그러면 위 그림처럼 4층에서 3층으로 가는 비용도 a로 같다. 그렇기 때문에 a와 b가 대소 관계를 갖게 된다면, 정답은 2층이나 4층에 있게 된다. (a==b인 경우만 3층일 경우가 정답이 될 수 있는데, 이 경우는 2층으로 쌓나 4층으로 쌓는 경우도 3층으로 쌓는 경우와 비용이 같게 된다.. 2024. 3. 11.
[프로그래머스/C++] 아방가르드 타일 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제를 처음 봤을 때 DP문제면서 매우 간단한 줄 알았다... 하지만 정답이 아니길래 곰곰히 생각해봤더니 많은 패턴들이 숨어있었다. 먼저 아래 그림을 보자 단순히 3개를 연속으로 붙이는 경우와 1개를 붙이는 경우의 패턴이 있다. 저 패턴들을 붙였을 때 길이를 k라고 하면, 아래와 같이 나타낼 수 있다. $$DP[k-3] \times 1, \,\,\,\,\, DP[k-1] \times 1$$ k보다 길이가 3 짧은 경우에서 3개를 붙여 현재 패턴을 만들 수 있고, k보다 1개 더 길이가 짧은 경우에서 현재 패턴을 만들 수 있기 때문에 위처럼 나타낼 수 있는 것이다. + 이러한 타일링 문제를 처음 보면 세워져있는.. 2024. 3. 10.
[프로그래머스/C++] 등굣길 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 출발지에서 도착지까지 도달하는 최단경로의 개수를 return하는 문제다. 여기서 방향은 항상 오른쪽 아래로 움직이기 때문에, 일정 횟수를 움직여서 도달할 수 있는 위치는 정해져 있다. 그러므로 n칸 움직여서 도달할 수 있는 위치는 위와 왼쪽방향에 있는 n-1칸 움직여서 도달할 수 있는 곳의 경우의 수의 합과 같다. 아래 그림을 참고하면 이해가 쉬울 것이다. 위 그림과 같이 1, 1이 출발지 3, 4가 도착지라고 하면 각 칸까지 이동하는데 걸리는 경우의 수를 나타낼 수 있다. 예를 들어 (2,2)에 도달하는 경우의 수는 (1,2)에서 아래로 이동하는 경우와 (2,1)에서 오른쪽으로 이동하는 경우가 있다... 2024. 3. 8.
[프로그래머스/C++] 등산코스 정하기 (2022 KAKAO TECH INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제에서 핵심은 특정 노드를 방문할 때마다 경로 중에서 가장 시간이 오래걸린 값을 저장해야 된다는 것이다. 그리고 가장 시간이 오래 걸리는 구간의 크기가 같다면 봉우리의 숫자가 가장 작은 값을 return해야한다. 이와 비슷한 문제를 해결하는 알고리즘 중에는 다익스트라 알고리즘이 있는데, 다익스트라 알고리즘은 최단 경로를 구하는 알고리즘으로 가장 작은 값을 계속해서 계산해 나가는 알고리즘이다. 이 문제도 마찬가지로 항상 intensity가 가장 작은 값을 가지고 있으면서 만약 intensity가 같다면 mountain의 번호가 가장 작은 경로를 먼저 계산하면 편하다. 여기서 위 그림과 같이 S에서 시작을 한다.. 2024. 3. 7.
[프로그래머스/C++] 숫자 타자 대회 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때, 단순히 그리디로 풀 수 있나? 고민을 했다. 하지만 어떤 손가락을 움직일지 선택을 하기 위해서는 뒤에 오는 숫자들에 규칙같은게 있어야 하는데, 없기 때문에 그리디로 풀면 안된다는 결론이 나왔다. 그래서 생각한 방법은 탐색이었는데, 탐색도 그냥 하기에는 너무 많기 때문에 DP로 문제를 해결했다. 손가락 위치를 기준으로 특정 숫자를 입력할 때, 내 손가락의 위치를 기록한 vector가 있다면, 최악의 경우 100,000*10*10으로 문제가 해결되기 때문이다. 그리고 특정 번호에서 다른 번호로 이동해서 누르는 경우의 가중치를 쉽게 계산하기 위해 계산을 도와줄 2차원 vector를 만들었다... 2024. 3. 6.
[프로그래머스/C++] 기지국 설치 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 조금만 생각하면 쉽게 풀 수 있는 문제다. 아래 그림을 참고해 보자 여기서 기지국을 어떻게 설치해야 할까? 이미 설치된 기지국의 범위와 새로 설치하는 기지국의 범위가 같다는 점에 유의하면 기지국을 최소로 설치하기 위해서는 기지국이 설치되지 않은 연속된 칸을 기지국의 범위로 나누면 쉽게 해결할 수 있다. 그림에서 보이듯이 기지국을 설치할 때 차지하는 칸의 범위가 3이라면 1~2 범위는 크기가 2이므로 기지국을 하나 설치해서 그 범위를 메꿀 수 있다. 다음 범위는 6~9의 범위를 메꿔야 하는데, 범위의 크기가 4이므로 기지국을 2개 설치해야 메꿀 수 있다. 이처럼 연속으로 비어있는 부분의 크기를 기지국의 .. 2024. 3. 5.
[프로그래머스/C++] 억억단을 외우자 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 이 문제를 봤을 때, 최악의 경우 5000000을 1~5000000 사이의 수로 나누어 보면서 개수를 세는 문제인가 생각이 들었다. 하지만 이 경우 N^2이 되기 때문에 불가능 했다. [첫 번째 풀이] 그래서 생각한 아이디어는 결국 곱셈해서 특정한 수가 나온다는 것은 약수의 개수와 같기 때문에 소인수 분해를 이용해 푸는 방법이었다. 여기에 e에 대한 수들을 전부 계산할 필요 없이 e/2까지만 계산하면 된다는 생각이 들었다. (e/2이하의 숫자라면 2를 곱해서 약수의 수가 더 많은 수를 만들 수 있기 때문이다.) 그러므로 최악의 경우 2500000*(logN 이하의 소수의 개수)로 문제가 해결 될 것이라고 .. 2024. 3. 5.
반응형

티스토리툴바