반응형 Develop/Coding Test | Algorithm17 [알고리즘] 퀵정렬 Quick Function 퀵정렬 pivot을 이용해서 좌, 우측으로 정렬하는 기법 pivot은 맨 앞, 중간, 맨 뒤 등 임의로 설정할 수 있다. 평균 O(nlogn), 최악일 경우 O(n^2)의 시간 복잡도를 가진다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; class Main { public static int[] arr; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt.. 2024. 3. 14. [알고리즘] 해시 함수 (Hash Function) 해시 함수 자료의 저장, 탐색에 이용된다. 임의의 길이를 가진 데이터로 고정된 길이의 데이터를 출력한다. 서로 다른 문자열이더라도 동일한 해시 값을 가질 수 있다. ⏩ "abcde" + 해시 함수를 통한 별도의 값 -> 1235124 - 해시 충돌 방지를 위해 수열의 각 항마다 고유 계수를 부여한다. - 항의 번호에 해당하는 만큼 특정 숫자를 거듭제곱하고 더한다. - 임의의 값 M 으로 나누기 해당 알고리즘을 사용한 백준 풀이를 하고 싶다면 링크 참고 https://www.acmicpc.net/problem/15829 15829번: Hashing APC에 온 것을 환영한다. 만약 여러분이 학교에서 자료구조를 수강했다면 해시 함수에 대해 배웠을 것이다. 해시 함수란 임의의 길이의 입력을 받아서 고정된 길이.. 2024. 3. 12. [알고리즘] 유클리드 호제법 - 최대공약수 / 최소공배수 구하기 ▶️ 유클리드 호제법 : 유클리드 알고리즘, 최대 공약수 구하는 알고리즘 소인수분해 후 공통된 소수를 찾으면 된다. a, b를 나누어 떨어지게 하는 수 중 가장 큰 수 찾기 > 유클리드 알고리즘은 쉽게 말하면 MOD(나머지 구하기)라고 할 수 있다. ▶️예시 24와 18의 최대공약수(GCD) i) A = 24 / B = 18 인 경우 GCD(24, 18) -> GCD(18, 6) -> GCD(6, 0) = 6 a) 24 % 18 = 6 b) 18 % 6 = 6 (최대공약수) c) 6 % 6 = 0 278과 192의 최대공약수(GCD) ii) A = 278 / B = 192 인 경우 GCD(278, 192) -> GCD(192, 78) -> GCD(78, 36) -> GCD(36, 6) -> GCD(6, .. 2024. 3. 12. [백준] JAVA풀이 - 1978 : 소수 찾기 ▶️백준 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net ▶️답안 1은 소수가 아니다. 2부터 n 제곱근까지 확인하면서 소수인지 아닌지 판별한다. import java.util.Scanner; class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int count = 0; for (int i=0; i 2024. 3. 11. [백준] JAVA풀이 - 1157 : 단어 공부 ▶️백준 https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net Map, HashMap, Entry를 적절히 사용하며 문제 풀기 완료! 해당 백준 문제를 풀면서 Map.Entry 인터페이스 내 메서드를 공부할 수 있었다. -- Map 로 이루어진 인터페이스 Map.Entry 인터페이스 주요 메서드 Method Description Object getKey() Entry의 key 객체 반환 Object getValue() Entry의 value 객체 반환 boolean equals(Ob.. 2024. 2. 26. [백준] JAVA 풀이 - 10811 : 바구니 뒤집기 ▶️백준 https://www.acmicpc.net/problem/10811 10811번: 바구니 뒤집기 도현이는 바구니를 총 N개 가지고 있고, 각각의 바구니에는 1번부터 N번까지 번호가 순서대로 적혀져 있다. 바구니는 일렬로 놓여져 있고, 가장 왼쪽 바구니를 1번째 바구니, 그 다음 바구니를 2 www.acmicpc.net ▶️실패 답안 인텔리제이에서는 동작했지만 백준에서는 시간 복잡도를 고려하지 못해서 틀린 답안으로 제출되었다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public.. 2024. 2. 13. [백준] JAVA 풀이 - 5597 : 과제 안 내신 분..? ▶️ 백준 문제 https://www.acmicpc.net/problem/5597 5597번: 과제 안 내신 분..? X대학 M교수님은 프로그래밍 수업을 맡고 있다. 교실엔 학생이 30명이 있는데, 학생 명부엔 각 학생별로 1번부터 30번까지 출석번호가 붙어 있다. 교수님이 내준 특별과제를 28명이 제출했는데, www.acmicpc.net 처음에 두 배열을 비교해야겠다고 생각하고 차집합(removeAll)을 이용해서 문제를 풀었지만 해당 함수를 모를 경우를 대비해 다른 방법으로도 풀이가 가능해서 기록으로 남기고자 한다. ▶️ 차집합 풀이 import java.io.*; import java.util.ArrayList; import java.util.List; public class Main { publi.. 2024. 2. 12. [백준] JAVA 풀이 -10951 : A + B - 4 해당 백준 문제 풀이 중 제출했지만 런타임 에러가 발생해서 기록 겸으로 작성! ▶️ 백준 문제 https://www.acmicpc.net/problem/10951 10951번: A+B - 4 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 현재 내 풀이는 인텔리제이에서는 작동이 잘 되지만 백준에서 런타임 에러가 발생하는 상황이다... 🤔🤔 ▶️ 런타임에러(Null Pointer) import java.io.*; import java.util.StringTokenizer; public class Main { public static void main (String[] args) throws IOException { BufferedReader br =.. 2024. 2. 10. 이전 1 2 다음 728x90 반응형
