반응형
알고리즘

알고리즘

    백준 4673번 셀프 넘버

    1 ~ 10000까지의 숫자중에 셀프 넘버가 아닌 데이터를 noSelfNumber에 집어넣고 loop를 순회하면서 selfNumber 여부를 체크하면 된다. 간단한 문제이다. https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다..

    백준 4936 - 섬의개수

    결국은 순회하면서 하는 DFS를 했는데 다음번에는 DP 또는 그래프 문제를 좀 많이 풀어 보고 싶다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126import java.util.*; public class Main { public static void main(String[..

    백준 알고리즘 2583 - 영역 구하기

    백준 알고리즘 2583번 영역구하기 문제는 DFS를 사용해서 구현해봤다. 문제지를 보자마자 읽기 싫어졌지만 읽어보면 되게 단순하게 많이 접해봤던 문제인거 같다. https://www.acmicpc.net/problem/258312345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612..

    백준 1929번 소수 구하기 문제

    일반적으로 소수 구하는 방식으로 진행하면 시간이 너무 걸려서 에러가 발생한다. 그래서 고민하던 중에이런 생각이 났다. 모든 수는 자신의 제곱근 이상의 수로 나눠지지 않기 때문에 자신의 제곱근까지 2이상의 자연수로 나눠지는지 판단하면 된다고 생각했다. 그 결과 된다.1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556import java.math.BigDecimal;import java.util.ArrayList;import java.util.List;import java.util.Scanner; public class Main { public static void main(..

    백준 알고리즘1032 명령프롬프트 문제

    문제입력된 파일 리스트를 보고 공통적으로 사용될 수 있는 Regex를 찾아서 출력하는 문제이다. 코드 코드는 간단하게 처음입력받은 파일명을 기준으로 잡고 추가로 들어오는 나머지 파일명들과 다른 부분에 대해서 모두 ?로 바꿔버렸다. 12345678910111213141516171819202122232425262728293031323334353637import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 파일 개수 입력 int wordCnt = sc.nextInt(); // 첫 번째 파일이름 char[] creteria = sc.next()..

    백준 알고리즘 11650 - 좌표 정렬하기

    문제 입력된 좌표를 정렬해서 보여주는 문제이다. 코드 좌표를 담는 하나의 DTO 객체를 만들어서 comparable을 정의해서 사용해도 되나 좀 다르게 해보고 싶었다. 각 x좌표를 키로 사용하는 map을 만들고 각 x좌표마다 y좌표들을 담는 리스트가 존재한다. y좌표값이 채워질때는 정렬이 된 상태로 삽입된다. insertSort 메소드는 ATM 알고리즘에서 사용했던 것 가져왔다. 그리고 Map을 출력할 때는 Key를 기준으로 정렬한 후 forEach를 사용하여 정렬한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354import java.util.*; public class ..

    백준 알고리즘 11399 ATM 문제

    문제 이번 알고리즘 문제는 최소 ATM 사용시간을 구하는 문제이다. 주어진 사람마다 ATM 사용시간이 주어진다. 이 사용시간에 따라 어떻게 사람이 서있을 때 빠르게 모두 ATM 을 사용할 수 있는지 구하는 문제이다. 각 사람마다 걸리는 시간을 모두 더해서 가장 최소의 시간이 나오게 하는 구현하는게 목표이다. 가장 빠르게 모두 인출이 끝나기 위해서는 사용시간이 가장 작은 사람 부터 큰 순서대로 서서 인출을 해야한다. 왜냐하면 뒤에 있는 사람이 인출하는데 걸리는 시간은 결국 앞사람이 사용한 시간의 누적값이기 때문이다. 코드소요시간 별로 오름차순으로 정렬한 후 에 합을 구하면 된다. 그러기 위해서 모든 데이터를 입력받고나서 가장 시간 복잡도가 낮은 퀵정렬을 사용하면하면 되지만 그냥 데이터가 삽입되는 순간에 삽..

    백준 1094 막대기 문제

    문제 내용 https://www.acmicpc.net/problem/1094소스코드자세한 소스는 참고 https://github.com/weduls/algorithm/tree/master/%EC%8B%9C%EB%AE%AC%EB%A0%88%EC%9D%B4%EC%85%98/%EB%A7%89%EB%8C%80%EA%B8%B0 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768import java.util.Scanner;import java.util.Stack;import java.util.stream.IntStream; public cl..

    백준 알고리즘 4150번 피보나치 수 문제

    저번에 공부한 BigInteger를 응용하여 알고리즘 문제를 풀어보자. 이번문제는 피포나치 수열을 해결하는 문제이다. 저번에 포스팅 했었던 피보나치 수열을 구하는 방법은 재귀와 DP 그리고 반복문이 있다. 이번 문제는 반복문을 사용하여 구해보자. 위에 문제를 보면 데이터의 결과 크기가 Long의 범위를 벗어난다. 그렇기 때문에 데이터를 담기위해서 BigInteger를 사용하였다. 생각보다 문제는 간단하나 여러가지 경우를 정리 할 수 있었서 좋았다. 1234567891011121314151617181920212223242526272829303132333435363738394041package test; import java.math.BigInteger;import java.util.ArrayList;imp..

    [공유] 시간 복잡도와 공간복잡도 정리

    시간복잡도와 공간복잡도 관련하여 많이 잊어먹어서 정리된 사이트를 공유합니다. https://joshuajangblog.wordpress.com/2016/09/21/time_complexity_big_o_in_easy_explanation/

    백준 6603번 로또 문제 풀이

    매주 진행중인 알고리즘 공부 중 오늘은 백준 6603번 DFS와 백트래킹 문제를 풀어보자. #문제 https://www.acmicpc.net/problem/6603#풀이과정사용자로 부터 로또번호를 생성할 번호의 개수 k를 입력받고 입력받은 k개의 숫자를 이용하여 로또를 오름차순으로 6개짜리 배열을 만들어 출력해야한다. 처음에 문제를 보자마자 재귀를 써야겠다는 생각은 하였지만 백트래킹을 써야하는지는 감이 오지 않아서 고민을 많이 했다. 시작점을 0번째 부터 로또를 딱 만들수 있는 크기인 k - 5번까지 사용하는 반복문을 만들어서 배열을 만든다. 그리고 findLottoNum 메소드에 현재 인덱스와 만들고 있는 String값을 전달해준다. 그럼 현재 인덱스 바로 앞에 위치할 숫자를 구해서 String에 붙혀..

    백준 알고리즘 10988번 문제 팰린드롬 문제 풀기

    팰린드롬은 단어를 앞뒤로 거꾸로 했을 때 동일한 단어를 이야기한다. 코드가 아주 간단하다.입력받은 String 길이의 반만큼 반복문을 돌면서 앞과 뒤가 맞는지 체크하고 앞에서오는 인덱스 i와 뒤에서 오는 인덱스 j가 서로 교차하는 순간까지 서로 다르지 않으면 1을 반환하고 체크하던 도중에 한부분이라도 같지 않으면 0을 반환하면 된다.자세한 코드는 아래 또는 github에서 확인 가능하다. 12345678910111213141516171819202122232425262728293031323334package test; import java.util.Scanner; public class WedulPlindrom { public static void main(String args[]) { Scanner sc..

    피보나치 수열 재귀, DP, loop 방법으로 구현하고 차이 확인

    피보나치 수열을 이용한 재귀 프로그래밍은 대학교 1학년때 처음 재귀를 구하면서 접했었다. 당시에는 재귀의 예제로써 피보나치와 팩토리얼함수를 구현하는 것으로 소개되었다.하지만 시간복잡도에 대해 다시 공부하던 중 우리가 배웠던 피보나치 수열의 재귀는 좋은 방식이 아니라는 것을 알게되었다. 피보나치 수열의 3가지 방식에 대해 구현해보고 차이를 느껴보자. 우선 피보나치 수열은 현재 값을 구하기위해서는 이전의 값(n-1)과 그 더 이전의 값(n-2)을 더하면서 구한다.N = (n - 2) + (n -1)0, 1, 1, 2, 3, 5, 8, 13, 21, 34........ 1) 재귀방식재귀로 구현하는 방식은 가장 익숙한 방법이지만 매번 구할 때 마다 처음까지 가야하는 가장 안좋은 BigO(2^n)의 시간 복잡도를..

    백준 알고리즘 2167 2차원 배열의 합 DP 알고리즘으로 풀기 (JAVA)

    알고리즘 문제를 계속해서 연습해야겠다고 생각한 시점에서 백준 알고리즘 2차원 배열문제를 풀어보기로 했다. 문제는 간단하게 말하면 2차원 배열이 주어졌을 때, 특정 i, j 위치에서 x, y위치 까지의 value들의 합을 구하는 문제이다. 나는 특정 알고리즘을 생각하지 않고 단순하게 접근해서 array에 value를 다 넣어놓고 1,1에서 2, 3 까지 value를 구하라고 하면 1,1에서 2,3까지 반복문을 돌면서 value를 다 더했었다. 하지만 그렇게 하는게 아니라 DP 알고리즘을 사용해야 한다고 한다. 우선 자세한 문제는 백준 홈페이지에서 확인하시면 된다. https://www.acmicpc.net/problem/2167 그리고 먼저 말했던 단순하게 접근한 코드는 다음과 같다. 1 2 3 4 5 6..

    규칙 55 - 신중하게 최적화하라

    모든 프로그래머가 알아둬야 하는 최적화에 관련된 격언이 있다. 1. 맹목적인 어리석음을 비롯한 다른 어떤 이유보다도, 효율성이라는 이름으로 저질러지는 죄악이 더 많다. 2. 97%는 효율성을 잊어버려라. 섣부른 최적화는 모든 악의 근원이다. 그리고 프로그램을 작성하면서 기준을 삼아야 할 내용에 대해 소개한다. [기준] 빠른 프로그램을 만들려고 처음부터 노력하지말고, 좋은 프로그램을 만들려 노력하라. -> 좋은 구조를 가진 프로그램은 빠른게 변경하는데 어렵지 않다. -> 정보은닉의 원칙을 지키는 것이 좋은 구조를 갖는것에 첫 번째 항목이다. 설계를 할 떄는 성능을 제약할 가능성이 있는 결정들을 피하라. -> 특히 통신 API, 프로토콜 정의서는 변경하기 어렵기 때문에, 신중하게 코딩해야한다. API를 설계..

    정렬알고리즘 - 버블정렬

    1234567891011121314151617for(int i = money.length; i>0; i--){ for(int j=0;jmoney[j+1]){ temp=money[j]; money[j]=money[j+1]; money[j+1]=temp; } } }Colored by Color Scriptercs

    정렬알고리즘 - 삽입정렬

    12345678910111213141516171819202122232425262728 for(int i=0;i

    정렬알고리즘 - 선택정렬

    1234567891011121314151617181920212223242526272829for(int i = 0; i

    10진수 2진수 변환

    1234567891011121314151617181920212223242526272829303132package java8; import java.util.Scanner; public class MainClass { public static void main(String args[]) { Scanner in = new Scanner(System.in); StringBuilder result = new StringBuilder(); int input; System.out.print("10진수를 입력하세요. : "); input = in.nextInt(); //10 -> 2진수 while (input != 1) { result.insert(0, String.valueOf(input % 2)); input =..

    백준 1924 - 요일 맞추기

    12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879import java.util.Scanner; @SuppressWarnings("resource")public class Main { enum YOIL { MON, TUE, WED, THU, FRI, SAT, SUN } public static void main(String args[]) { Scanner sc = new Scanner(System.in); int x = sc.nextInt(); int y = sc.nextInt(); if (..

    백준 2839 - 설탕 배달

    1234567891011121314151617181920212223242526import java.util.Scanner; public class Main { public static void main(String args[]) { int n = new Scanner(System.in).nextInt(); int three = 0, int five = n / 5; int n %= 5; while (five >= 0) { if (n % 3 == 0) { three = n / 3; n %= 3; break; } five--; n += 5; } if (n==0) { System.out.println(five + three); } else { System.out.println(-1); } }}Colored by..

    Stack을 이용한 문장 완성도 판별 프로그램

    개발을 진행하다보면 기본에 대해 잊어갈때가 있다. 잊지 않기위해 오늘 부터 매주 하나씩 자료구조를 이용한 문제를 풀어봐야겠다. 오늘은 Stack 첫번째 시간으로 문장의 완성도를 확인하는 프로그램을 작성하여 보자. [제약사항] - {[(에 대한 괄호들이 정상적으로 닫혀있어야 한다. - 주석 //, /* 안에 포함된 내용은 무시한다. - "" double quote에 들어있는 내용을 무시한다. 간단한 프로그램이라 설명은 생략한다. - Text를 읽고 판별을 진행하는 Main 클래스 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686..

    Stack - 후위 표기법으로 된 식 계산

    1 3 + 4 * 와 같이 후위 표기되어있는 식을 계산하는 프로그램을 stack을 이용해서 만들어라 주의사항 - 피연산자가 너무 많으면 오류를 발생시켜라. - 피연산자가 적어도 오류를 발생시켜라 - 연산자가 사칙연산 이외의 것이 나오면 예외를 발생시켜라 - 결과는 소수점 둘째까지 반올림해서 표현하라. - 예외는 이 프로그램을 위한 예외를 새로 만들어라 구성 - 파일을 읽는 메서드가 담긴 util 클래스 - 동작이 진행되는 Main 클래스 - 이 프로그램의 예외 OperatorException 클래스 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626..

    선택정렬, 버블정렬, 삽입정렬 예제

    선택정렬 for(int i = 0; i

반응형