본문 바로가기
  • 실행력이 모든걸 결정한다
반응형

Algorithm143

[시뮬레이션] 오픈채팅장 - 2019 카카오 블라인드 채용 해결 방법 문제를 보면, 유저가 중간에 닉네임을 변경했을 경우에도 이전에 기록했던 닉네임들까지 변경된 닉네임으로 바뀐다고 한다. 즉, 유저별 마지막 닉네임이 가장 중요하다. 유저의 닉네임이 바뀌는 경우는 Enter과 Change이므로, 이 경우에만 유저의 닉네임을 업데이트 해주면 된다. 유저별 마지막 닉네임을 확정지었다면, 유저의 마지막 닉네임이 반영된 로그를 출력해주기만 하면 된다. 소스 코드 #include #include #include #include using namespace std; map m; vector log[100001]; vector space; string str, action, uid; vector solution(vector record) { vector answer; for .. 2022. 3. 5.
[문자열] 문자열 압축 - 2020 카카오 블라인드 채용 주의할 점 이 문제를 이해할 때 놓치기 쉬운 포인트가 있는데, 문자열을 제일 앞부터 고정된 길이만큼 잘라야 하는 것이다. 즉, "ababcdcdababcdcd" 문자열을 2개 단위로 자르려면 다음과 같이 잘라야 하는 것이다. -> ab/ab/cd/cd/ab/ab/cd/cd 필자는 이 조건을 놓친 덕에 총 2문제를 풀게 되었다. 이 조건 없는게 더 압축 효율이 좋을텐데... 어쨌든, 문자열을 제일 앞부터 자르지 않아도 되는 경우에 해당하는 소스코드는 맨 아래에 첨부하였다. 해결 방법 본 문제로 넘어가서, 필자는 다음과 같은 방법으로 문제를 해결했다. 문자열을 1개 단위부터 s.length()/2개 단위까지 자른 모든 경우를 따져봐서, 압축된 각 문자열들의 최솟값을 구했다. 그리고, 문자열을 a개 단위로 자.. 2022. 3. 4.
[이분 매칭, 난이도 중] 백준 11375번, 열혈강호 이분 매칭 알고리즘이란? 이분 매칭 알고리즘은 선택하는 집단과 선택되는 집단이 있을 때, 두 집단 사이의 매칭 수가 최대가 되도록 하는 것이 목적인 알고리즘이다. 이분 매칭 알고리즘의 기본 원리 사람 A, B와 과일 X, Y, Z가 있는데, 한 사람당 하나의 과일만 먹을 수 있다고 가정하자. 사람 A는 모든 과일을 좋아해서 과일 X, Y, Z 모두를 선호하는 반면, 사람 B는 입맛이 까다로워서 과일 X만 선호한다. 초기 상태에서는 과일 X, Y, Z는 아무에게도 선택되지 않았다. 먼저, A가 선호하는 첫 번째 과일인 X를 매칭한다. 그 다음 B가 선호하는 첫 번째 과일인 X를 매칭하려고 하니 X는 A에 의해 이미 선택되어 있다. 그래서 B는 X를 선택한 A에게 이렇게 묻는다. "A님, 가능하다면 다른 과.. 2022. 3. 4.
이분탐색 고득점 kit 풀이 완료, 후기 이분탐색 알고리즘은 두 가지 선택지(true/false) 중에서 하나를 판단하고 범위를 좁혀 나가서 효율적으로 정답을 찾는 알고리즘이다. 이 알고리즘의 응용으로 1부터 10억까지 숫자중 상대방이 고른 숫자를 yes or no 문답 식으로 약 30번의 질문안으로 맞힐 수도 있을 정도로 매우 효율적인 알고리즘이다. 이분탐색 알고리즘을 프로그래머즈에서 처음 접해봐서 그런지 2개의 문제들은 모두 쉽지 않았다. 접근법을 떠올리는건 동적계획법, 그리디 알고리즘보다 다소 어려웠지만 매우 재미있는 알고리즘인 것 같다. 이 문제들을 풀면서 이분탐색 기법으로 어떻게 접근하는지 충분히 감을 익힐 수 있었다. 제일 먼저 할 일은 정답이라고 가정할 적당한 값을 세우는 것인데, 보통 정답이 될 수 있는 범위의 중간값으로 세우게 .. 2020. 11. 5.
[이분 탐색, 난이도 상] 프로그래머즈, 징검다리 출발지점부터 도착지점 사이에 놓여져 있는 돌들 중에서 n개를 뺀 상태의 모든 경우에서, 각 지점 사이의 거리들의 최솟값들중 가장 큰 값을 구하면 되는 문제이다. rocks의 순서는 뒤죽박죽 하기 때문에 오름차순으로 정렬해주고 시작해야 한다. 우리가 구해야 하는 답(바위를 n개 제거한 뒤 각 지점 사이의 거리의 최솟값 중 가장 큰 값) 을 미리 적당한 값으로 세워두고, 실제 정답이 미리 세워둔 값보다 큰지 작은지 판단하고 범위를 좁혀 나가면 된다. 바위를 몇개 제거해야 미리 세워둔 답이 실제 정답이 될 수 있는지 계산하는 것이 핵심이다. 그 바위 수는 n개가 나와야 하는 것이다. 입출력 예를 예로 들어보자. 정렬된 바위의 배치 -> [2,11,14,17,21] 각 지점 사이의 거리 (시작점, 도착점도 지점.. 2020. 11. 5.
[DFS, 난이도 중] 프로그래머즈, 쿼드압축 후 개수 세기 전체 영역을 4분할 한뒤 분할 영역 안의 요소가 모두 같을 경우에는 압축하고, 그렇지 않을 경우에는 분할 영역을 다시 4분할해가는 식으로 진행한다. 이 방식으로 모두 압축했을 때 남아있는 0,1의 개수를 계산하면 되는 문제이다. 자세한 설명은 맨 아래 첨부한 코드의 주석에 달아놓았다. dfs함수를 수행하기 전에 전체 영역에 대해 요소가 모두 같은지 여부를 알아내야 한다. 그 이유는 dfs함수에서는 영역을 4분할 하고 계산하기 때문에, 전체 영역을 바로 넣어버리면 전체 영역에 대해 요소가 모두 같더라도 강제로 4분할이 되어 버린다. 이러한 과정이 없다면, [[1,1],[1,1]] 이 입력으로 주어지더라도 출력값은 [0,1]이 아닌 [0,4]가 되어버릴 것이다. 테스트 케이스 16개 모두 통과 #includ.. 2020. 10. 19.
[동적계획법, 난이도 중하] 백준 11054번, 가장 긴 바이토닉 부분 수열 백준 11053번 가장 긴 증가하는 수열 문제를 응용한 문제이다. [동적계획법, 난이도 중] 백준 11053번 가장 긴 증가하는 부분 수열 제한 시간은 1초며, N의 범위가 (1 ≤ N ≤ 1,000) 으로 좁은 편이기 때문에 O(N^2) 까지 쓸 수 있다. 그래도 이 문제는 1차원 배열의 DP로 풀 수 있다. 첫 INPUT에 대한 DP의 첫 인덱스 값을 1로 두며 시작�� kimcoder.tistory.com 가장 긴 증가하는 수열을 정방향, 역방향 2번 계산하여 해결할 수 있는데 계산 과정은 위 포스팅에 자세히 설명해놨으므로 이 포스팅에선 설명을 따로 하지 않을 것이다. 아래에 예제 입력1 계산표에서 Up행은 가장 긴 증가하는 수열을 적용한 DP이고, Down행은 가장 긴 감소하는 수열을 적용한 DP.. 2020. 10. 12.
[이분 탐색, 난이도 중] 프로그래머즈, 입국심사 이 문제는 시간 복잡도 O(n)도 통하지 않는다. 인구 수, 심사 시간 데이터 범위가 10억이기 때문에 이분 탐색을 적용해야 하는 변수는 이 둘중 하나임을 알 수 있다. 이분 탐색 알고리즘은 IT계열의 대학교에서 대부분 1학년때 배울 것이다. "1000개의 수중 하나를 선택했을 때 10번 이내의 yes or no 질문으로 선택한 수를 찾을 수 있다" 이런 기초적인 예시로 많이 배웠을거라 생각이 든다. 여기서 핵심은 탐색 조건은 yes or no라는 것이다. 이분 탐색은 중간값을 기준으로 찾으려는 값이 큰가 or 작은가로 판단하여 탐색이 이루어진다. 찾으려는 값이 크다면 첫 번째 값~ 중간 값 까지는 찾으려는 수가 없다는 의미이고, 찾으려는 값이 작다면 중간 값~ 마지막 값 까지는 찾으려는 수가 없다는 의.. 2020. 10. 8.
힙(Heap) 고득점 kit 풀이 완료, 후기 힙으로 우선순위 큐를 구현한다면, 삽입과 삭제가 모두 O(logn)으로 이루어진다. 시간복잡도 계산 시 logn은 거의 상수로 봐도 무방할 정도다. 완전히 상수는 아니지만 n과 비교해도 엄청난 차이임을 알 수 있다. 삽입, 삭제가 원활하게 이루어져야 하는 프로그램에서는 힙구조 우선순위 큐를 이용하면 매우 좋다. C++에서 priority_queue 라이브러리를 사용하는 방법에 대해 포스팅해둔 글이 있으니 참고하면 좋을 것이다. 구조체의 특정 요소(변수)를 기준으로 우선순위를 정하는 방법도 같이 설명해두었다. kimcoder.tistory.com/110?category=887628 삽입, 삭제 모두 O(logn)!! STL priority_queue 소개 priority_queue는 큐에 데이터가 삽입, .. 2020. 10. 8.

티스토리툴바