자바125 [백준 1256] 사전 / 자바 / 조합 #문제 레벨: G2알고리즘: 조합, dp풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1256 #문제 풀이 이 문제에서 얻어갈 점은 두가지입니다.1. 조합을 계산하는 방법(일반 계산, dp로 표현)2. 문제 해결 아이디어문제 해결 아이디어부터 설명드리겠습니다. 문제를 보자마자 모든 알파벳 조합을 만들어 보는 것은 시간제한이 걸린다는 것을 직감할 수 있습니다. 그렇다면 저희가 해야 할 일은 앞에 놓을 수 있는 글자들을 놓아보는 것입니다. 앞에 a가 올려면 a~~~~에 문자열이 K번 째 문자열이 포함된다는 거고 앞에 z가 올려면 z~~~~에 k 번째 문자열이 포함된다는 겁니다.다르게 설명드리면, a~~~~에 놓을 수 있는 경우의 수가 .. 2025. 2. 1. [백준 2629] 양팔저울 / 자바 / dp #문제레벨: G3알고리즘: dp풀이시간: 1:20힌트 참조 유무: 유https://www.acmicpc.net/problem/2629#문제 풀이**첫 번째 접근: 실패처음 보자마자 **브루트 포스로 시간 복잡도가 통과되는지 확인했습니다. 구슬의 조합으로 해당 숫자를 잴 수 있는지 확인하려면, 숫자들의 플러스 마이너스의 조합입니다. 예를 들어 설명하겠습니다.아래 4개의 숫자 사이에 + 혹은 - 를 대입하고 합을 구하면 측정할 수 있는 무게가 됩니다. 만약 모두 -로 값이 음수라면 절대값을 씌우면 됩니다. 모두가 +인 값과 동일하기 때문입니다. 이 방식의 최악의 시간복잡도를 따져보면, 빈칸의 들어갈 조합의 경우의 수이기 때문에 2^30(N 최대값) 입니다. 1,024 x 1,024 x 1,024 = 1,00.. 2025. 1. 24. [백준 2098] 외판원 순회 / 자바 / TSP(dp + 비트마스킹 + dfs) #문제레벨: G1알고리즘: dp + 브루트 포스 + 비트 마스킹풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2098#문제 풀이TSP(Traveling Salesman Problem)시간 복잡도 O(n^2 * 2^n)이 문제는 전형적인 TSP 문제입니다. 한 노드에서 출발하여 모든 노드를 순회하고 다시 시작점으로 돌아오는데 최소값을 구하는 문제가 TSP입니다.TSP 문제를 가장 무식하게 푸는 방법은 모든 경우의 수를 다 탐색해보는 것입니다. 모든 경우의 수를 탐색해보는 것은 N!인데, 알고리즘에서 가장 나쁜 경우의 수가 N!입니다.저희는 DP를 사용해야 합니다. 큰 문제를 작은 문제로 쪼갠다. N = 3 일 때를 가정하면 아래와 같은 경우의 수가 있습니다.1.. 2025. 1. 23. [백준 2186] 문자판 / 자바 / dp + dfs #문제 레벨: G3알고리즘: dp + dfs풀이시간: 힌트 참조 유무:https://www.acmicpc.net/problem/2186#문제 풀이 처음 문제를 봤을 때 별 생각없이 아래와 같이 dfs 코드를 짰다. 코드는 문제에 맞게 구현됐다. 단지, 시간 초과가 날 뿐이다...잠시 이 dfs 코드를 흝어봐주고 내려와주라.dfs코드import java.io.*;import java.util.*;public class Main { static int N, M, K; static char[][] board; static String word; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, .. 2025. 1. 22. [9663] N-Queen , 자바 , dfs(백트래킹) 1. 문제레벨: G4알고리즘: dfs(백트래킹)풀이시간: 30분힌트 참조 유무: 유https://www.acmicpc.net/problem/96632. 문제 풀이실패 시도:서로 공격하지 않는 경우의 수로 구하려고 하였으나 N^2 C N 의 시간 복잡도가 나왔습니다. 이는 한 눈에 봐도 큰 경우의 수 입니다. 아무리 백트래킹을 한다그래도 N = 15, 시간제한 = 10초 안에 불가능할 거라 판단하였습니다.전체 경우의 수 - 서로 공격하는 경우 로 구하려고 하였으나 서로 공격하는 경우에서 2 ~ N이 서로 공격하는 경우를 구할 때 중복이 발생함으로 중복을 해결하는 과정이 너무 복잡해보였습니다. 잘못된 방법인 냄새실패 원인: N^2 C N에 대한 오해N^2 C N은 "N^2개의 칸에서 N개의 퀸을 선택하여 .. 2025. 1. 19. [백준 1799] 비숍 / 자바 / 백트래킹 + 분할정복 #문제레벨: G1알고리즘: 백트래킹 + 분할정복풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/1799#문제 풀이완전탐색을 할 경우 2의 100승으로 무조건 시간초과입니다. 그렇다 하면 조금 더 긍정적으로 생각해보겠습니다. 흰색칸 비숍과 검정칸 비숍은 서로 영향을 줄 수 없습니다. 그래서 우린 흰색칸 비숍과 검정칸 비숍을 나누어서 탐색하게 된다면2^50 + 2^50 으로 아까보다 나아졌습니다. 그래도 우린 시간초과에 걸립니다. 그렇다면 우리에겐 dp가 남아있습니다. 위 문제를 dp로 풀 경우를 생각하면 비트마스킹 dp을 생각해볼 수 있습니다. 이차원배열을 100자리의 비트마스킹으로 표현하는 것입니다. 그러나 대각선의 겹치는 비숍이 있는지 검사하기에는 까다로울 .. 2025. 1. 18. [쿼리문 개선] 댓글/대댓글 조회 dto로 받기 && 반복 루프로 인한 추가 쿼리 호출 문제 해결 기존코드PostCommentGetService@Service@RequiredArgsConstructorpublic class PostCommentGetService { private final PostCommentRepositoryCustom postCommentRepositoryCustom; @Transactional public List getPostComment(long postId) { List postCommentList = postCommentRepositoryCustom.findByPostId(postId); List responseList = new ArrayList(); Map responseHashMap = new HashMap();.. 2024. 12. 18. [백준 16565] N포커 / 자바 / 수학(포함배제원리 + 모듈러 연산) #문제 레벨: G1알고리즘: 수학(포함배제원리 + 모듈러 연산) 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/16565#문제 풀이 쌍이 맞는 조합 카드 4개를 뽑고 나서 나머지 카드를 뽑으면 된다. 쌍이 맞는 4개의 카드를 뽑는 경우의 수는 13이고 나머지 카드를 뽑는 건 52-4= 48에서 N-4를 뽑으면 되니48C(N-4)를 해주면된다. 13x 48C(N-4)위는 틀렸다.위 공식은 두 개 이상의 포카드가 있는 경우를 중복 계산할 수 있다. 예를 들면 N=8일 때 K 조합을 뽑고 48C4에서 포카드 조합이 나오거나 안 나오거나 두 케이스를 커버칠 수 있는 거 아니야? 라고 생각할 수 있다. 그 생각이 맞다. 그러나 우리는 중복.. 2024. 9. 23. [백준 13549] 숨바꼭질3 / 자바 / 다익스트라 알고리즘 #문제 레벨: G5알고리즘: BFS(그래프 탐색) 풀이시간: 30분힌트 참조 유무:https://www.acmicpc.net/problem/13549#문제 풀이 직관적으로 가장 빠른 방법은 -초를 소비하고 2배를 가는 거다. 그렇다면 우린 다익스트라 알고리즘을 사용하면 된다. 최종 목표지까지 최소한의 비용을 알고싶다면 출발지부터 최소한의 비용의 노드들 부터 탐색하면 되는 거다. 그래서 미리 큐에 거듭해서 거리는 두배지만 시간은 그대로인 배열이 거듭해서 추가 되고 먼저 빼지는 거다.#풀이 코드 import java.util.*;public class Main { static final int MAX = 100001; public static void main(.. 2024. 9. 14. 이전 1 2 3 4 ··· 14 다음
