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

Algorithm143

[완전탐색] 카드 짝 맞추기 - 2021 KAKAO BLIND RECRUITMENT 해결 방법 필자는 DFS와 BFS를 기반으로 완전탐색을 이용해서 해결했다. BFS를 통해 현재 커서로부터 각 칸까지 이동할 때 필요한 최소 키 조작 횟수를 구했다. 예를 들어, 입출력 예 #1에서 최초로 실행되는 BFS 결과는 다음과 같다. 1칸 이동, 일괄 이동의 경우를 모두 반영했다. 그리고 DFS에서는 뒤집혀 있는 카드의 상태에 따라 동작 방식이 다르다. 소스 코드에서는 뒤집혀 있는 카드의 상태를 state 변수에 저장했다. state가 0인 경우에는 어떠한 카드도 뒤집혀 있지 않은 상태고, state가 0이 아닌 경우에는 뒤집혀 있는 카드의 번호가 저장되어 있다. DFS는 다음과 같이 동작한다. state==0 : 현재 뒤집힌 카드가 없다면 남아있는 모든 카드를 한 번씩은 뒤집어본다. state!.. 2022. 11. 2.
[완전탐색] 양궁대회 - 2022 KAKAO BLIND RECRUITMENT 해결 방법 화살을 쏴서 얻을 수 있는 점수로는 총 11가지(0점부터 10점) 경우가 있기 때문에, n개의 화살이 11가지 경우에 분배되는 모든 경우를 따지면 된다. 과녁에 있는 하나의 원에 여러 화살이 꽂힐 수도 있으므로 중복 조합(H)을 구하면 된다. 예를 들어, 입출력 예 #1 에서는 11H5=3003 가지 경우를 따지면 된다. 중복 조합을 구하는 소스 코드는 https://hydroponicglass.tistory.com/20를 참고했다. 중복 조합으로 계산한 모든 경우에 대해 어피치와의 점수 차이를 구하고 문제에 안내된 대로 동일 점수에 대한 처리도 진행해주면 된다. 소스 코드 #include #include #include using namespace std; vector perm; // 중복 .. 2022. 10. 18.
[DFS] 양과 늑대 - 2022 KAKAO BLIND RECRUITMENT 해결 방법 사실상 모든 경로를 다 따져봐야 하는 문제다. 물론, 양과 늑대의 수가 같아지는 시점부터는 해당 경로에 대한 dfs는 중단해야 한다. 필자는 현재까지의 방문 노드들을 하나의 통합 노드로 두고, 통합 노드의 인접 노드들을 하나씩 방문해나가는 방법으로 해결했다. 시작 정점에서 정점을 추가해가며 단계적으로 트리를 확장한다는 접근법만 놓고 보면 프림 알고리즘과 비슷한 느낌이 들지 않는가? 물론 간선의 비용도 없고 dfs이기 때문에 방문을 취소해야 할 때가 있다는 차이점이 있기는 하다. 인접노드를 방문했을 때 양과 늑대의 수가 같아지거나 더 이상 방문할 노드가 없다면 해당 경로에 대한 dfs를 중단하면서 방문도 취소해주면 된다. 소스 코드 #include using namespace std; vecto.. 2022. 10. 14.
[구간합] 광고 삽입 - 2021 KAKAO BLIND RECRUITMENT 해결 방법 필자는 초 단위로 누적 재생시간에 대한 구간합을 구해서 해결했다. 최대 재생 시간은 359999초이기 때문에 O(N)의 시간복잡도 정도는 부담스럽지 않다. 이렇게 구간합을 구해두면 [0, adv_time) 구간부터 [play_time - adv_time, play_time)에 대한 모든 구간합을 구하는데 O(N)의 시간복잡도로 해결할 수 있다. 그리고 "hh:mm:ss" 문자열 형식으로 표현된 시간을 초 단위의 정수로 변환하는 함수와 초 단위의 정수를 "hh:mm:ss" 문자열 형식으로 변환하는 함수를 추가해서 손 쉽게 시간을 계산할 수 있도록 했다. 소스 코드 #include #include using namespace std; #define MAX 360000 int dup[MAX]; //.. 2022. 10. 11.
[구현] 순위 검색 - 2021 KAKAO BLIND RECRUITMENT 해결 방법 정확성 테스트라면 어렵지 않게 통과할 수 있을 것이지만, info, query 벡터에 대해 그대로 2중 for문을 쓴다면 효율성에서 좋은 점수를 받지 못할 것이다. 필자는 다음과 같이 4차원 벡터를 선언했다. vector iv[4][3][3][3]; 개발언어 항목, 지원 직군 항목, 경력구분 항목, 소울 푸드에 있는 각 정보를 차례대로 정수로 나타내어서 저장하기 위해 4차원 형태로 만들었다. cpp/java/python/- backend/frontend/- junior/senior/- chicken/pizza/- '-' 부분에는 나머지 조건에 해당 하는 모든 경우를 넣어주면 된다. 조건이 4개이기 때문에 하나의 조건이라도 반영하지 않는 경우의 수는 15(4C1+4C2+4C3+4C4=15)가 될.. 2022. 10. 7.
[구간합] 파괴되지 않은 건물 - 2022 KAKAO BLIND RECRUITMENT 해결 방법 정확성 테스트라면 어렵지 않게 통과할 수 있을 것이지만, 2차원 누적합 알고리즘을 사용하지 않는다면 효율성 테스트에서 통과하기 힘들 것이다. 필자는 데미지 범위를 나타내는 벡터와 데미지를 나타내는 벡터 총 2개의 벡터를 만들어서 해결했다. 입출력 예 #1를 기반으로 해결 방법을 설명해보겠다. 데미지 범위 벡터(damage_pos) 먼저, 데미지 범위 벡터의 모든 요소는 0으로 초기화해둔다. (r1, c1)부터 (r2, c2)까지 degree 만큼의 공격을 받았다고 해보자. 이 때는 damage_pos의 (r1, c1), (r2+1, c2+1)에는 degree만큼 빼주고, (r1, c2+1), (r2+1, c1)에는 degree만큼 더해준다. 이를 그림으로 나타내면 다음과 같다. 회색 부분은 (.. 2022. 10. 4.
[구간합] 두 큐 합 같게 만들기 - 2022 KAKAO TECH INTERNSHIP 해결 방법 입출력 예 #1를 이용하여 해결 방법을 설명해보겠다. 필자는 2개의 큐를 각각 다른 순서로 결합한 2개의 벡터를 만들어놓고 구간합을 이용해서 해결했다. 2개의 결합 벡터를 만든 이유는 모든 구간합을 편하게 계산하기 위함이다. 2개의 결합 벡터는 다음과 같다. 그리고 각 큐의 합은 두 큐의 합의 1/2이어야 하기 때문에 구간합이 15인 구간을 따로 선정했다. 각 결합 벡터에 대한 누적합 벡터를 따로 만들어서 이 누적합 벡터에 투포인트 알고리즘을 적용해서 구간합을 구하는 것이 효율적이다. 이제 특정 구간합만 왼쪽 큐에 모을 수 있게 해보자. 큐의 원소는 한쪽으로만 들어오고 다른 한쪽으로만 나간다는 특성을 이용해서 들어오는 원소의 개수와 나가는 원소의 개수를 합하기만 하면 작업 횟수를 구할 수 있다.. 2022. 9. 30.
[Graph] 합승 택시 요금 - 2021 KAKAO BLIND RECRUITMENT 해결 방법 처음엔 BFS+DP로 시도해보았는데 시간초과가 나서 결국은 플로이드 와샬(Floyd Warshall) 알고리즘으로 해결했다. 플로이드 와샬 알고리즘은 각 정점끼리의 모든 최단 경로를 구해야할 때 사용되는 알고리즘이며, 구현하기 매우 쉽다는 장점이 있다. 자세한 동작을 알고싶다면 나동빈님의 블로그를 참고하길 바란다. https://blog.naver.com/ndb796/221234427842 24. 플로이드 와샬(Floyd Warshall) 알고리즘 지난 시간에는 다익스트라(Dijkstra) 알고리즘에 대해 학습했습니다. 다익스트라 알고리즘은 하나의 정점... blog.naver.com 소스 코드 #include #include using namespace std; int min_fare[201.. 2022. 9. 28.
[완전탐색] 메뉴 리뉴얼 - 2021 KAKAO BLIND RECRUITMENT 해결 방법 단품 메뉴 조합에서 2개 이상을 고른 모든 조합을 모두 추출하고, 나타난 조합의 빈도를 계산하면 된다. map을 이용하면 이를 쉽게 계산할 수 있을 것이다. 의 next_permutation() 함수를 이용하면 간단하게 모든 조합을 구할 수 있다. 사용 방법은 아래 포스팅을 참고하길 바란다. https://kimcoder.tistory.com/118 next_permutation을 이용한 조합 구현 #include #include #include #include using namespace std; vector arr; vector check; void set_check(int n, int r){ for(int i=0;i next_permutation 함수는 배열을 순열해주는 함수이다. 일반적.. 2022. 9. 23.

티스토리툴바