본문 바로가기
반응형

Algorithm292

[프로그래머스/C++] 가사 검색 (2020 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 처음 이 문제를 봤을 때 trie 알고리즘을 사용하면 빨리 문제를 해결할 수 있겠다는 생각이 들었다. 왜냐하면 특정 문자가 같은지 비교하고 수를 세는 과정에서 trie 알고리즘을 사용하면 빠르게 해결 될 것 같았기 때문이다. 문제는 조건을 제대로 안읽어서 ab?cd와 같이 중간에 ?가 들어갈 수 있는 줄 알고 코드를 구현했다. 하지만 알고보니 양 끝에만 ?가 연속적으로 들어갈 수 있었다... [문제 풀이] trie 알고리즘으로 문제를 푼 방법은 다음과 같다. 예를 들어 trie라는 문자가 들어온다고 가정하자. 이 경우 위 그림과 같이 t 뒤에는 물음표가 3개 오는 경우가 올 수 있다. 이를 map를 이용해 [문자열의 길이: 개.. 2024. 3. 27.
[프로그래머스/C++] 표 병합 (2023 KAKAO BLIND RECRUITMENT) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 표 병합 문제에서 중요한 명령어는 MERGE와 UNMERGE다. 다른 명령어들은 vector를 이용하면 바로 수행할 수 있지만, MERGE나 UNMERGE된 셀일 수 있기 때문에 이를 파악하는게 중요하다. 이 문제를 풀기 위해 union-find 알고리즘을 이용했다. 예를 들어 (1, 1) 셀과 (2, 2) 셀이 병합 되었다고 가정하자. 이 경우 (2, 2) 셀은 (1, 1)셀의 집합에 포함되어 있다고 표시를 한다면, (2, 2)셀의 값을 업데이트 하거나 변경할 경우 (2, 2)셀의 집합의 값을 변경하면 문제가 해결된다. UNMERGE는 반대로 한 집합에 속한 모든 원소들을 초기화 시키고 마지막에 명령어에 있는 .. 2024. 3. 26.
[프로그래머스/C++] 징검다리 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음에 생각 났던 풀이는 가장 짧은 거리를 찾은 다음 어떤 돌을 제거할지 선택하는 방법이다. 하지만 이 방법은 최악의 경우 시간복잡도가 O(N^2)이 되기 때문에 다른 방법을 생각했다. 그러다가 바위 사이의 최소 거리를 정한 다음 돌을 몇 개 제거해야 하는지 계산하면 더 빠르게 연산이 될 것이라는 생각이 들었다. 여기서 바위 사이의 최대 거리는 도착점까지의 거리이므로 min Distance = 1, max Distance = 도착점까지의 거리로 이분탐색을 하도록 코드를 구현했다. 예를 들어 돌 사이의 최소 거리가 4라고 하면, 돌 A와 돌 B 사이의 거리는 최소 거리인 4보다 커야한다. 만약 돌 A, B 사이의 .. 2024. 3. 25.
[프로그래머스/C++] 몸짱 트레이너 라이언의 고민 (2017 카카오코드 본선) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때, 규칙을 찾아보려고 생각했다. 규칙을 찾을 경우 인원이 최대 몇명 겹치는지 알면 쉽게 풀 수 있을 것 같았기 때문이었다. 인원이 최대 몇명 겹치는지를 계산하기 위해서 운동 시작시간을 기준으로 정렬을 한다. 운동이 끝나는 시간을 pq에 삽입하고, pq에 들어있는 시간이 다른 사람의 운동 시작 시간보다 빠르다면 그 사람은 운동이 끝났으므로 pq에서 빼준다. 이때 pq의 크기가 max인 경우가 최대 사람 수다. 하지만, 2명인 경우와 사람의 수가 n*n/2+n%2 보다 큰 경우를 빼고는 규칙을 찾기 힘들었다. 그래서 다음으로 생각한 풀이는 2명 이상일 경우에 최대 거리가 2*(n-1)이하로 나.. 2024. 3. 24.
[프로그래머스/C++] 고고학 최고의 발견 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 처음 이 문제를 봤을 때 어떻게 풀어야 할지 오래 고민했다. 열쇠의 모양이 십자 모양이기 때문에 맨 위 부분만 파악할 수 있으면 쉽게 풀 수 있지만, 열쇠의 정 중앙이 성궤의 테두리에 놓일 수 있기 때문이었다. 그렇게 고민하던 중 다른 사람의 힌트를 봤고, 모든 경우를 전부 탐색할 필요는 없이 첫 줄만 결정하면 된다는 것이었다. 맨 위 부분만 판단하면 되는 이유는 위 그림을 보면 알 수 있다. 양 옆에 다른 열쇠 조각에 영향을 끼치는 부분은 가운데 줄에 위치해야만 가능하다. 그렇기 때문에 남은 조각을 탐색했을 때, 맨 위 조각이 12시가 아닌 상태라면 무조건 그 아래에 있는 부분을 돌려 12시를 맞춰야 하기 때문.. 2024. 3. 23.
[프로그래머스/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 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제는 수열의 회전에 관한 문제다. 문제의 내용을 보면 수열을 이동하는 쿼리와 수열의 특정 범위의 합을 묻는 쿼리에 대해 답을 출력하는 문제다. 여기서 특정 범위의 합은 매번 계산하기보다 누적합을 이용하면 한번의 계산으로 답을 출력할 수 있다. 수열의 이동은 원순열을 생각하면 편하다. (한쪽 끝으로 이동하다가 범위를 넘어서면 반대쪽으로 넘어간다) 먼저 처음에 시작 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.
반응형

티스토리툴바