문제 아맞다 우산 문제 바로가기 경재씨는 저녁 약속을 가기 전 챙기지 않은 물건들이 있는 지 확인하고 있다. 필요한 물건은 전부 챙긴 것 같았고 외출 후 돌아오는 길에 경재씨는 외쳤다. "아 맞다 우산!!!" 경재 씨는 매번 외출하고 나서야 어떤 물건을 집에 놓고 왔다는 것을 떠올릴 때마다 자책감에 시달리는 것이 너무 싫었다. 외출이 잦은 경재 씨는 반복되는 일을 근절하기 위해 꼭 챙겨야 할 물건들을 정리해보았다. 하지만 지갑, 스마트폰, 우산, 차 키, 이어폰, 시계, 보조 배터리 등 종류와 개수가 너무 많았다. 평소 불필요한 움직임을 아주 싫어하는 경재 씨는 이 물건들을 최대한 빠르게 챙겨서 외출하는 이동 경로를 알고 싶었다. 경재 씨는 한 걸음에 상하좌우에 인접한 칸으로만 움직일 수 있다. 경재 씨..

난이도 : 골드 4 걸린 시간 : 40분 문제 가장 가까운 공통 조상 문제 바로가기 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다. 예를 들어 15와 11를 모두 자손으로 갖는 노드는 4와 8이 있지만, 그 중 깊이가 가장 깊은(15와 11에 가장 가까운) 노드는 4 이므로 가장 가까운 공통 조상은 4가 됩니다. 루트가 있는 트리가 주어지고, 두 노드가 주어질 때 그 두 노드의 가장 가까운 공통 조상을 찾는 프로그램을 작성하세요..

난이도 : 골드 3 걸린 시간 : 30분 문제 다리 만들기 문제 바로가기 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 풀이 가장 짧은 다리의 길이 == 가장 가까운 두 점 사이의 최단 거리 모든 섬 사이의 최단 거리를 구해야 함 각 섬에 속한 점들로부터 다른 섬의 점들까지의 최단 거리 계산 가중치 없으므로 bfs 이용 각 섬에 속하는 점들은 bfs로 따로 찾기 코드 #include #include using namespace std; int map[101][101]; int direction[4][2] = { ..

문제 문제 설명 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. 풀이 만약 완전탐색으로 하고자 했다면? 반복을 index 0부터 n-1까지 돌면서 해당 집에서 시작해서 나타나는 최대의 money를 구할 수 있음 하지만 index 2를 고른다면, 집의 개수..

합승 택시 요금 난이도 : ★★★☆☆ 걸린 시간 : 못 풀었음 문제 합승 택시 요금 링크 해설 그래프 최단 경로 알고리즘 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명이 주..

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

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