본문 바로가기

분류 전체보기

[백준 알고리즘 -11722] 가장 긴 감소하는 부분 수열 - java (Collections.reverse(), Java 8 Stream API) int[] 뒤집기 (Collections) feat. 백준 11722문제풀다보면 Arrays나 Collections의 도움을 참 많이 받게 되는데,간단한 sort는 따로 정리할 것도 없지만, 요론건 또 정리해줘야 기억날듯하다.int형 배열을 뒤집으려면 간단하게는 새로운 배열을 생성해서 하나하나 for문 돌릴 수 있겠지만,사람이 또 뭔가 그런 방법말고 다른 방법 없나 찾고싶고 그런 마음이 있다ㅎㅎㅎㅎㅎ JAVA 8에서 Stream API로 Object[]로 바꿔서 반환해주는게 있긴 하던데, Object[]를 또 int[]로 바꾸기 한참 걸려서 패스 하고,Collections를 사용하기로 했다. 물론 List를 int[]로 바꾸는데 활용하긴 했음 사실 Arrays에서 reverse메소드를 제공해주면 참 쉬워.. 이론/문제풀이 2018. 9. 24.
[Java] Thread in java(간단 사용 예제) Thread in javaThread 클래스를 상속받는 방법쓰레드의 실행은 Thread.start() 메소드를 실행시킴으로써 할 수 있고, 이 때 쓰레드 클래스의 run()이 호출된다. 즉, run() 오버라이딩 메소드안에 수행할 작업을 구현해야한다.​ public class ThreadTest extends Thread{ int arg; public ThreadTest(int arg) { this.arg=arg; } @Override public void run() {//Thread.start()시 실행되는 함수, System.out.println("Thread Start: "+this.arg); try { Thread.sleep(1000); }catch(Exception e) { e.printStac.. 이론/알고리즘&자료구조&Java 2018. 9. 20.
[백준 알고리즘 - 1946] 신입사원 - java 문제 조건: 채용되기 위해서는 서류 심사 성적과 면접 심사 성적 둘 중 하나는 다른 어떤 사원보다 높아야 한다. = 서류 심사 성적과 면접 심사 성적이 둘 다 낮은 신입 사원이 한 명이라도 존재하면 신입사원으로 채용될 수 없다문제 해결 과정: 1) 하나하나 모두 비교하면 O(N^2) -> 10000000000 이기 때문에 제한 시간을 넘어간다. 2) 한 명의 지원자를 대상으로 채용여부를 검사할 때, 그 사원의 서류 점수보다 높은 지원자들과의 면접 점수만 비교하면 된다.Key 1) 서류 심사 등수 순으로 정렬한다(반대의 경우도 가능) 2) 면접 등수는 서류 심사 등수가 현재 검사하는 지원자보다 높은 지원자들 중 가장 높은 등수랑만 비교하면 된다. 즉, 반복문을 돌면서 max값을 업데이트 하면 O(1) 로 .. 이론/문제풀이 2018. 9. 18.
[백준 알고리즘 1464] 1로 만들기 - java(Dynamic Programming) 다이나믹 프로그래밍을 푸는 첫 번째 과정은 DP[n] (또는 k차원의 배열]이 무엇인지를 정의하는 것이다. 일반적인 문제는 그대로 정의하면 된다. 이 문제에서는, dp[n] = n을 1로 만드는 최소한의 연산의 수 라고 생각할 수 있다. 또, dp[n]은 dp[n-1]+1, dp[n/2] +1, dp[n/3] +1 중 하나이고, 이전 단계 즉, N-1 또는 N/2 또는 N/3 을 1로 만드는 최소한의 연산의 수 라는 조건을 만족한다면, N을 1로만드는 최소한의 연산의 수라는 조건도 만족한다. 간단한 문제이기 때문에 바로 코드, Top-Down 방식으로 재귀 호출로 구현한 코드이다. d배열에 메모를 하는 방식이다. 문제는 충분히 시간 안에 해결할 수 있지만 재귀 호출의 오버헤드 문제 때문인지 Bottom-.. 이론/문제풀이 2018. 9. 12.
[LocalDate - JAVA 8] LocalDate 정리 java.util.date 로 쩔쩔 고생했던게 엊그제 같은데 진작 8로 갈아탈걸 그랬다. 그것도 모르고 java.jodal.LocalDate로 개발했넹 자주 사용할 법한 것들만 정리하였다.레퍼런스 -> https://docs.oracle.com/javase/8/docs/api/java/time/LocalDate.html LocalDateTime은 여기에 따로 추가하도록 하겠당당Java 8부터 새로 생긴 java.time.LocalDate로 날짜 표현하기현재 날짜 반환 LocalDate localDate=LocalDate.now(); System.out.println(localDate.toString());//(현재기준)2018-09-11 출력 현재 날짜의 다양한 요소 반환 System.out.printl.. 이론/알고리즘&자료구조&Java 2018. 9. 11.
[백준 알고리즘 - 2632] 피자판매 - java/완전탐색(재귀호출) 진짜 전혀 어려울 것 없는 문제였는데, 조건문 계속 삽질하고 예외케이스 하나 계속 못찾아서 4시간 걸렸다 ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 발전좀하자!! 제발! A, B에 대한 부분집합을 각각 구해준 뒤 하나씩 합해서 경우의 수를 세면 되는 문제인데, 첫 번째 신경써야 할 부분은 1. "연속된" 원소만 더해야 할 것 -> 따라서 최대 1000000개이기 때문에 완전탐색이 가능하다 -> 난 여기에 추가로 S가 넘지 않으면 아예 탐색을 종료하도록 구현하였다. 아주 조금이라도 시간을 줄이겠다는 욕망 ,,? 2. 둘 중 하나는 아예 담지 않아도 되게 할 것 -> 0을 추가해준 뒤 오름차순 정렬해주면 쉽게 처리 가능하다. 3. 배열에 담았을 시 맨 뒤를 담으면 끝나는 것이 아닌 맨.. 이론/문제풀이 2018. 9. 9.
[백준 알고리즘 - 1208] 부분집합의 합 2 - java/재귀호출 크기가 n인 집합이 주어졌을 때, 그 부분집합의 갯수는 2^n이다. 이 문제에서 최대 N은 40이기 때문에 2^40=1.0995116e+12 어느정도인지는 모르겠고, 1초 안에 해결할 수 없는 크기인건 알겠다. 따라서 이 문제는 분할하여 풀어야한다. 2^20은 약 1000000으로 1초안에 계산할 수 있기 때문에 주어진 집합을 반으로 쪼개어서 각각 구한 후 풀이한다. 풀이과정은 다음과 같다. [ A, B, C, D, E, F ] 집합이 주어졌을 때, [ A, B C ] [ D, E, F ] 로 쪼갠다. 분할된 두 집합의 부분집합을 구한 후(공집합 포함) 두 분할을 활용하면 문제를 풀이할 수 있다. 여기서 공집합을 포함하는 이유는 앞의 부분집합의 공집합을 선택할지라도 뒤에서 공집합이 아닌 집합을 선택하면 .. 이론/문제풀이 2018. 9. 6.
[백준 알고리즘 - 1261] 알고스팟 (java, BFS) 가중치가 있는 그래프 문제라고 할 수 있다. 일반적으로 가중치가 있는 그래프 문제는 BFS로 풀 수 없지만0과 1로만 구성되어있는 경우에는 예외적으로 BFS로 해결이 가능하다. 0인 곳으로 이동할 때는 dist를 증가시켜주지 않고, 1인곳으로 이동할 때는 dist를 증가시켜 주는데두 vertex를 구분짓기 위해 DEQ를 사용하였다 무조건 나중에 삽입한 vertex를 사용한다고 정한다면 0인 곳은 Last에 삽입하고 1인 곳은 First에 삽입함으로써 0인 곳을 먼저 방문하도록 설정할 수 있다 0인 곳을 모두 방문하였다면 별도의 설정 없이도 다음 1인 곳을 탐색하게 된다 상태 저장 변수는 check와 dist를 활용하였다. import java.io.BufferedReader; import java.io... 이론/문제풀이 2018. 9. 4.

티스토리툴바