전체 글

10942 - 팰린드롬?https://www.acmicpc.net/problem/10942문제ex. 칠판에 적은 수 1, 2, 1, 3, 1, 2, 1- S = 1, E = 3 -> 1, 2, 1 (O)- S = 2, E = 5 -> 2, 1, 3, 1 (X)- S = 3, E = 3 -> 1 (O)- S = 5, E = 7 -> 1, 2, 1 (O)입력첫째 줄: 수열의 크기 N (1 둘째 줄: 칠판에 적은 수 N개 (셋째 줄: 질문의 개수 M (1 넷째 줄 ~ M개의 줄: 질문 S, E출력: 총 M개 줄에 걸쳐 팰린드롬 O -> 1 / X -> 0풀이DP질문 M이 1,000,000개 -> 팰린드롬인지 검사하는 로직 1,000,000번 반복=> 검사를 O(1)로 해야 함IF. 한 번 검사할 때 O(N),..

1987 - 알파벳https://www.acmicpc.net/problem/1987문제세로 R칸, 가로 C칸 보드/ 각 칸에 대문자 알파벳 적혀 있고 좌측 상단 (1행 1열)에 말이 놓여 있음말은 상하좌우 인접한 네 칸 중 한 칸으로 이동할 수 있음새로 이동한 칸에 적혀 있는 알파벳은 지나온 모든 칸에 적혀 있는 알파벳과 달라야 함 (같은 알파벳 적힌 칸 두 번 지날 수 없음)입력첫째 줄: R, C (1 둘째 줄 ~ R개 줄: 보드에 적혀 있는 C개의 대문자 알파벳출력: 말이 지날 수 있는 최대 칸 수풀이알파벳 방문 여부 체크static boolean[] visited = new boolean[26];visited[board[0][0] - 'A'] = true;코드import java.io.*;impor..

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..