우대비의 블로그

도시에서 태양이 질 때 보이는 건물들의 윤곽을 스카이라인이라고 한다. 스카이라인만을 보고서 도시에 세워진 건물이 몇 채인지 알아 낼 수 있을까? 건물은 모두 직사각형 모양으로 밋밋하게 생겼다고 가정한다. 정확이 몇 개의 건물이 있는지 알아내는 것은 불가능하고, 건물이 최소한 몇 채인지 알아내는 것은 가능하다. 이를 알아내는 프로그램을 작성해보자. 입력1. 첫째 줄에 N이 주어진다.2. N개의 줄에 2개의 수가 입력되고 왼쪽의 수는 x좌표, 오른쪽 수는 y좌표이다.3. 입력되는 좌표값들의 의미는 스카이라인의 고도가 바뀌는 지점이다. 풀이 방법우리는 최소 빌딩 수를 찾아야하는 조건이 있기 때문에 높이가 같은 입력들을 하나로 묶어줘야 합니다. 하지만 높이가 같다고 해도 연결되어있지 않다면 하나로 묶을 수 없습..

1부터 N까지의 수를 오름차순으로 정렬한 후, 숫자 사이에 '+' , '-', ' '(공백)을 삽입하여 계산할 때, 0이되는 모든 수식을 찾아주세요공백은 숫자를 이어 붙이는 것을 의미합니다 ex) 1 2+3 4+5 6 => 12 + 34 + 56 풀이 방법이 문제는 모든 경우의 수를 탐색 해야하는 브루트포스 알고리즘 문제입니다.이런 경우에는 DFS를 사용하여 탐색하는게 편합니다. private void DFS(List answer, string str, int num, int total)str에 1부터 넣고 2 ~ N 까지 차례대로 넣어주며 모든 경우의 수를 탐색합니다. 경우의 수 1) str + $"+{num}" 경우의 수 2) str + $"-{num}"경우의 수 3) str + $"+{num}+{..

틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임입니다.게임 판의 최종 상태들을 입력으로 받을 때, 그 상태가 게임에서 발생할 수 있는 상태인지 판별해주세요.가능하다면 valid, 불가능하다면 invalid를 출력합니다. 풀이 방법이 문제는 여러 조건문을 통해 풀어야하는 문제입니다.조건 1) O가 X보다 1개 이상 많으면 안됨 조건 2) X가 O보다 2개 이상 많으면 안됨 조건 3) 완성된 형태가 없는데 빈칸이 있으면 안됨 조건 4) X가 이겼는데 개수가 같으면 안됨 조건 5) O가 이겼는데 개수가 다르면 안됨조건 6) O와 X가 완성한 줄이 각각 하나 이상씩 있으면 안됨 게임의 시작은 항상 X가 먼저 하기 때문에 O가 X보다 더 많이 둘 수 없습니다.또한, 서로 하나씩 두기 때문에 X가 O보..

숫자를 입력받을 때, 하나 이상의 연속된 소수의 합으로 표현할 수 있는 가지 수를 구해주세요.ex) N = 41 -> 2+3+5+7+11+13, 11+13+17, 41 (3개) 풀이 방법해당 문제는 에라토스테네스의 체 알고리즘과 투 포인터 알고리즘을 통해 풀 수 있습니다.우선, 에라토스테네스 알고리즘을 통해 모든 소수를 찾고, 찾은 소수들을 바탕으로 투 포인터 알고리즘으로 N을 만들 수 있는 모든 조합을 찾습니다. 에라토스테네스의 체bool[] visited = new bool[N+1];for (int i = 2; i * i primNums = new List();for (int i = 2; i 에라토스테네스의 체를 통해 구한 소수들을 List에 담아줍니다.2 ~ N의 제곱근까지만 연산을 수행하여..

2차원 세계의 세로 길이 H와 가로 길이 W가 주어지고, 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 배열로 주어질 때,빗물이 내리면 고이는 빗물의 총량을 출력하여라.(바닥은 항상 막혀있고, 양 옆은 막혀있지 않습니다) 풀이 방법Stack을 활용해서 풀이하는 방법을 공유하겠습니다. 내려가는 계단왼쪽부터 오른쪽으로 높이를 Stack에 넣으면서 계산을 합니다.1번, 2번, 3번을 넣고 4번을 넣을 때, Stack.Peek()의 값보다 현재 높이가 더 높습니다.즉, 빗물을 채울 수 있는 조건을 의미합니다. 빗물이 채워지기 위해서는 빗물이 채워지는 공간 양 옆에 블록 기둥이 필수적으로 있어야합니다.4번을 넣을 때에는 반대쪽 기둥의 높이를 알아야합니다. stack.Push(list[i]);maxH = M..

양의 정수 K와 알파벳 소문자로 이루어진 문자열을 입력받을 때,(조건 1) 어떤 문자를 정확히 K개를 포함하는 가장 짧은 연속 문자열의 길이와(조건 2) 어떤 문자를 정확히 K개를 포함하며 첫 번째와 마지막 문자가 같은 연속된 문자열의 길이를 구해주세요.(구할 수 없다면 -1을 반환합니다.) 풀이 방법1. 문제의 함정조건 1과 조건 2는 탐색 방법이 다를 것 같지만 사실 그렇지 않습니다.조건 2는 첫 번째와 마지막 문자가 같다는 차이점이 보이지만, 조건 1도 마찬가지입니다."aaa", "baa", "aba" 조건 1은 모든 경우에서 조건 2와 마찬가지로 첫 번째 문자와 마지막 문자가 같습니다. 2. 시간초과 해결법문자열의 길이는 최대 1만, 문제의 수는 최대 100개 입니다.즉, N * N의 속도로 해..

뱀과 사다리 게임은 1부터 100까지의 숫자가 적힌 보드판에서 1에서 시작해서 100에 도착하는 게임이다.1부터 6까지 적힌 주사위를 굴려서 나온 수 만큼 이동할 수 있고, 사다리와 뱀을 만나면 연결된 위치로 이동하게 된다.이 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 최소 횟수를 구해보자. 풀이 방법이 문제는 최단 거리를 찾는 문제입니다 저는 Dijkstra 알고리즘을 사용하여 풀었습니다. - 입력 처리static void Main(string[] args){ string[] inputs = Console.ReadLine().Split(' '); int N = int.Parse(inputs[0]); int M = int.Parse(inputs[1]); List la..

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를 지워보겠습니다."먼저 푸는 것이..