알고리즘176 [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. [백준 16234] 인구 이동 / 자바 / bfs #문제레벨: G4알고리즘: bfs풀이시간: 50분힌트 참조 유무:https://www.acmicpc.net/problem/16234#문제 풀이특정 국가(A)를 기준점으로 삼고 그 국가와 연할될 수 있는 국가(B)를 찾고 B와 연합될 수 있는 국가를 찾고(C) 반복한다. 이 형식 어디서 보지 않았는가? 4방향+bfs(or dfs)이다. 그런데 bfs 한 번으로 모든 국가를 다 탐색할 수는 없다. 그래서 이중 for문으로 모든 국가를 돌대 visited =false(방문하지 않은) 곳만 bfs(or dfs)를 돌린다. 코드는 둘 다 첨부하겠다.코드를 보면 bfs(or dfs)를 마치고나서 인구이동을 시킨다. bfs로 인접국가를 순회하는 김에 인구이동까지 하면 안되나? 라는 충동이 들었지만, 구현이 복잡하고 .. 2025. 1. 17. [백준 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. 이전 1 2 3 4 ··· 20 다음
