java
[백준] 10757번 : 큰 수 A+B - JAVA [자바]
[백준] 10757번 : 큰 수 A+B - JAVA [자바]
2021.02.01www.acmicpc.net/problem/10757 10757번: 큰 수 A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 Java로 풀 경우 매우 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 참고로 일반적으로 큰 수를 쓸 때 쓰는 long형은 264-1으로 약 1844경 정도 된다. 하지만 이 번 문제의 경우 입력 범위가 최대 1010000 이므로 long형을 아득히 넘는다. 그러면 이를 어떻게 풀어야 할까? 크게 두 가지 방식이 있다. 먼저 덧셈 과정을 직접 구현하는 방법이 있다. 그리고 Java에서 제공하는 BIgInteger 클래스를 이용하는 방법이 있다. 이 번에는 이 두 방식 모두 보여주려고 한다. 먼저 덧셈을 구현하는..
[백준] 11866번 : 요세푸스 문제 0 - JAVA [자바]
[백준] 11866번 : 요세푸스 문제 0 - JAVA [자바]
2021.01.23www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 문제 알고리즘 [접근 방법] 큐를 이용한 매우 쉬운 문제다. 예제를 이해해보자면 이렇다. 1부터 N까지 나열 된 수에서 K번째 수 마다 차례대로 뽑아 낸 수열을 출력하는 것이다. 예제를 예로 들어보자. seq {1, 2, 3, 4, 5, 6, 7}, result {} round 1 : seq {1, 2, 3, 4, 5, 6, 7}, result {3} round 2 : seq {1, 2, 4, 5, 6, 7}, result {3, 6} round 3 : seq {1, 2, 4, 5, 7}, re..
[백준] 17298번 : 오큰수 - JAVA [자바]
[백준] 17298번 : 오큰수 - JAVA [자바]
2021.01.21www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 Stack의 원리를 이해하면 생각보다 그리 어렵지는 않다. 알고리즘 [접근 방법] 이 문제가 의외로 어떻게 스택을 활용해야할지 갈피를 못잡는 문제인 것 같다. 이중 for문을 사용하면 최대 1,000,000 * 1,000,000 = 1,000,000,000,000 (1조)으로 시간초과 날 것이 뻔하다. 스택의 기본 원리는 딱 한 가지만 기억하면 된다. '후입선출' 즉, 가장 최근에 들어온 것이 가장 먼저 나오는 것이다...
자바 [JAVA] - 거품 정렬 (Bubble Sort)
자바 [JAVA] - 거품 정렬 (Bubble Sort)
2021.01.18[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) 4. 거품 정렬 (Bubble Sort) - [현재 페이지] 5. 셸 정렬 (Shell Sort) 6. 힙 정렬 (Heap Sort) 7. 합병(병합) 정렬 (Merge Sort) 8. 퀵 정렬 (Quick Sort) 9. 이진 삽입 정렬 (Binary Insertion Sort) 10. 팀 정렬 (Tim Sort) Bubble Sort [거품 정렬] 거품 정렬은 아마 정렬 방식 중 가장 쉽게 생각할 수 있는 알고리즘 중 하나일 것이다. 두 개의 인접한 원소를 비교하여 정렬하는 방식이다. 왜 Bubble 이라는 이름이 붙었는지 찾아보니 정..
[백준] 1010번 : 다리 놓기 - JAVA [자바]
[백준] 1010번 : 다리 놓기 - JAVA [자바]
2021.01.18www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제 문제만 제대로 이해한다면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 문제는 매우 간단하다. 우선 문제에서 두 가지 포인트를 짚고 넘어가보자. 1. 한 사이트에는 한 개의 다리만 놓일 수 있다. 2. 서로 다른 다리가 겹치면 안된다. 즉, 위 그림처럼 첫 번째 같이 서로 겹치지 않게 다리를 놓는 경우 외엔 한 사이트에 두개의 다리가 놓이거나, 서로 다른 다리가 가로지르면 안된다. 그럼 무엇을 생각할 ..
[백준] 1934번 : 최소공배수 - JAVA [자바]
[백준] 1934번 : 최소공배수 - JAVA [자바]
2021.01.17www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 문제 바로 직전 문제인 '최대공약수와 최소공배수' 문제를 풀었다면 그리 어렵지 않게 풀 수 있었을 것이다. 알고리즘 [접근 방법] 이 문제는 유클리드 알고리즘으로 풀라고 나온 문제다. 즉, 유클리드 호제법(Euclidean algorithm)을 사용하라는 것인데, 앞서 필자가 이미 '최대공약수와 최소공배수' 문제를 풀이하면서 설명했다. '꼭 아래 포스팅을 먼저 보고 오시길 바란다' http:..
[백준] 13305번 : 주유소 - JAVA [자바]
[백준] 13305번 : 주유소 - JAVA [자바]
2021.01.13www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 설명이 조금 복잡해보이나 원리만 이해하면 정말 쉬운 문제다. 알고리즘 [접근 방법] 문제 설명이 길어서 그렇지 내용 자체가 어려운 문제는 아니니 먼저 문제부터 이해하고 넘어가보자. 먼저 N개의 도시가 있고, 각 도시를 잇는 N-1개의 도로가 있다. 그리고 각 도시에는 주유소의 리터당 가격이 써져 있고, 각 도로에는 거리가 적혀져 있다. (1km당 1L 기름을 사용함) 문제에 있는 예시를 보면..
[백준] 9184번 : 신나는 함수 실행 - JAVA [자바]
[백준] 9184번 : 신나는 함수 실행 - JAVA [자바]
2021.01.05www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 문제 문제가 어려운 편은 아니다. 주어진 조건에 따라 함수를 그대로 옮겨적고 메모이제이션만 추가하면 된다. 알고리즘 [접근 방법] 문제를 설명하기는 모호한데.. 일단 동적계획법의 특징은 대체로 재귀 + Memoization(메모이제이션) 이라는 것을 생각하면 된다. 위에서 설명한 조건에 따른 함수(재귀)호출은 코드로 보면 이렇다. static int w(int a, int b, int c) { if(a 20) { ..
[백준] 2164번 : 카드2 - JAVA [자바]
[백준] 2164번 : 카드2 - JAVA [자바]
2020.12.19www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 문제 큐에 대한 원리만 알고 있어도 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 이 번 문제같은 경우 자료구조를 한 번쯤 접해봤거나 큐에 대한 개념이 있다면 쉽게 풀 수 있는 문제다. 잠깐 큐에 대해 설명하자면 큐 자료구조의 경우 '선입선출' 자료구조로 말 그대로 먼저 들어간 요소가 먼저 나오는 방식이다. 쉽게 생각해서 놀이기구를 타기위해 줄서있는 모습을 생각하면 된다. 큐에 대한 자세한 내용과 구현은 아..
자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기
자바 [JAVA] - 연결리스트를 이용한 Deque (덱) 구현하기
2020.12.17자료구조 관련 목록 링크 펼치기 더보기 0. 자바 컬렉션 프레임워크 (Java Collections Framework) 1. 리스트 인터페이스 (List Interface) 2. 어레이리스트 (ArrayList) 3. 단일 연결리스트 (Singly LinkedList) 4. 이중 연결리스트 (Doubly LinkedList) 5. 스택 인터페이스 (Stack Interface) 6. 스택 (Stack) 7. 큐 인터페이스 (Queue Interface) 8. 배열 큐 (Array Queue) 9. 연결리스트 큐 (LinkedList Queue) 10. 배열 덱 (Array Deque) 11. 연결리스트 덱 (LinkedList Deque) - [현재 페이지] 12. 힙 (Heap) 13. 우선순위 큐 (..