고양이 두 잔

으로 구현한 다른 정렬: [Java+Python]버블 정렬(Bubble Sort) [Java+Python]선택 정렬(Selection Sort) [Java+Python]병합 정렬(Merge Sort) [Java+Python]힙 정렬(Heap Sort) [Java+Python]퀵 정렬(Quick Sort) [Java+Python]카운팅 정렬(Counting Sort) 삽입 정렬(Insert Sort)은 한 마디로 말하면 모든 요소를 정렬이 완료된 부분과 비교하여 자리를 찾아 삽입하는 알고리즘이다. 실생활에서 문제가 주어졌을 때 무의식적으로 가장 먼저 사용하는 알고리즘이며, 이 덕분에 가장 직관적이고 간결하다. 선택 정렬이나 거품 정렬 같은 알고리즘에 비해 빠른 편이며, 최선의 경우 거품 정렬과 함께 최고의..

문제 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 단어 S가 주어진다. 단어의 길이는 100을 넘지 않으며, 알파벳 소문자로만 이루어져 있다. 출력 각각의 알파벳에 대해서, a가 처음 등장하는 위치, b가 처음 등장하는 위치, ... z가 처음 등장하는 위치를 공백으로 구분해서 출력한다. 만약, 어떤 알파벳이 단어에 포함되어 있지 않다면 -1을 출력한다. 단어의 첫 번째 글자는 0번째 위치이고, 두 번째 글자는 1번째 위치이다. 풀이 알파벳 개수대로 26개의 원소를 가진 리스트를 생성해 -1로 전부 채워두었다. 이후 주어진 단어를 char(..

문제 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 1,000보다 작거나 같은 자연수 N이 주어진다. 출력 첫째 줄에 1보다 크거나 같고, N보다 작거나 같은 한수의 개수를 출력한다. 풀이 정의에 따라 1부터 99까지는 전부 한수이다. 또한 1000은 한수가 아니니 제외하면, 실제 문제는 '세 자리의 정수 중 각 자리의 차이가 같은 숫자'의 개수를 구하는 간단한 문제라는 걸 알 수 있다. 코드도 간단하다. import java.util.Scanner; import java.util.stre..

문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다. 33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ... n을 d(n)의 생성자라..

재귀란 일반적으로 정의하자면 자기 언급이다. 수학으로 봤을 땐 일종의 점화식이라고 할 수 있으며, 프로그래밍적으로 이야기하자면 재귀 함수란 정의 단계에서 자시 자신을 호출하는 함수를 가리킨다. 주어진 문제를 풀 때 자기 자신을 다시 호출함으로써 코드의 복잡도를 줄이기 위해 사용한다. 하지만 꼬리재귀 최적화가 되어있지 않은 환경에서 재귀 호출은 스택 메모리를 빠르게 잡아먹게 되므로 실행 속도 측면에서 반복문이 더 좋은 선택이 된다. 여기서 꼬리재귀 최적화란 메서드를 재귀 호출 메서드와 꼬리 메서드로 구분해 재귀 호출 이후 추가적인 연산을 실행하지 않도록 막는 방법이며, C++, Swift, Kotlin 컴파일러에는 자동으로 구현되어 있으나 보안상의 이유로 자바 컴파일러엔 구현되지 않았다. 다만 이에 영향을..

자료구조에서의 그래프는 굉장히 일반적인 개념이고 그 예가 많지만, 특정 기준을 이용해 둘로 나누면 아래와 같이 구분할 수 있다. 바로 무방향 그래프(G1)와 방향 그래프(G2)인데, 이와 같은 자료구조를 자바에 구현하는 방법은 크게 두 가지가 존재한다. 하나씩 알아보자. Adjacency Matrix 인접 행렬은 말 그대로 노드간의 관계를 행렬로 나타낸 것이다. 노드가 n개인 그래프의 인접행렬은 n X n 정사각 행렬이 되며, 인접한 경우엔 1, 그렇지 않은 경우엔 0을 채워 넣는다. 추가로 무방향 그래프의 경우엔 인접 행렬이 대칭을 이루고 있는 것이 특징이다. 방향 그래프의 경우엔 반드시 대칭 행렬을 이루지는 않는다. 인접 행렬의 장점은 노드 사이의 빠른 경로를 찾기 편하다는 점이며 단점은 간선의 유무..

목차 Tree Traversals 특정 목적을 가지고 모든 노드를 한 번씩 방문하는 것을 트리 순회라 한다. 순회 방법은 크게 네 가지가 있으며, 공통적으로 왼쪽에서 오른쪽으로 진행한다. 이진트리는 그 정의상 서브 트리 역시 이진트리이기 때문에, 재귀 함수를 적용하기 편하다. 먼저 루트와 좌 우 서브트리 순서에 따른 분류를 보자. 전위 순회(Preorder Traversal)는 VLR의 순서로 방문한다. 아래와 같다. 참고로 이 방식은 그래프 순회의 깊이 우선 탐색(DFS)과 동일한 방법이다. 이어서 중위 순회(Preorder Traversal) 순회는 LVR이다. 아래와 같다. 마지막으로 후위 순회(Postorder Traversal) 순회는 LRV이다. 아래와 같다. 추가로 VRL 분류와 별개로 레벨..

목차 Stack Stack은 더미, 쌓다 등의 의미를 지니고 있다. 하나의 입출력 방향만을 가진 구조에 데이터를 넣는 것으로 생각할 수 있는데, 때문에 가장 큰 특징은 후입 선출 구조라는 점이다. 추가로 데이터를 한 번에 하나씩만 넣고 뺄 수 있다는 특성도 존재한다. 주로 브라우저의 앞으로 가기나 뒤로 가기, 실행 취소(컨트롤+z), 혹은 함수의 호출이나 재귀 함수 역시 스택에 기반을 두고 있다. 보통 고정된 크기를 가지기 때문에 다 사용하면 넘치게 되며, 이를 스택 오버플로우라고 부른다. Queue 이에 반해 큐는 입력과 출력의 방향이 따로 정해진, 선입선출 구조를 지니고 있다. 스택과의 공통점은 데이터를 한 번에 하나씩만 넣거나 뺄 수 있다는 점이 있으며 프린터의 출력 알고리즘 같은 작업/데이터의 순..

문제 정수 n개가 주어졌을 때, n개의 합을 구하는 함수를 작성하시오. 작성해야 하는 함수는 다음과 같다. Java: long sum(int[] a); (클래스 이름: Test) a: 합을 구해야 하는 정수 n개가 저장되어 있는 배열 (0 ≤ a[i] ≤ 1,000,000, 1 ≤ n ≤ 3,000,000) 리턴값: a에 포함되어 있는 정수 n개의 합 풀이 함수 안에 스트림을 집어넣어 구현해 보았다. 정확하게 이유는 모르겠지만 중간에 mapToLong()을 제거하면 틀린다. 숫자 범위 때문인가. 아무튼 간략한 풀이! import java.util.Arrays; public class Prob15596Stream { long sum(int[] a) { long ans = Arrays.stream(a) .m..

문제 X 대학 M 교수님은 프로그래밍 수업을 맡고 있다. 교실엔 학생이 30명이 있는데, 학생 명부엔 각 학생별로 1번부터 30번까지 출석번호가 붙어 있다. 교수님이 내준 특별과제를 28명이 제출했는데, 그중에서 제출 안 한 학생 2명의 출석번호를 구하는 프로그램을 작성하시오. 입력 입력은 총 28줄로 각 제출자(학생)의 출석번호 n(1 ≤ n ≤ 30)가 한 줄에 하나씩 주어진다. 출석번호에 중복은 없다. 출력 출력은 2줄이다. 1번째 줄엔 제출하지 않은 학생의 출석번호 중 가장 작은 것을 출력하고, 2번째 줄에선 그다음 출석번호를 출력한다. 풀이 스트림으로 어떻게 풀지.. 하다가 며칠 전에 자바 8과 11을 비교한 포스팅을 적은 걸 기억해냈다. 거기서 얻은 Predicate키워드를 이용해 일단 1부터..