Hayden's Archive

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 내가 작성한 코드 import java.util.Scanner; public class Main { public static boolean prime(int a) { if(a==1) {//1인 경우 return false; } for(int i=2; i*i

알고리즘 문제 출처 : https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 내가 작성한 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { public static int gcd(int a, int b) { //최대공약수 if(b==0) { re..

* 나머지 연산(Modular Arthimetic) - 컴퓨터의 정수는 저장 범위가 한정적 -> 그래서 답을 M으로 나눈 결과를 출력하라는 문제가 종종 나옴 - (A+B)%C 와 (A%C+B%C)%C 는 같고, (A*B)%C 와 (A%C*B %C)%C 는 같다 * 최대공약수(Greatest Common Drivisor = GCD) // 관련 알고리즘 : https://hayden-archive.tistory.com/279 - 서로소(Coprime) : 최대공약수가 1인 두 수 - 최대공약수를 구하는 가장 빠른 방법 -> 유클리드 호제법(Euclidean algorithm) 이용 - 유클리드 호제법 : a를 b로 나눈 나머지를 r이라고 할 때 GCD(a,b) = GCD(b,r) - 이 때 r이 0이면 그 ..

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이�� www.acmicpc.net 관련 문제 포스팅 : https://hayden-archive.tistory.com/276 내가 작성한 코드 후위 표기식 문제를 풀고 풀었더니 쉽게 풀 수 있었던 문제. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.ut..

알고리즘 문제 출처 : https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식�� www.acmicpc.net 관련 알고리즘 : 차량기지 알고리즘 https://ko.wikipedia.org/wiki/%EC%B0%A8%EB%9F%89%EA%B8%B0%EC%A7%80_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 정답 비율 30.790%를 자랑하는 문제. 생각지도 못한 반례에서 계속 부딪혀서 9번만에 정답을 맞혔다... 후위표기식 문제에서 나올 수 있는..

알고리즘 문제 출처 : https://www.acmicpc.net/problem/10808 10808번: 알파벳 개수 단어에 포함되어 있는 a의 개수, b의 개수, …, z의 개수를 공백으로 구분해서 출력한다. www.acmicpc.net 내가 작성한 코드 아스키코드를 활용하면 쉽게 풀 수 있는 문제 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.HashMap; import java.util.Stack; public class Main { ..

알고리즘 문제 출처 : https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 내가 작성한 코드 헷갈려서 많이 헤맸던 문제. 스택 없이도 풀어볼 수 있을 것 같아서 이중 for문으로 도전했다가 시간 초과가 나왔다. 이후 스택을 2개를 사용해보기도 했지만 애시당초 접근이 틀렸다. 자료의 크기가 최대 백만개이므로 이중 반복문을 돌릴 경우 백만의 제곱만큼 시간 복잡도가 소요된다. 각설하고, 이 문제는 오큰수를 만나지 못한 인덱스를 스택에 넣어야 한다. 우선 0번째 인덱스..

알고리즘 문제 출처 : https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저� www.acmicpc.net 내가 작성한 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Stack; public class Main { pu..

알고리즘 문제 출처 : https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 � www.acmicpc.net 내가 작성한 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Stac..

알고리즘 문제 출처 : https://www.acmicpc.net/problem/10866 10866번: 덱 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 �� www.acmicpc.net 내가 작성한 코드 마지막 요소를 삭제할 때 pop()을 썼는데 자꾸 결과가 이상하게 나오길래 확인해봤더니 첫번째 요소를 삭제해주는 메소드였다. 그래서 pop()을 쓰지 않고 removeLast()를 사용해서 코드를 작성했다. import java.io.BufferedReader; import java.io.BufferedWriter; import jav..