공부하는 블로그

5052번: 전화번호 목록 문제 전화번호 목록이 주어진다. 이때, 이 목록이 일관성이 있는지 없는지를 구하는 프로그램을 작성하시오. 전화번호 목록이 일관성을 유지하려면, 한 번호가 다른 번호의 접두어인 경우가 없� www.acmicpc.net 전화번호 목록 중 한 번호가 다른 번호의 접두어가 되는지 판단하는 문제이다. import java.util.Arrays; import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int tc = sc.nextInt(); for (int i = 0; i < tc; i++) { int n = sc.nextInt(); S..

Hash Table 해시 테이블(Hash Table)은 자료의 탐색을 위한 알고리즘으로 탐색 키워드인 Key와 그에 대한 결과 값인 Value가 한 쌍으로 저장된 자료구조이다. 해시 테이블은 해싱(Hashing)을 통해 Key 값에 알맞은 Value를 찾아낸다. Hashing? 해싱은 Key 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의 주소를 계산하여 항목에 접근한다. 해싱에서 자료를 저장하는 데 배열을 사용한다. 배열은 원하는 항목이 저장된 인덱스(index)를 알고 있을 경우 O(1)의 시간 복잡도로 매우 빠르게 자료를 삽입하거나 꺼낼 수 있다. 배열의 인덱스는 0부터 시작하는 정수로 문자열인 Key를 통해 배열로 저장된 Value에 접근하기 위해서는 해시 함수(Hash Func..

Queue? 컴퓨터의 기본적인 자료 구조의 한가지로, 먼저 집어 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 구조로 저장하는 형식을 말한다. 나중에 집어 넣은 데이터가 먼저 나오는 스택과는 반대되는 개념이다. Queue Method · add() : 리스트의 끝 부분에 새로운 요소를 추가한다. · remove() : 리스트의 첫 번째 항목을 제거한다. · peek() : 큐에서 가장 위에 있는 항목을 반환한다. · isEmpty() : 큐가 비어 있을 때에 true를 반환한다. Queue Code(JAVA) import java.util.ArrayList; import java.util.List; class MyQueue { private List que = new ArrayL..

Stack? 스택(Stack)은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형구조(LIFO - Last In First Out)로 되어있다. 자료를 넣는 행위를 푸시(Push), 넣어둔 자료를 꺼내는 행위를 팝(Pop)이라고 한다. *LIFO : 나중에 넣은 값이 가장 먼저 나오는 것을 LIFO 구조라 한다. 스택은 프로그래밍 언어마다 라이브러리로 구현되어 있지만 직접 사용자가 연결 리스트를 이용하여 구현해낼 수도 있다. Stack Method · pop() : 스택에서 가장 위에 있는 데이터를 제거한다. · push() : 스택의 가장 위에 데이터를 추가한다. · peek() : 스택의 가장 위에 있는 항목을 반환한다. · isEmpty() : 스택이 비어있을 때에 true를 반환한다. Stack C..

10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다. n=17일때 까지 피보나치 수를 써보면 다음과 같다. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 n이 주어졌을 때, n번째 피보나치 수를 구하는 www.acmicpc.net 재귀함수를 이용하여 n번째 피보나치 수를 구하는 문제이다. import java.util.Scanner; public class Main { public static void main(Strin..

1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) www.acmicpc.net 에라토스테네스의 체의 원리를 이용하여 소수를 구하는 문제이다. 이전에 풀었던 방식으로 풀면 시간초과가 난다.. import java.util.ArrayList; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = sc.nextInt(); ArrayList primeList = new ArrayList(); primeList.add..

1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 입력 받은 수가 소수인지 아닌지 판별하는 문제이다. 소수란 1보다 큰 정수 중 1과 자기자신으로만 나누어 떨어지는 수이다. (1은 소수가 아님) import java.util.Scanner; public class Main { static boolean isPrime(int num) { if(num == 1) return false; int w = 2; while(w < num) { if(num % w == 0) { return false; } w++; } return true; } public static void main(St..

2869번: 달팽이는 올라가고 싶다 문제 땅 위에 달팽이가 있다. 이 달팽이는 높이가 V미터인 나무 막대를 올라갈 것이다. 달팽이는 낮에 A미터 올라갈 수 있다. 하지만, 밤에 잠을 자는 동안 B미터 미끄러진다. 또, 정상에 올라간 후에는 미끄러지지 않는다. 달팽이가 나무 막대를 모두 올라가려면, 며칠이 걸리는지 구하는 프로그램을 작성하시오. 입력 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) 출력 첫째 줄에 달팽 www.acmicpc.net 달팽이가 나무를 오르는데 얼마나 걸리는지 구하는 문제이다. import java.util.Scanner; public class Main { public static void main(St..