전체 카테고리
자바 [JAVA] - 이진 삽입 정렬 (Binary Insertion Sort)
자바 [JAVA] - 이진 삽입 정렬 (Binary Insertion Sort)
2021.08.01[정렬 알고리즘 모음] 더보기 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) Binary Insertion Sort [이진 삽입 정렬] 이번 포스팅의 경우 삽입 정렬을 토대로 하기에 반드시 삽입 정렬을 먼저 보고 오시기를 바란다. 만약 필자의 정렬 알고리즘을 시리즈로 보았다면 왜 퀵 정렬 다음에 이진 ..
블로그 사용 설명서
블로그 사용 설명서
2021.07.25@github : kdgyun @E-mail : stlab.strangers@gmail.com 안녕하세요. ST입니다. 블로그를 시작한지 벌써 약 1년 6개월이 지나버린 시점에 제가 늦게나마..(너무 늦었지만) 제 블로그를 처음 오시는 분들을 위해 제 블로그 소개를 하고자 합니다. 아무래도 어떤 글들이 어디에 있는지 찾기 어려우실 수도 있고, 뭐하는 블로그인지 궁금하실 수도 있어 이렇게 적어봅니다 :) Intro. 블로그 소개 ㅡ 일단, 블로그 이름부터 설명드려야 겠네요. 정식 명칭까지는 아니지만, 제 블로그 이름은 "Stranger's lab" 입니다. 블로그의 주요 내용은 알고리즘, 자료구조, 그 외 프로그래밍에 도움이 될 법한 사소한 것들이 주를 이루며, 아직까진 Java언어와 C++언어를 중점적으..
[백준] 10818번 : 최소, 최대 - [C++]
[백준] 10818번 : 최소, 최대 - [C++]
2021.07.23https://www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 1차원 배열 카테고리의 첫 문제다. 그리 어려운 것은 아닌지라 쉽게 푸실 수 있을 것이다. 알고리즘 [접근 방법] 배열에 대해 이미 알고있다면 이 문제는 그렇게 어렵지는 않은 문제다. 사실 최소, 최대를 찾는다면 배열을 쓸 필요가 없기도 하다. 하지만, 배열의 첫 카테고리인만큼 배열로 먼저 접근해서 풀어보고, 그 다음 마지막으로 배열을 쓰지 않고 푸는 방식..
[백준] 1920번 : 수 찾기 - JAVA [자바]
[백준] 1920번 : 수 찾기 - JAVA [자바]
2021.07.16https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 문제 새 카테고리인 이분 탐색의 첫 번째 문제인 수 찾기다. 알고리즘 [접근 방법] 일단, 풀이 방법을 알아보기 전에 이분 탐색(Binary Search)에 대해 알아보자. 이 전 문제까지 우리가 분할 정복을 살펴보았다. 분할 정복 방식의 경우에는 문제가 주어지면 해당 문제를 둘 이상으로 나누면서 나눠진 부분문제에 대해 풀렸다면 해당 부분은 끝내고,..
[백준] 1110번 : 더하기 사이클 - [C++]
[백준] 1110번 : 더하기 사이클 - [C++]
2021.07.06https://www.acmicpc.net/problem/1110 1110번: 더하기 사이클 0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, www.acmicpc.net 문제 그리 어려운 문제는 아닐 것이다. 조금만 문제를 자세히 살펴보면 쉽게 풀 수 있다. 알고리즘 [접근 방법] 문제 원리는 간단하다. 1. 1의 자릿수는 10의 자리수가 된다. 2. 각 자릿수의 값을 더한 결과의 1의 자릿수는 1의 자리수가 된다. 3. 위 과정을 통해 얻은 결과가 초기에 주어진 수랑 같을 때 까지 반복한다. 이 세 개만 찾아내면 된다. 쉽게 말해 아래 이미지와 같..
자바 [JAVA] - Linked Hash Set (연결 해시 셋) 구현하기
자바 [JAVA] - Linked Hash Set (연결 해시 셋) 구현하기
2021.07.02자료구조 관련 목록 링크 펼치기 더보기 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. 우선순위 큐 (Priority..
[백준] 10951번 : A + B - 4 - [C++]
[백준] 10951번 : A + B - 4 - [C++]
2021.06.29https://www.acmicpc.net/problem/10951 10951번: A+B - 4 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 이 전 문제인 A+B - 5와 문제가 같아보이나 이 번 문제는 유의해야 할 점이 있다. 알고리즘 [접근 방법] 이 번 문제의 키 포인트는 문제를 자세히 보면 몇 개를 입력받는지 알 수 없다는 것이다. 이렇게 주어진 입력 파일만 갖고 입력을 받을 때 더이상 읽을 수 있는 데이터가 없는 경우 즉, 파일의 끝일 때 이를 EOF(End Of File) 이라고 한다. 위 문제를 본다면 입력에서 더이상의 읽을 수 있는 데이터가 존재하지 않을 때 반복문을 종료하라는 것이다. (참고로 우리는 일상적으로 문장의 끝을..
[백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]
[백준] 2261번 : 가장 가까운 두 점 - JAVA [자바]
2021.06.26https://www.acmicpc.net/problem/2261 2261번: 가장 가까운 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net 문제 이 번 문제는 분할 정복 카테고리의 마지막 문제인만큼 조금 많이 어려운 문제다. 분할 정복 방식 자체는 이전 문제인 히스토그램에서 가장 큰 직사각형과 접근 방식은 유사하나 조금 더 신경써야할 부분들이 존재하므로 같이 알아보도록 하자. 알고리즘 [접근 방법] 이 번 문제의 경우 일반적인 분할 정복 방식과 스윕 라인 방식 이렇게 두 가지 풀이 방식이 존재한다. 일..
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 - JAVA [자바]
[백준] 6549번 : 히스토그램에서 가장 큰 직사각형 - JAVA [자바]
2021.06.18https://www.acmicpc.net/problem/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 문제 히스토그램 내의 가장 큰 넓이를 구하는 문제는 엄청 유명한 문제라 알고리즘을 많이 접해보았다면 한 번쯤은 접해보았을 문제다. 알고리즘 [접근 방법] 이 번 문제의 경우 풀이 방법 자체는 대표적으로 두 가지 방식이 있다. 먼저 이 문제의 카테고리 처럼 분할정복으로 풀이하는 방식, 그리고 스택 자료구조를 이용한 풀이 방식이 있다. 이 번에..
[백준] 10952번 : A+B - 5 - [C++]
[백준] 10952번 : A+B - 5 - [C++]
2021.06.13https://www.acmicpc.net/problem/10952 10952번: A+B - 5 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 새로운 카테고리인 while 문의 첫 문제다. 알고리즘 [접근 방법] 만약 while문을 다뤄보았다면 모두가 쉽게 풀 수 있었을 것이다. 기본적으로 for문과 유사하게 반복문이라는 메커니즘을 갖고있지만 조금은 양식이 다르다. 그동안 배웠던 for문은 기본 형식이 다음과 같았다. 반면에 while문은 형태가 조금 더 간단하다. 두 개의 반복문은 본질적으로 그렇게 큰 차이는 없지만 for문은 초기식에 따른 변수에 따라 조건식을 검사하기 때문에 좀 더 유연하게 활용할 수 있고, 반면에 while문은 단순한..