Nirsa's Learning Lab

[Algorithm] 시간 복잡도 정리 입력 제한에 따라 어떠한 알고리즘을 사용할지 정할 수 있는데 이는 아래와 같습니다. n

문제 링크 : https://school.programmers.co.kr/learn/courses/30/lessons/72410 [프로그래머스 Lv1] 신규 아이디 추천 아래와 같은 단계들의 유효성 검사를 통과하며 문자열을 다루는 문제입니다. 1단계 new_id의 모든 대문자를 대응되는 소문자로 치환합니다. 2단계 new_id에서 알파벳 소문자, 숫자, 빼기(-), 밑줄(_), 마침표(.)를 제외한 모든 문자를 제거합니다. 3단계 new_id에서 마침표(.)가 2번 이상 연속된 부분을 하나의 마침표(.)로 치환합니다. 4단계 new_id에서 마침표(.)가 처음이나 끝에 위치한다면 제거합니다. 5단계 new_id가 빈 문자열이라면, new_id에 "a"를 대입합니다. 6단계 new_id의 길이가 16자 이..

문제 링크 : https://www.acmicpc.net/problem/14916 [백준] 14916번: 거스름돈 (실버5, 그리디 알고리즘, JAVA) count 변수를 선언하여 최종적으로 출력한 동전의 최소 개수를 구합니다. while true를 사용하여 무한루프를 실행시키고, 각각의 조건식은 다음과 같습니다. N%5 == 0 && N != 0 5로 나누어 떨어지고, N이 0이 아닐 경우에는 count를 증가시키고 N에서 5를 감소시킵니다. N/2 >= 1 N의 값에서 2를 나눳을 때 최소 1번 이상 나누어질 경우 count를 증가시키고 N에서 2를 감소시킵니다. N != 0 N의 값이 0이 아닐 경우 -1를 출력하고 반복문을 종료합니다. 그 외의 경우에는 N에 대한 모든 계산이 끝나고 나누어 떨어지..

문제 링크 : https://www.acmicpc.net/problem/14659 [백준] 14659번: 한조서열정리하고옴ㅋㅋ (브론즈1, 그리디 알고리즘, 50%~53% 시간초과, JAVA) 문제의 요약은 아래와 같습니다. "자신보다 낮은 봉우리에 서있는 적들만 처치할 수 있게 되었다" → 현재 위치의 값보다 오른쪽의 값이 낮다면 적을 처치함 "출발한 봉우리보다 높은 봉우리를 만나면 그대로 공격을 포기" → 오른쪽 값이 높다면 그 이후의 값은 보지 않음 "모든 용들은 오른쪽으로만 나아가며" → 오른쪽의 값만을 확인 "봉우리의 높이는 중복 없이 유일하다." → 같은 높이의 값을 존재하지 않음 처음에 시도할 때의 코드인데, 각각의 값들을 비교하고 오른쪽의 값이 더 낮다면 적을 처치(kill)하고, 더 높은..

[Algorithm] 완전 탐색, 브루트포스 알고리즘 (Brute Force) 완전 탐색, 브루트포스 알고리즘은 이름 그대로 모든 경우를 탐색하여 답을 도출하는 알고리즘입니다. 이러한 특징 때문에 정답을 당연히 찾아 맞출수는 있지만, 모든 경우를 탐색하는 만큼 정답이 도출될 때 까지의 시간은 장담할 수 없는 큰 단점이 있습니다. 즉, 시간 복잡도가 매우 큽니다. 즉, 만약 123456789라는 정답이 있을 경우 아래와 같이 동작하게 되는 알고리즘 입니다. 숫자 1 탐색 숫자 2 탐색 숫자 3 탐색 .... 숫자 123456787 탐색 숫자 123456788 탐색 숫자 123456789 탐색 후 정답 도출 이러한 특징으로 인해 브루트포스 알고리즘의 경우 대부분 무한 루프, 중첩되는 for문과 if문을 조합..

문제 링크 : https://www.acmicpc.net/problem/1145 [백준] 1145번: 적어도 대부분의 배수 (브론즈1, 브루트포스 알고리즘, JAVA) 해당 문제는 입력받은 5개의 숫자 중, 3개 이상이 공통적으로 가지는 배수를 찾아내는 브루트포스(완전탐색) 문제 입니다. 우선 사용자로부터 입력받은 후 오름차순으로 정렬하고 최솟값을 가지는 0번 인덱스에서 부터 무한루프를 사용하여 탐색을 시작합니다. public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuil..

문제 링크 : https://www.acmicpc.net/problem/1253 [백준] 1253번: 좋다 (골드4, JAVA) 우선 아래의 코드를 사용하여 사용자로부터 입력을 받고 배열로 변환 합니다. 단, 문제를 풀 때 수월하게 풀기 위해서 따로 원본 배열과 사본 배열을 생성하고 사본 배열을 오름차순 정렬하였습니다. BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int N = Integer.parseInt(br.readLine()); String input = br.readLine(); sb.append(input); // 스트링 배열로 변환 S..

문제 링크 : https://www.acmicpc.net/problem/11399 11399번: ATM (실버4, JAVA) 사용자가 입력한 값을 String 배열로 받고 int 배열로 변환 후, 필요한 시간의 최솟값을 구해야하기 때문에 오름차순으로 정렬합니다. import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int[] arr = new int[N]; sc.nextLine(); String[] str = sc.nextLine().split(" "); ..

문제 링크(2839) : https://www.acmicpc.net/problem/2839 문제 링크(10162) : https://www.acmicpc.net/problem/10162 [백준] 2839번: 설탕 배달 (실버4, JAVA) 봉지의 최수 개수(divide)를 선언하고 사용자의 입력(N)을 받은 후 dfs 메소드를 호출합니다. public class Main { int divide; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); Main main = new Main(); main.dfs(N); } 문제에서 주어진 내용에서 중요한 부분은 `최대한 적은 봉지를 들고..

문제 링크 : https://www.acmicpc.net/problem/2720 [백준] 2720번: 세탁소 사장 동혁 (브론즈3, JAVA) 아래의 코드는 dfs 메소드를 구현하기 전 입니다. 거스름돈을 몇개 받았는지 확인할 쿼터, 다임, 니켈, 페니의 인스턴스 변수를 생성하고, 사용자로부터 테스트 케이스 수(T)와 거스름돈(C)를 입력받고 dfs 메소드를 실행합니다. public class Main { int quarter; int dime; int nickel; int penny; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); Main main = new Main();..