[Algorithm] 프로그래머스 - 2021 KAKAO BLIND RECRUITMENT 풀이

코딩테스트 연습 > 2021 KAKAO BLIND RECRUITMENT

신규 아이디 추천

programmers.co.kr/learn/courses/30/lessons/72410

코딩테스트 연습 - 신규 아이디 추천

 

시행착오

6단계에서 연산 후 . 문자열을 제거해야하는데, 문제를 꼼꼼히 읽지 않아서 시간을 좀 소모함.

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/String/Solutions/Programmers/%EC%8B%A0%EA%B7%9C%20%EC%95%84%EC%9D%B4%EB%94%94%20%EC%B6%94%EC%B2%9C.cpp

insooneelife/AlgorithmTutorial

 

메뉴 리뉴얼

programmers.co.kr/learn/courses/30/lessons/72411

코딩테스트 연습 - 메뉴 리뉴얼

 

문제풀이

모든 order 문자열에 대하여,

모든 course 개수만큼의 조합(부분 문자열)을 모두 생성한다.

생성된 부분 문자열을 카운팅한다.

course 에 맞게 최대로 카운팅 된 부분문자열들을 출력한다.

 

시행착오

조합 알고리즘을 직접 만들며 시간을 많이 소모함.

정답을 정렬해야하는 예외를 놓쳐서 시간을 조금 소모함.

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/BruteForce/Solutions/Programmers/%EB%A9%94%EB%89%B4%20%EB%A6%AC%EB%89%B4%EC%96%BC.cpp

insooneelife/AlgorithmTutorial

 

 

순위 검색

programmers.co.kr/learn/courses/30/lessons/72412

코딩테스트 연습 - 순위 검색

문제풀이

자료구조 차원에서 들어올 수 있는 query에 바로 대응할 수 있도록 테이블을 미리 다 생성해 둔다.

핵심적인 부분은 "-"에 대한 처리인데, 이 부분도 자료구조 차원에서 처리할 수 있도록 미리 저장해둔다. 

 

시행착오

문자열을 파싱하는 알고리즘을 직접 구현하면서 시간을 많이 소모함.

문자열 파싱에 있어서 STL의 istreamstream이 매우 효과적임.

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/Bitmask/Solutions/Programmers/%EC%88%9C%EC%9C%84%20%EA%B2%80%EC%83%89.cpp

insooneelife/AlgorithmTutorial

 

 

 

합승 택시 요금

 

programmers.co.kr/learn/courses/30/lessons/72413

코딩테스트 연습 - 합승 택시 요금

문제풀이

시작점 S

A의 도착위치 A

B의 도착위치 B

F(S -> A)는 S -> A 로 이동하는 최소 가중치 합

 

S에서 어떤 지점 X를 경유하여 A, B로 각각 갈라진다고 했을 때, 다음과 같이 경우를 나눌 수 있다.

X가 A일 경우

F(S -> A) + F(A -> B)

 

X가 B일 경우

F(S -> B) + F(B -> A)

 

그 외 모든 점 X

F(S ->X) + F(X -> A) + F(X -> B)

문제에서 원하는 최소경로는 위 모든 경우들의 최소값이다.

 

F(S -> X) 연산은 위 공식 속에서 N번 연산되기 때문에, 다익스트라 알고리즘을 이용한다면 시간초과가 날 것이다.

그러므로 플로이드 알고리즘을 통해 모든 정점쌍에 대한 최소가중치 합 테이블을 만들어,

F(S -> X)라는 쿼리에 O(1)로 동작하도록 하고, 위 공식을 구현한다.

 

시행착오

Overflow 예외를 예상하지 못하여 시간을 소모함.

플로이드와 같은 dp 계열 문제에서는 항상 overflow 예외를 의심하도록 하자.

 

소스코드

https://github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/ShortestPath/Solutions/Programmers/%ED%95%A9%EC%8A%B9%20%ED%83%9D%EC%8B%9C%20%EC%9A%94%EA%B8%88.cpp

insooneelife/AlgorithmTutorial

 

 

 

광고 삽입

programmers.co.kr/learn/courses/30/lessons/72414

코딩테스트 연습 - 광고 삽입

 

문제풀이

타임라인의 범위가 360000이기 때문에, 메모리를 이용해서 접근할 수 있다.

유저들의 시청시간은 구간으로 되어있기 때문에, 유저 수 만큼 for loop을 돌며 시청구간을 for loop로 타임라인에 누적하려고 하면 O(N^2)로 시간초과가 나게 된다. 

먼저 유저의 구간 시작위치를 1, 구간 끝 위치를 -1로 타임라인(psum)에 더해준다.

그 후 다음 코드를 실행하면 마법처럼 모든 유저의 누적시청구간이 만들어진다.

for (int i = 1; i < play_time_sec; ++i)
{
    psum[i] += psum[i - 1];
}

그 후, 적절한 광고표시위치를 찾기 위해 가장 누적합이 큰 시청구간을 찾아야 하는데, 이것을 구현하기 위해서는 구간단위 누적합에 대한 쿼리를 많이 수행할 수 밖에 없다. 누적합에 대한 쿼리를 쉽게 수행하기 위해, 누적누적합을 psum에 만들고 psum[i] - psum[i - a] 라는 쿼리로 빠르게 누적합을 계산해낼 수 있다.

 

 

시행착오

구간합 처리에 있어서 배열의 한 원소가 갖는 의미는, 문제에서 언급하는 시간 구간과 대응시키기 위해 조금 헷갈리는 정의를 내릴 수 밖에 없다. 또한 그 과정에서 인덱스 차이로 자주 예외가 발생하기 때문에 엄밀하게 구분해야한다. 

그리고 이 문제도 합을 이용하는 문제이기 때문에, overflow 예외에 주의해야한다.

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/PartialSum/Solutions/Programmers/%EA%B4%91%EA%B3%A0%20%EC%82%BD%EC%9E%85.cpp

insooneelife/AlgorithmTutorial

 

 

 

 

카드 짝 맞추기

programmers.co.kr/learn/courses/30/lessons/72415

코딩테스트 연습 - 카드 짝 맞추기

 

문제풀이

게임의 전체 상태와 전체 액션을 기준으로 잡고 게임트리 탐색을 수행하면 게임의 완료지점까지의 깊이가 너무 깊기 때문에 시간초과를 피할 수 없다.

탐색의 깊이를 줄이기 위해 문제를 조금 더 분할하여 설계하여야 한다.

게임 내 카드는 반드시 한 종류에 2개씩 존재하기 때문에, 먼저 카드 탐색 순서를 미리 정해놓고 문제에 접근해보자.

먼저 게임 내 커서는 모든 임의의 위치에서 다른 임의의 위치로 움직일 수 있다. 그러므로 탐색을 무작위하게 수행하는 것 보다는, 카드에서 카드로 최대한 뒤집어 가며 접근하는 방법이 훨씬 빠를 것이다. (최적해 또한 이 안에 존재한다.)

 

1. 게임 내 총 6종류의 카드가 존재하므로, 6! 개의 카드탐색순서가 만들어질 것이다.

2. 순서가 정해진 상태에서 게임을 수행한다고 가정했을 때, 한 종류에 2개의 카드가 있기 때문에 종류 단위 뒤집기 순서가 다시 정해질 것이다. 예를 들어 A -> B -> C 순서로 카드를 탐색해야하는 경우, 실제로 뒤집기 위해 다음과 같은 경우의 순서들이 존재한다.

A1 -> A2 -> B1 -> B2 -> C1 -> C2

A1 -> A2 -> B1 -> B2 -> C2 -> C1

A1 -> A2 -> B2 -> B1 -> C1 -> C2

A1 -> A2 -> B2 -> B1 -> C2 -> C1

...

A2 -> A1 -> B2 -> B1 -> C2 -> C1

 

 

3. 카드탐색을 수행하는 경우 A2 -> A1과 같은 연산은 최단거리로 게임트리를 탐색하는 과정으로 BFS(A2 -> A1)과 같은 형태로 정의할 수 있다.

4. 총 연산량은 6! * 2^6 * BFS * 6 정도 될 것이다.

 

시행착오

카드 뒤집기 순서 배열을 만들기 위해 너무 복잡하게 돌아갔다.

카드 쌍에 대한 순서도 배열에 미리 만드려는 접근은 좋았지만, DFS 과정 중 combs에 추가만 두번 해주면 되는것을 굳이 탐색 과정을 복잡하게 해가며 만들 필요는 없었다.

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/StateSpaceSearch/Solutions/Programmers/%EC%B9%B4%EB%93%9C%20%EC%A7%9D%20%EB%A7%9E%EC%B6%94%EA%B8%B0.cpp

insooneelife/AlgorithmTutorial

 

 

 

매출 하락 최소화

programmers.co.kr/learn/courses/30/lessons/72416

코딩테스트 연습 - 매출 하락 최소화

 

문제풀이

이 문제는 모든 직원이 참석 or 불참이 가능하다. 그러므로 참석여부에 대한 공간을 최적해 인자에 추가한다.

어떤 직원 N이 불참했을때의 최적해를 F(N, 0) 라고 하자.

어떤 직원 N이 참여했을때의 최적해는 F(N, 1)가 될 것이다.

최적해 F를 부분 F들의 연산집합으로 재귀적 정의한다.

 

F(N, true) 는 본인이 참여했기 때문에 child들의 참여여부는 중요하지 않다.

참여여부는 참석 or 불참 중 최소인 선택으로, 모든 child의 최소들의 합으로 표현된다.

F(N, true) = sales[N] + sum all K (min(F(K, true), F(K, false)))    (K는 child)

F(N, false) 는 본인이 참여하지 않았기 때문에 child들 중 최소 한명은 참여해야 한다.

그러므로 순서대로 child중 한명씩 필참시키고, 나머지는 참여여부에 따른 최소를 선택하도록 하고,

그 모든 선택지들 중 최소를 선택하도록 한다.

F(N, false) = 

min all

F(1, true) + [sum all K (min(F(K, true), F(K, false)))  K = 1 제외]

F(2, true) + [sum all K (min(F(K, true), F(K, false)))  K = 2 제외]

...

F(N, true) + [sum all K (min(F(K, true), F(K, false)))  K = N 제외]

 

 

 

 

시행착오

불참의 경우, childs 중 최소 하나 이상의 참석자가 있도록 해야하는데, minimum을 통한 선택의 자유가 섞여있는 상태에서 그 점화식을 생각해내는게 조금 어려웠음.

 

소스코드

github.com/insooneelife/AlgorithmTutorial/blob/master/Algorithm/Sources/DP/Solutions/Programmers/%EB%A7%A4%EC%B6%9C%20%ED%95%98%EB%9D%BD%20%EC%B5%9C%EC%86%8C%ED%99%94.cpp

insooneelife/AlgorithmTutorial