Algorithm

[프로그래머스, Java] 단속카메라

🔗 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42884 🤔 문제 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 📌 제한사항 차량의 대수는 1대 이상 10,000대 이하입니다. routes에는 차량의 이동 경로가 포함되어 있으며 routes[i][0]에는 i번째 차량이 고속도로에 진입한 지점, routes[i][1]에는 i번째 차량이 고속도로에서 나간 지점이 적..

[프로그래머스, Java] N^2 배열 자르기

🔗 문제 링크 https://programmers.co.kr/learn/courses/30/lessons/87390 🤔 문제 정수 n, left, right가 주어집니다. 다음 과정을 거쳐서 1차원 배열을 만들고자 합니다. n행 n열 크기의 비어있는 2차원 배열을 만듭니다. i = 1, 2, 3, ..., n에 대해서, 다음 과정을 반복합니다. 1행 1열부터 i행 i열까지의 영역 내의 모든 빈 칸을 숫자 i로 채웁니다. 1행, 2행, ..., n행을 잘라내어 모두 이어붙인 새로운 1차원 배열을 만듭니다. 새로운 1차원 배열을 arr이라 할 때, arr[left], arr[left+1], ..., arr[right]만 남기고 나머지는 지웁니다. 정수 n, left, right가 매개변수로 주어집니다. 주어..

[백준, Java] 1707번 : 이분 그래프

🔗 문제 링크 https://www.acmicpc.net/problem/1707 🤔 문제 그래프의 정점의 집합을 둘로 분할하여, 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할할 수 있을 때, 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 라 부른다. 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오. 😮 문제 해결 방법 이분 그래프는 문제에 나와 있는 것 처럼 정점끼리 이어진 그래프를 하나의 집합으로 보고 서로 연결된 정점끼리는 다른 두 그룹으로 속하게 하는 그래프를 말한다. 따라서, 이분 그래프를 판별하는 방법은 다음과 같다. 색칠되지 않은 모든 정점에 대해 BFS를 진행한다. BFS의 시작 정점을 임의의 색상으로 색칠한다. ..

[백준, Java] 1806번 : 부분합

🔗 문제 링크 https://www.acmicpc.net/problem/1806 🤔 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. 😮 문제 해결 방법 아래의 그림과 같이 num 배열이 주어지고 다음 인덱스로 갈 때 마다 이전 값을 누적해서 더해주는 sum배열을 생성한다. 각 인덱스의 누적합을 더해준 sum배열의 동작에 대해 알아야한다. 예를 들어, sum 배열에서 인덱스 2에서 인덱스 6까지의 부분합을 구하고 싶다면, sum[6] - sum[2] = 25를 구할 수 있다. 이 결과가 성립할 수 있는 이유는 sum[2] = num[1] ~ num[2]까지..

[ 백준, Java] 1339번 : 단어 수학

🔗 문제 링크 https://www.acmicpc.net/problem/1339 🤔 문제 민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그..