chocho_log

[Java] 에라토스테네스의 체 - 소수 판별

[에라토스테네스의 체] - 가장 대표적인 소수 판별 알고리즘. 소수(Prime)이란 양의 약수를 1과 자기자신만 가지고 있는 자연수. - 대량의 소수를 빠르게 구하는 방법 * 일반적인 소수 판별 코드 (시간 복잡도: O(N)) boolean isPrime(int x) { for (int i=2; i < x; i++) { if (x % i == 0) { return false; } } return true; } [에레토스테네스의 체 동작 방식] ex) 1~25에서 소수 판별 1. 소수를 판별하고자하는 범위 크기의 배열을 정의하고 숫자들을 배열에 넣어준다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 2. 2부터 시작해서 특정 숫자의 ..

[백준][Gold1] 제곱ㄴㄴ수 - JAVA

[문제 설명] www.acmicpc.net/problem/1016 1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net 문제는 간단하지만 풀다보니 시간효율성을 통과하는 것이 까다로워 가히 Gold 레벨에 있는것이 납득이 가는 문제다. 문제를 읽고 일반 코드로 풀어보니 시간 초과가 나면서 통과하지 못했다. 에라토스테네스의 체 원리를 이용하여 된다. [JAVA code] package com.algorithm.baekjoon.silver5; import java.io.BufferedReader; imp..

[백준][silver5][JAVA] 1010-다리 놓기

[문제 설명] www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net [풀이 과정] M개 중에 N개 선택하여 조합하는 경우의 수를 구하는 문제다. 조합 경우의 수를 구하는 방법은 여러가진데 메모이제이션을 이용하면 가장 효율적으로 풀 수 있다. * 메모이제이션을 이용한 조합 경우의 수 구하기 - 메모이제이션(memoization) 기법은 동적 프로그래밍의(dynamic programming)의 일종이다. 메모를 할 배열을 만들어 놓고 처음 계산한 값은 배열에 저장한다..

[백준][silver4][JAVA]터렛

[문제 설명] www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net [풀이 과정] 조규현, 백승환 각 좌표와 떨어진 거리를 반지름으로 원을 그려보면 두 원이 만나는지 여부를 알 수 있다. 두 원이 만나는 접점의 개수가 류재명이 있을 수 있는 좌표의 개수이다. 총 6가지 경우가 있다. 1. 두 점에서 만남 한 점에서 만남 2. 외접 3. 내접 반지름의 차 r1 + r2) 5. 두 중점 거리 < 반지름의 차이 (d < r2 - r1) 6. 두 중점..

[프로그래머스][Level3][Java]징검다리 건너기

[문제 설명] programmers.co.kr/learn/courses/30/lessons/64062 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr [풀이 과정] 파라매트릭 서치(Parametric search)를 이용하여 푸는 문제다. 단순 코딩으로도 문제를 풀수는 있지만 파라매트릭 서치를 활용하지 않으면 효율성 체크에서 실패가 난다. 파라매트릭 서치는 이분탐색과 유사한 알고리즘으로 최적화 문제를 결정 문제로 바꾸어 푸는 것이다. * 최적화 문제 - 최적의 해가 무엇인가를 묻는 문제 - 주로 문제 상황을 만족하는 특정 변수의 최솟값, 최댓값을 구하는 문제 * 결정 문제 - 어떤 조건이 예-아니요로 답이 있는 문제 예시)..

[프로그래머스][Level3]셔틀버스 -JAVA

[문제] https://programmers.co.kr/learn/courses/30/lessons/17678 코딩테스트 연습 - [1차] 셔틀버스 10 60 45 ["23:59","23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59", "23:59"] "18:00" programmers.co.kr [풀이] 어떤 알고리즘을 알아야만 풀수 있는 문제가 아닌 문제에 주어진 상황을 코드로 구현할 수 있는지 보는 문제같다. 1. 큰 틀은 다음과 같이 구현했다. 1) 탑승객들을 빨리 도착한 시간 순서대로 줄 세운다(PriorityQueue 사용) ..

[프로그래머스][Level3][Java] 길 찾기 게임

[문제 설명] programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr [풀이 과정] 이진 탐색 트리(Binary Search Tree)의 개념을 확실히 알 고 있는지 보는 문제다. 1. 이진 탐색 트리를 만들 수 있는지. 2. 전위 순회(preOrder)로 이진 탐색트리를 조회 할 수 있는지. 3. 후위 순회(postOrder)로 이진 탐색트리를 조회 할 수 있는지. 풀이 과정은 다음과 같다. 1) 노드 클래스 만들기 이진 탐색 트..

이진 탐색 트리(Binary Search Tree)개념 및 Java 구현

이진 탐색 트리(Binary Search Tree) 다음과 같은 조건을 충족하는 이진 트리를 이진 탐색 트리라고 한다. ① 트리의 각 노드들은 반드시 키 값을 가지고 있다. 키 값은 모두 달라야 한다. ② 노드 N의 왼쪽 서브트리 모든 노드의 키 값은 노드 N의 키 값보다 작아야 한다. ③ 노드 N의 오른쪽 서브트리 모든 노드의 키 값은 노드 N의 키 값보다 커야 한다. 이진 탐색 트리 구현 이진 탐색 트리는 자료 구조 연결리스트를 활용한다. ✅ 준비단계. 노드 클래스 만들기 이진 탐색트리의 개별 노드를 나타내는 클래스이다. 다음과 같이 3개의 필드로 구성된다. ① Data: 실제 데이터가 들어가는 필드 ② Left: 노드의 왼쪽 서브 트리 ③ Right: 노드의 오른쪽 서브 트리 [Java code] ..

[프로그래머스][Level3][JAVA] 야근 지수

[문제 설명] programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr [풀이 내용] 야근 피로도(각 작업량 제곱의 합)이 최소가 되려면 가장 큰 수의 작업량부터 처리해야 한다. 완전탐색으로 정답이 될 수 있는 모든 경우의 수를 나열해 보았는데 최소작업량이 더 작은 것보다 최대작업량이 더 작은것이 야근피로도가 더 적었다. 이유는 큰 수와 작은 수가 1차이가 나더라도 제곱의 차이는 확 커지기 때문이다. 따라서 주어진 n..