Algorithm (PS)/백준18 [백준 9663] N-Queen (Java) [백트래킹] 문제 https://www.acmicpc.net/problem/9663 알고리즘 백트래킹 풀이 특정 규칙을 파악하면 바로 풀 수 있는 문제이다. 15x15의 모든 경우의 수를 파악하게 된다면 15!이므로 시간초과가 나게 된다. 따라서 특정 조건에 맞는다면 재귀를 타게하고 조건에 맞지 않는다면 스킵하면 백트래킹 처리를한다. 체스를 놓을 때마다 각 행에 대해 퀸의 위치를 마킹하고, 만약 전에 놓았던 퀸이 있다면 퀸을 놓을 수 있는 위치를 파악하며 문제를 풀이한다. 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Test_Bac.. 2023. 7. 20. [백준 1753] 최단경로(Java) 다익스트라 문제 https://www.acmicpc.net/problem/1753 알고리즘 다익스트라 (우선순위 큐 사용) 풀이 이 문제는 가중치가 1이 아니고 음의 가중치도 아니기 때문에 다익스트라를 이용하여 풀이 할 수 있다. 먼저 모든 노드의 거리를 무한으로 초기화 한다. 그리고 우선순위 큐를 사용하여 간선의 거리가 짧은 것부터 나오도록 해주어 시작점부터 다른 노드까지의 최소 거리를 구한다. 코드 package com.company; import java.io.*; import java.util.*; public class Test_dijstra { static int V,E; static int start; static int[] dist; static List[] graph; static final int.. 2023. 7. 19. [백준 14501]. 퇴사 (Java) - 완전탐색 문제 https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 알고리즘 완전탐색 풀이 완전탐색을 통해 상담할 수 있는 모든 경우의 수를 구한다음 최대 값을 구해주어 풀었다. 1개 의 상담에 대해 선택 O/X하는 2가지의 경우가 존재하므로 전체 N개 상담에 대한 최대 경우의 수 = 2^n => 32,768이다. 조건 값이 적어서 그렇지 많게 되면 dp로 풀어야한다. 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.. 2023. 7. 17. [백준] 15661 (Java) [완전탐색] 문제 https://www.acmicpc.net/problem/15661 15661번: 링크와 스타트 첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 알고리즘 완전탐색 (브루트포스) 풀이 먼저 메인함수에서 for문을 통해 최소1명부터~N명까지 pick을 하고 재귀를 통해 그에 맞게 팀을 start와 link로 구분하면 되는 문제였다. 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import j.. 2023. 7. 14. [백준] 2178. 미로탐색 (Java) [BFS 최단거리) 문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 알고리즘 BFS 최단거리 풀이 BFS를 통해 4방향 탐색을 하며 최단거리를 구하는 문제다. 단 벽이 있는 경우, 이미 방문한 좌표, 맵 밖을 벗어나는 경우를 주의하며 이동을 해야한다. 코드 package com.company; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.L.. 2023. 7. 11. [백준] 1260. DFS와 BFS (Java) 문제 https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 알고리즘 DFS, BFS 풀이 그래프 간의 연결 관계를 인접리스트로 설정해주고, 정점 작은 것을 먼저 방문해줘야 하기 때문에 정렬을 해줬다. 그리고 DFS, BFS를 통해 탐색을 진행시켰다. 인접리스트를 이용한 풀이, 배열을 사용한 풀이 2가지로 풀어보았다. 코드 [인접리스트를 이용한 풀이] package com.company; import java.io.. 2023. 7. 10. 이전 1 2 3 다음