난이도 : 골드 5 걸린 시간 : 1시간 반 이상 (오류 찾기) 문제 최단경로 문제 바로가기 풀이 다익스트라 기본 구현을 이용해서 푼다. 다익스트라 개념 바로가기 코드 #include #include #include using namespace std; int main() { // 입력 // v, e는 10^5, 10^6이하 int V; int E; cin >> V >> E; int start; // 시작 정점 cin >> start; vector edge(V+1, vector(0)); for (int i = 0; i > from >> to >> val; edge[from].push_back(make_pair(to..

난이도 : 골드 5 걸린 시간 : 50분 문제 합분해 문제 바로가기 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 풀이 작은 문제 : 현재 남은 N에서 남은 K개로 N을 만들 수 있는 경우의 수 재귀 함수 : (N, K) => int 의 형태 사용하는 수 i를 for문 돌면서, j를 1씩 감소시켜서 재귀 종료 조건 N이 0일 때는 남은 수가 모두 0인 경우 1가지만 존재 K가 0이고 N가 0이 아닐 때 남은 경우..

괄호 변환 문제 programmers.co.kr/learn/courses/30/lessons/60058 문제 설명 카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다. 수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다. 용어의 정의 '(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개..

최단 경로 그래프에서 유도되는 문제들 중 최단 경로 문제가 있다. 주어진 그래프에서 특정 정점에서 다른 정점까지의 최단 경로(가중치 합이 최소인 경로)가 무엇인지를 알아내는 문제이다. 이는 이전의 MST 문제와 다르다. 모든 정점을 포함할 필요가 없기 때문이다. 하지만 MST에서 사용했던 Prim(Dijkstra) 알고리즘을 응용해서 구현할 수 있다. [MST] Dijkstra 알고리즘 구현 vertice(정점)는 3가지 분류로 나뉜다. tree vertice(T) : tree에 속해 있는 정점 fringe vertice (F) : tree에 포함되지 않으면서 연결되어있는 정점 unseen vertice (U) : 나머지 MST에서 T와 F의 정점 사이의 최소 가중치를 계속 갱신해주었던 것 대신에, 최단..

MST Spanning Tree : 그래프 내의 모든 정점을 포함하는 트리 우선 트리의 정의는 connected undirected acyclic graph (연결 비방향 비순환 그래프)이다. 모든 노드는 연결되어있으며, 방향성은 없고 순환이 존재하지 않는 그래프이다. 하나의 그래프가 주어졌을 때, 그래프 내에서 여러 트리를 찾을 수 있다. 그 중 특별하게 모든 정점을 포함하는 트리를 Spanning Tree라고 한다. 다르게 말하면 Spanning tree(신장 트리)는 그래프의 부분 그래프면서 간선의 수가 가장 적은(최소 연결) 그래프이다. 감이 안온다면 그림으로 살펴보자. 위의 그림과 같이 그래프가 주어졌을 때, 최소한의 간선을 사용하여 모든 정점을 포함하는 부분 그래프가 여러 개 존재한다. 이 부..

여행경로 문제 https://programmers.co.kr/learn/courses/30/lessons/43164 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합..

타겟 넘버 문제 https://programmers.co.kr/learn/courses/30/lessons/43165 문제 설명 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 = 3 +1+1+1-1+1 = 3 +1+1+1+1-1 = 3 사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 주어지는 숫자의 개수는 2개 이상 ..

위장 문제 https://programmers.co.kr/learn/courses/30/lessons/42578 문제 설명 스파이들은 매일 다른 옷을 조합하여 입어 자신을 위장합니다. 예를 들어 스파이가 가진 옷이 아래와 같고 오늘 스파이가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야 합니다. 종류 이름 얼굴 동그란 안경, 검정 선글라스 상의 파란색 티셔츠 하의 청바지 겉옷 긴 코트 스파이가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요. 제한사항 clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다...