문제 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.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 알파벳이 대소문자로 이루어져있고 가장 많이 나온 글자를 출력하는 문제이다. 배열의 인덱스가 대문자의 아스키코드가 된다면 글자가 몇개가 나올지를 배열에 넣을 수 있을것이다. 즉, 예를 들어 s라는 배열이 있고 단어에 a가 2개가 나왔다면 s[65]==2가 된다. 배열의 인덱스를 대문자로 만들기 위해서 입력받은 문자열에 대해 toupper함수를 사용하면 된다. 주의해야 될것이 있다. 처음에 문제를 풀 때 for문에서 조건부분에 strlen(str)..
www.acmicpc.net/problem/1152 1152번: 단어의 개수 첫 줄에 영어 대소문자와 띄어쓰기로 이루어진 문자열이 주어진다. 이 문자열의 길이는 1,000,000을 넘지 않는다. 단어는 띄어쓰기 한 개로 구분되며, 공백이 연속해서 나오는 경우는 없다. 또한 � www.acmicpc.net solved.ac에서 브론즈 2, class 1으로 책정된 문제 문제의 내용은 다음과 같다. 1. 단어는 띄어쓰기 한 개로 구분 2. 공백이 연속해서 나오는 경우는 없다 3. 문자열의 앞과 뒤에는 공백이 있을 수도 있다. 공백이 포함되게 입력을 받고 문자열에서 공백의 개수를 구한다. 문자열의 맨 앞과 맨 뒤에 공백이 있는지 확인한다. 공백이 있으면 공백의 개수에서 -1을 해준다. 그리고 단어의 개수는 공..
https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 자료구조 수업시간에 재귀를 배울 때 나온 내용 배우고 시험봤을때는 쉬웠는데 한달 동안 쉬고 봤더니 은근 까다로움 알고리즘 1번에서 3번으로 n개의 원판을 옮긴다고 하자 그렇다면 가장 큰 판을 3번으로 우선 옮겨야 할 것이다. 따라서 가장 큰 판을 제외하고 n-1개의 나머지 판들을 2번으로 옮긴다. 그리고 가장 큰 판을 3번으로 옮긴 후 2번의 n-1개 판들을 3번으로 옮기면 된다. 나..
