알고리즘179 [백준 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. [백준 2188] 축사 배정 / 자바 / 이분매칭 #문제 레벨: P4알고리즘: 이분매칭 풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/2188#문제 풀이 이분매칭이 처음이라면 https://jsw5913.tistory.com/214 [백준 11375] 열혈강호 / 자바 / 이분 매칭#문제 레벨: P4알고리즘: 이분 매칭 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/11375#문제 풀이 이 문제는 이분 매칭 문제이다. 예시를 통해 문제를 설명하겠jsw5913.tistory.com이 글을 먼저 읽고 오길 바란다. [풀이방법] DFS 함수에서는 해당 소가 들어갈 수 있는 모든 축사를 확인한다:이미 방문한 축사.. 2024. 9. 21. [백준 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. [백준 12850] 본대 산책2 / 자바 / 수학 #문제 레벨: G1알고리즘: 수학풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/12850#문제 풀이 N의 최대값이 1억이다. 이미 브루트포스는 실패이다. 그렇다 하면 종료조건을 걸얼 백트래킹하게 하는 건 어떨까? 백트래킹의 조건은 학생회관까지 갔는데 남은 시간이 3분인 거다. 돌아가는 시간은 최소 4분이 걸리기 때문에 이미 실패다. 이 뒤에 상황을 안 살펴봐도 되는 거다.아니다. 그렇다 하더라도 무조건 시간복잡도에서 걸릴 것이다. 생각이 나지 않는다. 그래서 다른 사람의 풀이를 참조하였다. 문제의 포인트는 행렬곱셈이다. 예를 들어 설명하겠다. 아래 표는 1초에 i에서 j까지 갈 수 있는 경우의 수 배열이다.N =1ABCA011B.. 2024. 9. 12. [백준 28707] 배열 정렬 / 자바 / 다익스트라 알고리즘 #문제 레벨: G1알고리즘: 다익스트라 알고리즘풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/28707 #문제 풀이 이 문제는 다익스트라 알고리즘을 사용한다. 통상적인 다익스트라 알고리즘은 노드에 도입하여 이 문제에 대해서 어떻게 다익스트라 알고리즘을 이용할지 가늠이 안 갈 수도있다. 다익스트라 알고리즘을 적용할 때 노드가 아니라 상태A -> 상태 B로 갈 때 최소 비용이라고 생각하면 이해하기 편할 거다. 만약 예제2번을 들어 설명하자면,1313 - > 1133 로 갈 때의 최소비용을 저장하는 것이다. 다익스트라 알고리즘을 사용할 수 있는데 또 다른 이유가 있다. 당연한 이야기지만, 우리는 정렬된 정답 배열을 알고있다. 만약 131.. 2024. 9. 11. [백준 9328] 열쇠 / 자바 / bfs + 구현 #문제 레벨: G1알고리즘: bfs + 구현풀이시간: 1시간 힌트 참조 유무: 유https://www.acmicpc.net/problem/9328#문제 풀이 이 문제에서 중요한 건 bfs가 아니다. 구현에 초점에 맞춰진 문제이다. 그냥 bfs로 탐색하면 지금은 못가더라도 나중에 키(소문자)를 획득하고 나서 갈 수 있는 곳은 어떻게 갈 것인가? 어떻게 구현할 것인가를 묻고 있다. 아이디어는 간단하다. 지금 열 수 없는 문은 나중에 열 수도 있으니 저장해둔다. 그리고 해당 키를 얻었을 때 열 수 있는 문을 다 열고 마저 탐색한다.나머지는 주석참고 바란다.#풀이 코드 import java.io.BufferedReader;import java.io.IOException;imp.. 2024. 9. 10. [백준 7543] 합이 0인 네 정수 / 자바 / 투포인터 #문제 레벨: G2알고리즘: 투포인터풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/7453 #문제 풀이 ✔ 풀이법4개의 배열을 각각 조회하면 시간초과가 발생하므로 A와 B 원소의 합이 C와 D 원소의 합이 부호만 다르고 절대값이 같은 경우를 찾으면된다.여기서 의아한 사람들이 있을 거다. 엥 a+b = - (c+d) 조합만 고려하면 모든 경우의 수를 찾지 못하지 않나? a+c = -(b+d)라던지 a+d = -(c+b) 의 조합을 고려해야지 않나?아니다. 한 가지의 조합만 고려해도 모든 경우의 수를 알 수 있다. 예시를 들어보겠다.위와 같은 배열이 있을 때 a+b = - (c+d)의 경우의 수만 구해보겠다. a+b가 (1+4=5.. 2024. 9. 9. [백준 2623] 음악프로그램 / 자바 / 위상정렬 #문제 레벨: G3알고리즘: 위상정렬 풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2623 #문제 풀이 위상정렬이란 순서가 정혀져 있는 작업을 순서를 정해주는 작업을 뜻한다.코드는 큐로 구현된다. 방향성이 있는 선들을 하나 씩 끊어주는 느낌으로 구현하면된다. 그리고 선이 다 끊어진 노드들은 결과에 포함시킨다. 글보다는 코드로 보는 것이 이해가 더 쉬울 것이다. 아래를 참조바란다.#풀이 코드 import java.util.*;import java.io.*;public class Main { static ArrayList[] graph; static int[] inDegree; static int N, M.. 2024. 9. 6. [백준 2239] 스도쿠 / 자바 / dfs(백트래킹) #문제 레벨: G4 알고리즘: dfs(백트래킹)풀이시간: 1시간힌트 참조 유무: 유https://www.acmicpc.net/problem/2239#문제 풀이 해당 자리에 숫자를 놓으려면 해당 열, 해당 행, 해당 박스 안에 같은 숫자가 있으면 안된다. 이것들을 검사하는 코드를 구현하고 백트래킹을 통해서 숫자를 채워넣으면 된다.dfs 코드는 아래와 같이 방문한다. -------------------------> 1 번째 행-------------------------> 2 번째 행 -------------------------> 3 번째 행 -------------------------> 4 번째 행 -------------------.. 2024. 9. 1. 이전 1 2 3 4 5 ··· 20 다음
