분류 전체보기

1916 - 최소비용 구하기https://www.acmicpc.net/problem/1916문제N개의 도시/ 한 도시에서 출발해서 다른 도시에 도착하는 M개의 버스A번째 도시에서 B번째 도시까지 가는데 드는 비용 최소화입력첫째 줄: 도시 개수 N (1 둘째 줄: 버스 개수 M (1 셋째 줄 ~ M+2줄: 출발지, 도착지, 비용 (0 M+3줄: 구하고자 하는 구간 출발지, 도착지출력: 출발 도시에서 도착 도시까지 가는데 드는 최소 비용코드import java.io.*;import java.util.*;// 최소비용 구하기public class boj_1916 { static class Node implements Comparable { int to, cost; Node(in..

1238 - 파티https://www.acmicpc.net/problem/1238문제N개의 숫자로 구분된 각각의 마을에 한 명 학생 살고 있음/ N명의 학생이 X번 마을에 모여서 파티를 벌이기로 함마을 사이에 총 M개의 단방향 도로가 있고 i번째 길을 지나는데 $T_i$ 시간 소비파티에 참석하기 위해 걸어가서 다시 마을로 돌아와야 함/ 최단 시간에 오가기도로는 단방향이기 때문에 오고 가는 길이 다를 수 있음입력첫째 줄: N (1 두 번째 줄 ~ M + 1줄: i번째 도로의 시작점, 끝점, 필요한 소요시간 $T_i$(시작점 != 끝점, 한 도시 A에서 다른 도시 B로 가는 도로의 개수 최대 1개)출력: N명의 학생들 중 오고 가능데 가장 오래 걸리는 학생의 소요시간풀이Dijkstra가중치(비용) 있는 그래..

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