본문 바로가기
반응형

C++246

[프로그래머스/C++] 고고학 최고의 발견 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때 어떻게 풀어야 할지 오래 고민했다. 열쇠의 모양이 십자 모양이기 때문에 맨 위 부분만 파악할 수 있으면 쉽게 풀 수 있지만, 열쇠의 정 중앙이 성궤의 테두리에 놓일 수 있기 때문이었다. 그렇게 고민하던 중 다른 사람의 힌트를 봤고, 모든 경우를 전부 탐색할 필요는 없이 첫 줄만 결정하면 된다는 것이었다. 맨 위 부분만 판단하면 되는 이유는 위 그림을 보면 알 수 있다. 양 옆에 다른 열쇠 조각에 영향을 끼치는 부분은 가운데 줄에 위치해야만 가능하다. 그렇기 때문에 남은 조각을 탐색했을 때, 맨 위 조각이 12시가 아닌 상태라면 무조건 그 아래에 있는 부분을 돌려 12시를 맞춰야 하기 때문.. 2024. 3. 23.
[프로그래머스/C++] 캠핑 (2017 카카오코드 예선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제에서 중요한 점은 두 쐐기로 직사각형을 만들었을 때, 그 안에 다른 쐐기가 없어야 한다는 점이다. 단순히 두 쐐기를 정하고 다른 쐐기가 안에 있는지 센다면, 시간복잡도가 O(n^3)으로 매우 커지게 된다. 하지만, 정렬을 잘 한다면 O(n^2)으로도 쉽게 풀 수 있는 문제다. 한번 쐐기의 데이터들을 그림으로 생각해 보자 세로 축을 y, 가로 축을 x라고 하면, 쐐기들의 정보를 y축, x축의 순서로 오름차순 정렬을 한다. 그러면 위 그림과 같이 쐐기들의 순서가 정렬이 될 것이다. 이제 1번 쐐기부터 탐색을 시작한다. 1번 쐐기와 연결할 수 있는 쐐기들은 2~7번 쐐기다. 여기서 2, 3번 쐐기는 1번 쐐기와.. 2024. 3. 22.
[프로그래머스/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++] 미로 탈출 명령어 (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 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 수열의 회전에 관한 문제다. 문제의 내용을 보면 수열을 이동하는 쿼리와 수열의 특정 범위의 합을 묻는 쿼리에 대해 답을 출력하는 문제다. 여기서 특정 범위의 합은 매번 계산하기보다 누적합을 이용하면 한번의 계산으로 답을 출력할 수 있다. 수열의 이동은 원순열을 생각하면 편하다. (한쪽 끝으로 이동하다가 범위를 넘어서면 반대쪽으로 넘어간다) 먼저 처음에 시작 index를 정한다. 이제 수열의 시작 부분이 k만큼 증가하면 이는 시작 index가 오른쪽으로 이동한 것과 같다. 만약 시작 부분이 k만큼 감소하면 이는 시작 index가 왼쪽으로 이동한 것과 같다. 여기서 합을 구하는 범위가 N을 넘어가지 않기 .. 2024. 3. 12.
[프로그래머스/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.
반응형

티스토리툴바