전체 글

1759 - 암호 만들기https://www.acmicpc.net/problem/1759문제암호는 서로 다른 L개의 알파벳 소문자/ 최소 1개의 모음(a, e, i, o, u) + 최소 2개의 자음으로 구성암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열암호로 사용했을 법한 문자의 종류는 C가지=> C개의 문자 모두 주어졌을 때, 가능성 있는 암호들 모두 구하기입력첫째 줄: 두 정수 L, C (3 다음 줄: C개의 문자 공백 구분 (중복 X)출력: 각 줄에 하나씩, 사전식으로 가능성 있는 암호 모두 출력풀이DFS + Backtracking모음 검사static boolean isVowel(char c) { return c == 'a' || c == 'e' || c == 'i' || c == 'o'..

9251 - LCShttps://www.acmicpc.net/problem/9251문제LCS(Longest Common Subsequence, 최장 공통 부분 수열): 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것 찾기ex. ACAYKP, CAPCAK의 LCS: ACAK입력: 첫째 줄과 둘째 줄에 알파벳 대문자로 이뤄진 두 문자열 주어짐 (최대 1000글자)출력: 주어진 두 문자열의 LCS 길이풀이`dp[i][j]`: str1의 i번째 문자까지, str2의 j번 문자까지 고려했을 때 LCS 길이`str1[i - 1] == str2[j - 1]` -> `dp[i][j] = dp[i - 1][j - 1] + 1`=> 두 문자 같으면 지금 문자를 LCS에 포함`str1[i - 1] !..

1149 - RGB 거리https://www.acmicpc.net/problem/1149문제RGB 거리에는 집이 N개 있음/ 거리는 선분으로 나타낼 수 있고 1 ~ N번 집 순서대로 있음집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 함/ 각각의 집을 rgb로 칠하는 비용 주어졌을 때 규칙 만족하면서 모든 집 칠하는 비용의 최솟값- 1번 집 색 != 2번 집 색- N번 집 색 != N-1번 집 색- i (2 입력첫째 줄: 집의 수 N (2 둘째 줄 ~ N개 줄: rgb로 칠하는 비용 (출력: 모든 집을 칠하는 비용의 최솟값풀이색 인덱스: 0 (빨강) / 1 (초록) / 2(파랑)`dp[i][j]`: i번째 집까지 칠했을 때, i번 째 집의 색이 j일 때의 최소 비용`dp[i][0] = min(dp[i ..

2166 - 다각형의 면적https://www.acmicpc.net/problem/2166문제2차원 평면상에 N(3 => 다각형의 면적입력첫째 줄: N다음 N개의 줄: 다각형을 이루는 순서대로의 x, y좌표 (x, y 출력: 면적/ 소수점 아래 둘째 자리에서 반올림하여 첫째 자리까지 풀이신발끈 공식N개의 꼭짓점 (x1​,y1​),(x2​,y2​),...,(xN​, yN​)이 반시계/시계 순서로 주어졌을 때면적 = $|Σ(x_i * y_{i+1}) − Σ(y_i * x_{i+1})| / 2$/ 마지막은 다시 첫 점과 이어줘야 함$x_{N+1​} = x_1$$y_{N+1} = y_1$​long sum1 = 0;long sum2 = 0;for (int i = 0; i 코드import java.io.*;impo..

1106 - 호텔https://www.acmicpc.net/problem/1106문제홍보할 수 있는 도시가 주어지고 각 도시별로 홍보하는데 드는 비용/ 그 때 몇 명의 호텔 고객이 늘어나는지에 대한 정보ex. 어떤 도시에서 9원 들여서 홍보 -> 3명 고객 늘어남 => 돈에 정수배만큼 투자할 수 있음9원 -> 3명, 18원 -> 6명, 27원 -> 9명 (O) / 3원 -> 1명, 12원 -> 4명 (X)=> 호텔 고객 적어도 C명 늘이기 위해 투자해야 하는 돈의 최솟값입력첫째 줄: C (둘째 줄 ~ N개 줄: 도시에서 홍보할 때 대는 비용, 그 비용으로 얻을 수 있는 고객 수 (출력: 문제의 정답풀이배낭 문제(Knapsack Problem)제한된 무게/비용 안에서 가치/이익을 최대화해서 조합 찾는 문제..

1707 - 이분 그래프https://www.acmicpc.net/problem/1707문제이분 그래프(Bipartite Graph): 그래프의 정점의 집합을 둘로 분할해 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할한 그래프입력첫째 줄: 테스트 케이스 개수 K각 테스트 케이스 첫째 줄: 그래프 정점의 개수 V, 간선의 개수 E (각 정점에는 1부터 V까지 차례로 번호)둘째 줄 ~ E개 줄: 인접한 두 정점의 번호 u, v (u != v, 간선의 대한 정보)출력: 이분 그래프 O -> YES / X -> NO 순서대로 출력풀이이분 그래프그래프의 모든 정점을 두 그룹(A, B)로 나눴을 때 인접한 두 정점이 같은 그룹 속하지 않게 나눌 수 있어야 함 = 인접한 정점은 항상 반대편 그룹이어야 함 시작..