분류 전체보기
-
[백준]1038: 감소하는 수 - JAVA문제풀이/백준 2021. 3. 9. 21:00
문제 www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 풀이 처음에는 정직한 완전탐색 방법으로, 이전에 뽑은 수에 1씩 더해가며 감소하는 수 인지 판별하며 수를 찾았다. 이렇게 풀면 시간초과가 발생한다. 제일 첫 번째 뽑는 수를 기준으로 감소하는 수를 만들어서 list에 저장하고, list를 정렬하여 n번째 수를 반환하도록 하였다. 예를들어서 아래와 같당. 처음에 뽑는 수 다음에 올 수 있는 수 만들어 지는 수 1 0 10 2 1, 0 21, 2..
-
자료구조 - 해시테이블CS/자료구조 2021. 3. 8. 20:01
해시테이블 해시테이블 이란? Key, Value의 쌍으로 데이터를 저장하는 자료구조 중 하나로 빠르게 데이터를 검색할 수 있다. 내부적으로 배열을 사용하여 데이터를 저장하고, 각각의 key값에 해시 함수를 적용해 배열의 유일한 인덱스를 생성한다. 이 인덱스를 활용해 값을 저장하거나 검색하게 된다. 해시 함수 저장할 데이터의 key를 고유한 인덱스로 변환하여 해시 테이블에 저장하기 위해 사용되는 함수. 대표적 해시 함수로는 아래 4가지가 있다. Division Method: 입력값을 테이블의 크기로 나누어 계산한다. Digit Fording: key의 문자열을 아스키 코드로 바꾸고 값을 합한 데이터를 주소로 사용한다. Multiplication Method: 특정한 값을 사용해 연산을 하여 주소로 사용한다..
-
[백준]2023: 신기한 소수 - JAVA문제풀이/백준 2021. 3. 8. 18:51
[백준]2023: 신기한 소수 www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 N자리 수중에 소수를 모두 출력하는 DFS문제이다. 숫자를 자리수 별로 하나씩 뽑으면서 뽑았을 때 소수가 되는 경우만 수를 이어서 뽑는다. 뽑다가 N자리가 되는 순간 출력을 하도록 하였다. 소수를 판별하는 방법은 에라토스테네스의 접근 방식을 사용했다. 소수 판별식 코드는 아래와 같다. public static boolean isPrime(int num) { if(n..
-
[백준]9019: DSLR - JAVA문제풀이/백준 2021. 3. 7. 19:53
문제 www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 풀이 A를 B로 표현할 수 있는 최소한의 방법을 출력하는 것이므로 BFS를 사용하였다. 모든 경우에서 4가지 명령어를 실행하고 각각의 실행한 경우에서 또 명령어를 실행하도록 반복해 주었다. 이러다가 B가 되었을때 그때까지의 명령어를 반환하도록 하였다. 현재까지 사용된 명령어를 저장하기 위해서 Node 클래스를 사용해 주었다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15..
-
Network - RoutingCS/Network 2021. 3. 6. 19:37
Routing 라우팅? 출발지에서 목적지 까지 패킷을 전달하기 위한 모든 경로를 말한다. 다른 네트워크 장비와 통신할 때 반드시 필요하다. 라우팅 하기 위해선 출발지 목적지의 주소, 입출력 인터페이스 상태, 가능성 있는 모든 경로, 최적의 경로(라우팅 테이블)를 알아야 하며 지속적으로 네트워크 상태를 확인하고 유지해야 한다. 라우팅 테이블 라우팅 테이블에 최종 목적지 정보가 있어야 통신이 가능하다. 네트워크에 대한 정보가 들어있다. 직접 연결되지 않은 라우팅 테이블 간에는 별도의 방법으로 학습할 수 있다. 목적지의 정보를 학습하는 방법 1. Static Routing 관리자가 직접 정보를 입력하는 방법이다. 목적지로 가기 위한 이웃 라우터를 관리자가 지정한다. 장점) 리소스 소모량이 적고, 관리자가 원하..
-
[프로그래머스]입국심사 - JAVA문제풀이/프로그래머스 2021. 3. 5. 14:30
[프로그래머스]입국심사 programmers.co.kr/learn/courses/30/lessons/43238 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 풀이 심사를 받는데 최소로 소요되는 시간을 반환하는 문제로 소요되는 시간을 기준으로 이분탐색을 하였다. 우선 제일 오래 걸리는 심사위원을 알아내기 위해 times를 정렬해 주었다. 그리고 제일 오래걸리는 심사위원의 시간을 알아내어 최대 시간을 계산해 주었다. 이때 최대 소요 시간이란, 제일 오래걸리는 심사위원이 n명 모두를 심사할때 소요되는 시간이 되므로..
-
[백준]13023: ABCDE - JAVA문제풀이/백준 2021. 3. 4. 14:19
[백준]13023: ABCDE www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 모든 경우를 탐색하는 DFS탐색 문제로, A -> B -> C -> D -> E인 관계가 있다면 1을 출력, 아니면 0을 출력하는 문제이다. 위와 같은 연결 관계가 있다면 DFS탐색 깊이가 4가 되는 것을 이용하여 문제를 풀었다. 반복문을 사용하여 시작 순서를 돌아가면서 DFS탐색을 하였고, 탐색 깊이가 4가 되는 순간 1을 출력하고 프로그램을 종료했다. 1이 출력되면 그 이후에는 더 이상 탐색하지 않아도 되기 때문이다. 모든 DFS탐색 동안 1이 출력이 되지 않는다면 위와 같은 ..
-
[프로그래머스]야근 지수 - JAVA문제풀이/프로그래머스 2021. 3. 4. 13:53
문제 programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 풀이 works 배열의 원소에서 n만큼 뺀 값중 나머지에 대해 제곱의 합이 최소인 값을 찾는 문제이다. 제곱의 합이 최소가 되기 위해서는 works의 각 숫자들이 전체적으로 균형이 맞아야 한다. 예를 들어 첫 번째 예제 입력의 경우, works = {4, 3, 3}이고 n이 4이다. 이때 n시간을 모두 첫 번째 일을 처리하는데 사용하면 남는 시간은 0, 3..