난이도 : 골드 4 걸린 시간 : 1시간 반 이상 문제 문제 바로가기 풀이 우선 완전탐색으로 해당 문제를 생각해본다. 완전탐색으로 구현한다면 dfs를 사용해서 재귀로 구현할 것이다. 재귀의 매개변수(받는 정보)는 현재 위치일 것이고, 내보내는 정보는 현재 위치에서 마지막까지의 경로의 수일 것이다. (0,0)을 처음으로 재귀함수에 넘기면 (0,0)에서 끝까지의 경로의 수이므로 우리가 원하는 답이 나온다. 재귀는 위, 오른쪽, 아래, 왼쪽으로 접한 부분으로 옮겨가며 해당 장소의 경로의 수를 현재 장소의 경로의 수에 더하는 방식으로 진행된다. 이 때, 장소는 맵 안에 있어야한다. 이 때, 내리막길로만 갈 수 있으므로 현재보다 더 높은 수를 가진 장소는 제외이다. 이렇게 구성하면 갔던 곳을 또 가는 경우가 생기..

난이도 : 골드 5 걸린 시간 : 1시간 반 이상 문제 문제 바로가기 오답 처음에 완전탐색으로 하되 최대한 조합의 범위를 줄여서 구현해보았다. 하지만, 시간 초과로 실패..! #include #include #include #include using namespace std; // 6시 4분 시작 => 6시 42분 중단, 11시 12분 시작 => // N > K; for (int i = 0; i > w >> v; vec.push_back(make_pair(w, v)); } // 무게 순 정렬 sort(vec.begin(), vec.end(), compare); // 무게는 같은데 가치가 작은 것은 없애기 for (int i = 1; i < vec.size(..

난이도 : 골드 3 걸린 시간 : 50분 문제 문제 바로가기 풀이 처음에 풀이를 이상하게 생각해서 O(n^3)의 완전탐색 혹은 DP를 사용하는 법을 생각하고 있었다. 그러다가 생각을 다시 해보니 쉽게 풀 수 있는 방법이 있어 20분만에 풀게 되었다. 역시 처음에 풀이를 주석으로 쭉 적어본 후 예제를 테스트 해보고 수행하는 것이 제일 정확하고 알맞은 방법인 듯 하다. 입력의 범위는 10^3로 그다지 높은 편은 아니었지만, 완전탐색 시 O(n^3)이 걸리므로 충분히 시간초과가 나올 수 있는 범위였다. 또한 각 숫자의 범위도 최대 10^3이므로 숫자를 하나씩 내려가며 / 올려가며 푸는 완전탐색 또한 불가능했다. 예제의 힌트를 보니 연속적이지 않은 수열의 흐름도 가능했고, 그렇다면 각 숫자가 보유하고 있는 ma..

합승 택시 요금 난이도 : ★★★☆☆ 걸린 시간 : 못 풀었음 문제 합승 택시 요금 링크 해설 그래프 최단 경로 알고리즘 dijkstra나 floyd-warshal 알고리즘 이용 플로이드 와샬 알고리즘 모든 정점 => 모든 정점 최단 경로 구하기 d[i][j] = i부터 j까지의 최저 택시 요금 min(d[s][k]+d[k][a]+d[k][b])를 구하면 됨 다익스트라 알고리즘 한 정점 => 모든 정점 최단 경로 구하기 배열(dist)과 우선순위 큐(qp)를 이용해서 첫 정점부터 각 노드까지의 거리를 배열에 업데이트하는 방식 우선순위 큐에 다음 갈 수 있는 노드들을 넣으면서 해당 거리를 dist 배열에서 갱신하는 방식 a, b 각각의 최단 거리 비용과 특정 지점까지의 최단 거리 비용 중 가장 작은 것을 ..

메뉴 리뉴얼 난이도 : ★★☆☆☆ 걸린 시간 : 50분 문제 메뉴 리뉴얼 문제 바로가기 문제 설명 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 새로운 메뉴를 제공하기로 결정했습니다. 어떤 단품메뉴들을 조합해서 코스요리 메뉴로 구성하면 좋을 지 고민하던 스카피는 이전에 각 손님들이 주문할 때 가장 많이 함께 주문한 단품메뉴들을 코스요리 메뉴로 구성하기로 했습니다. 단, 코스요리 메뉴는 최소 2가지 이상의 단품메뉴로 구성하려고 합니다. 또한, 최소 2명 이상의 손님으로부터 주문된 단품메뉴 조합에 대해서만 코스요리 메뉴 후보에 포함하기로 했습니다. 예를 들어, 손님 6명이 주..

신규 아이디 추천 난이도 : ★☆☆☆☆ 걸린 시간 : 30분 => 반성! 문제 신규 아이디 추천 문제 바로가기 문제 설명 카카오에 입사한 신입 개발자 네오는 카카오계정개발팀에 배치되어, 카카오 서비스에 가입하는 유저들의 아이디를 생성하는 업무를 담당하게 되었습니다. 네오에게 주어진 첫 업무는 새로 가입하는 유저들이 카카오 아이디 규칙에 맞지 않는 아이디를 입력했을 때, 입력된 아이디와 유사하면서 규칙에 맞는 아이디를 추천해주는 프로그램을 개발하는 것입니다. 다음은 카카오 아이디의 규칙입니다. 아이디의 길이는 3자 이상 15자 이하여야 합니다. 아이디는 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.) 문자만 사용할 수 있습니다. 단, 마침표(.)는 처음과 끝에 사용할 수 없으며 또한 연속으로 ..

매칭 점수 걸린 시간 : 3시간 이상 문제 난이도 ★★★☆☆ 문제 설명 프렌즈 대학교 조교였던 제이지는 허드렛일만 시키는 네오 학과장님의 마수에서 벗어나, 카카오에 입사하게 되었다. 평소에 관심있어하던 검색에 마침 결원이 발생하여, 검색개발팀에 편입될 수 있었고, 대망의 첫 프로젝트를 맡게 되었다. 그 프로젝트는 검색어에 가장 잘 맞는 웹페이지를 보여주기 위해 아래와 같은 규칙으로 검색어에 대한 웹페이지의 매칭점수를 계산 하는 것이었다. 한 웹페이지에 대해서 기본점수, 외부 링크 수, 링크점수, 그리고 매칭점수를 구할 수 있다. 한 웹페이지의 기본점수는 해당 웹페이지의 텍스트 중, 검색어가 등장하는 횟수이다. (대소문자 무시) 한 웹페이지의 외부 링크 수는 해당 웹페이지에서 다른 외부 페이지로 연결된 링..

길 찾기 게임 ★★★☆☆ LEVEL 3 문제 길 찾기 게임 문제 링크 문제 설명 전무로 승진한 라이언은 기분이 너무 좋아 프렌즈를 이끌고 특별 휴가를 가기로 했다. 내친김에 여행 계획까지 구상하던 라이언은 재미있는 게임을 생각해냈고 역시 전무로 승진할만한 인재라고 스스로에게 감탄했다. 라이언이 구상한(그리고 아마도 라이언만 즐거울만한) 게임은, 카카오 프렌즈를 두 팀으로 나누고, 각 팀이 같은 곳을 다른 순서로 방문하도록 해서 먼저 순회를 마친 팀이 승리하는 것이다. 그냥 지도를 주고 게임을 시작하면 재미가 덜해지므로, 라이언은 방문할 곳의 2차원 좌표 값을 구하고 각 장소를 이진트리의 노드가 되도록 구성한 후, 순회 방법을 힌트로 주어 각 팀이 스스로 경로를 찾도록 할 계획이다. 라이언은 아래와 같은 ..