문제 https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 풀이 주어진 시작점에서 다른 모든 정점으로의 최단경로인데 가중치가 양수이므로 다익스트라 알고리즘을 사용한다. 다익스트라 알고리즘을 사용할때에는 PrirorityQueue를 이용한다. 코드 import java.io.*; import java.util.*; public class Main { static class Info implements Compara..
문제 https://www.acmicpc.net/problem/11657 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 풀이 문제를 보면 한 도시에서 여러 도시로 이동할 수 있다고 한다. 그렇다면 쓸 수 있는건 그래프 알고리즘의 다익스트라와 벨만포드이다. 이때 시간은 음수가 나올 수 있다고한다. 그렇다면 벨만 포드 알고리즘을 이용하면 된다. 벨만포드 알고리즘은 다음 글을 참고하면 된다. https://velog.io/@suk13574/알고리즘Java..
문제 https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 말그대로 외판원 순회 문제이다. 외판원 순회는 DP + 비트마스킹 + DFS를 이용하여 풀어야 한다. 시간 복잡도는 O(2^n * n^2) 이므로 N의 크기가 작아야 한다. 따라서, 문제에서도 N의 크기가 15까지 나오는 것이다. dp배열은 다음과 같이 작성해야 한다. dp[현재 정점][방문한 정점들] 예를들어, 현재 2번정점에 있고 1,2,3을 방..
문제 https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 풀이 스타크래프트처럼 건물을 짓는데 순서가 있다. 따라서, 위상정렬을 이용하여 풀면된다. 자세한 내용은 바킹독님의 강의에 잘 나와있으니 밑 링크를 참고하면 되겠다 https://blog.encrypted.gg/1020 위상정렬을 이용할때에는 그래프를 저장하기위한 인접리스트와 indegree 배열이 필요하다. 이 문제에서는 각 건물을 짓는데 걸리는 시간을 구하기 때문에 이를 저장할 ..
문제 https://www.acmicpc.net/problem/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 풀이 Index Tree 를 이용하여 푼다 코드 import java.io.*; import java.util.*; public class Main { static int n; static int arr [] = new int [3000000]; static int first; static StringBuilder sb = new StringBuilder(); pu..
문제 https://www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 전체 경우의 수에 대하여 탐색해야 하므로 Back Tracking을 이용하는 문제이다. 퀸은 가로, 세로, 대각선으로 이동할 수 있다. 따라서 퀸 n개는 같은 가로줄, 세로줄, 대각선 줄에 존재하면 안된다. 예를 들어보자. 4x4 체스판에 4개의 퀸을 놓는다고 생각하자 (1,1) 과 (2,3)에 퀸을 놓았을 경우 3번째 행에는 퀸이 올수가 없다. 이는 다음의 그림을 통해 확인 할 수 있다. 따라서 퀸이..
대표적인 그리디 알고리즘 문제 /* package whatever; // don't place package name! */ import java.util.*; import java.lang.*; import java.io.*; /* Name of the class has to be "Main" only if the class is public. */ public class Main { public static void main (String[] args) throws java.lang.Exception { Scanner scan = new Scanner(System.in); int money [] = {500,100,50,10,5,1}; int n=scan.nextInt(); int result=0; ..
www.acmicpc.net/problem/10809 10809번: 알파벳 찾기 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출 www.acmicpc.net #include #include int main(){ int status=0; char s[101]={0}; scanf("%s",&s); for(int i=0;i
www.hackerrank.com/challenges/grading/problem Grading Students | HackerRank Round student grades according to Sam's rules. www.hackerrank.com next multiple of 5를 이용하여 다시 점수를 매기는 문제이다. next multiple of 5가 무엇인지를 알아야 한다. Take the number in a variable. Divide it by 5 and get the decimal value. (원래의 값에서 5로 나눈다. 이때 나누어진 값은 소수여야 함) Take the ceil value of the decimal value by using math. ceil(). (ceil()..
www.hackerrank.com/challenges/electronics-shop/problem Electronics Shop | HackerRank Determine the most expensive Keyboard and USB drive combination one can purchase within her budget. www.hackerrank.com 정해진 한도에서 두 배열에서 각각 하나씩 더해서 한도 내에 있으면 그것을 출력하고 아니면 -1을 출력하는 문제 keyboard[i]+drives[j]가 max보다 크고, b(예산) 이하이면 max에 keyboard[i]+drives[j]를 넣는다. max가 0이라는 것은 정해진 한도에서 살 수 없다는 뜻으로 -1을 리턴하고 아니면 max를 리턴한다.
