우대비의 블로그

V개의 마을과 E개의 도로로 구성되어 있는 도시가 있다.당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다.운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에 사이클을 찾아야한다.당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾아보자.( 두 마을을 왕복하는 경우도 사이클에 포함됨에 주의한다. ) 풀이 방법"가장 짧은 사이클"을 구하는 문제이기 때문에 아이디어가 필요한 문제입니다.우선, 가장 짧은 사이클이든 뭐든 최단 경로를 묻는 문제이기 때문에 사용할 알고리즘을 선택해야합니다. 해당 문제는 시작 위치가 정해져있지 않기 때문에 모든 노드 사이의 거리를 찾아야합니다.모든 ..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr A도둑괴 B도둑이 물건을 훔치려고 합니다. 물건을 훔칠 때 생기는 흔적의 양을 배열로 받고, A도둑이 경찰에 붙잡히는 최소 흔적 개수 N과 B 도둑이 경찰에 붙잡히는 최소 흔적 M을 입력 받을 때, A와 B 모두 경찰에 붙잡히지 않으면서 모든 물건을 훔치는 경우중 A의 최소 흔적 개수를 구해주세요. 풀이 방법info의 길이가 40이기 때문에 완전 탐색을 하면 2^40, 약 1조개의 탐색이 발생하게 됩니다.그렇기 때문에 완전탐색으로는 문제 해결을 못할것 같지만,예외처리를 잘해준다면 완전탐색 코드로도 충분히 해결이 가능합니다. 여기서는 DFS를 사용해서 문제를..

1번부터 N번까지의 문제가 있을 때, 문제를 푸는 순서를 구해주세요.조건 1. N개의 문제는 모두 풀어야한다조건 2. 먼저 푸는 것이 좋은 문제가 있다면 먼저 풀어준다.조건 3. 가능하면 쉬운 문제부터 푼다 (1 ~ N 순서로 난이도 상승)해당 문제는 위상 정렬 알고리즘을 통해 풀이하는 문제입니다.위상정렬에 대해서 모른다면 아래 링크에서 확인할 수 있습니다. 위상 정렬 알고리즘위상 정렬 알고리즘 - 순환이 없는 방향 그래프에서의 노드들을 순서대로 나열해주는 알고리즘 우선 위의 그래프를 위상 정렬 알고리즘을 통해 정렬을 하면 1 - 2 - 4 - 5 - 3 - 6 - 7 이 나옴 정렬 과flrjtwjrjt.tistory.com 풀이 방법 문제를 이해하기 위해 조건 2를 지워보겠습니다."먼저 푸는 것이..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr숫자를 입력 배열로 입력 받을 때, 숫자들을 조합해서 만들 수 있는 가장 큰 수를 구해주세요.ex) [3, 30, 34, 5, 9] => "9534330" 풀이방법해당 문제는 정렬 알고리즘 문제입니다.일반적인 정렬과는 다르게 두 원소를 이어붙였을 때, 어떤게 더 큰지에 따라 우선순위를 결정합니다.public bool Comp(int a, int b){ int A = int.Parse(a.ToString() + b.ToString()); int B = int.Parse(b.ToString() + a.ToString()); re..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 수를 strinf으로 입력 받을 때, 해당 수들을 조합해서 만들 수 있는 수 중에 소수인 것들의 개수를 구해주세요. (중복 조합 x) 풀이 방법해당 문제는 2개로 구분하여 풀이합니다. 1. 중복 없이 조합하기2. 소수인지 체크하기 우선 중복 없이 조합하는 방법을 소개하겠습니다.중복 없이 조합하는 방법public void DFS(string str = ""){ for (int i = 0; i DFS와 반복문을 조합하여 수를 조합합니다. public void DFS(bool[] visited, string str = ""){ for (int i =..

프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다.Demi는 N시간 동안 야근 피로도를 최소화하도록 일할 겁니다Demi가 1시간 동안 작업량 1만큼을 처리할 수 있다고 할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수 solution을 완성해주세요. ex) works = [4, 3, 3], k = 4works를 [2, 2, 2]로 만들어야 최소 야근 피로도가 나옵니다. 풀이 방법야근 피로도의 공식은 아래와 같습니다.works[0] ^ works + works[1..

10816번: 숫자 카드 2 들어가며이 문제는 숫자 카드를 몇개 가지고 있는지 찾는 문제입니다. 상근이가 가지고있는 숫자 카드의 최대 개수는 50만개,체크 해야할 숫자 카드의 최대 개수가 50만개이기 때문에 2중 for문을 사용하면 시간 초과가 발생합니다. 가장 빠르게 풀 수 있는 방법은 Dictionary를 통해 상근이가 가지고 있는 숫자 카드의 개수를 저장하는 것입니다.Dictionary cards = new Dictionary();cards[숫자 카드] += 1; 하지만, 해당 문제는 이진 탐색 문제이기에 이진 탐색 풀이 방법을 공유하겠습니다. 풀이 방법이진 탐색을 통해 상근이가 가지고 있는 숫자를 찾기 위해서는 우선, 상근이의 카드를 정렬 해줘야합니다.정렬된 카드들을 이진 탐색을 통해 위치를 ..

풀이 방법해당 문제는 완전 탐색을 통해 풀이해야 합니다.모든 경우의 수를 하나하나 탐색하여 퀸을 놓을 수 있는지 체크하고, 개수를 저장하고 출력하면 됩니다. 힌트 1퀸은 상, 하, 좌, 우로 이동할 수 있습니다.즉, 현재 놓으려는 위치의 Y값과, X값을 사용하는 다른 퀸이 존재한다면, 그 자리는 놓을 수 없는 자리입니다.그렇기에 Y값 하나에 1개씩, X값 하나에 1개씩 밖에 퀸을 둘 수가 없습니다. 힌트 2퀸은 대각선으로도 이동할 수 있습니다.즉 퀸A에 퀸B의 위치값을 뺄 때, 방향 벡터 X와 Y의 절대값이 같다면 대각선에 위치한다는 의미이기 때문에놓을 수 없는 경우의 수 입니다. 힌트 3최대 15개의 퀸을 15 * 15개의 체스판에 모두 배치하는 모든 경우의 수를 탐색할 때,반복문을 어떻게 배치해야할지..

using System;using System.Collections.Generic;using System.Linq;namespace Alroghtim_CS{ class Program { static void Input(out List rank, out List newRanks) { rank = new List(); newRanks = new List(); int n = int.Parse(Console.ReadLine()); string[] ranking = Console.ReadLine().Split(' '); for (int i = 0; i rank, out List newRanks); int n = rank.Count; HashSet[] outDegree = new Ha..

11729번: 하노이 탑 이동 순서 문제세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.아래 그림은 원판이 5개인 경우의 예시이다. 풀이 방법힌트1가장 아래의 원판을 3번째로 옮기려면 어떻게 해야할까?당연하게도 다른 모든 원판을 2번째로 옮겨야 한다. 즉, 가장 큰 원판을 제외한 다른 원판을 중간 지점으로 보내는 것이 핵심이..