문제 출처: https://www.acmicpc.net/problem/1120 1120번: 문자열 길이가 N으로 같은 문자열 X와 Y가 있을 때, 두 문자열 X와 Y의 차이는 X[i] ≠ Y[i]인 i의 개수이다. 예를 들어, X=”jimin”, Y=”minji”이면, 둘의 차이는 4이다. 두 문자열 A와 B가 주어진다. 이때, A의 www.acmicpc.net 1. 문제 접근방식 - 문자열이 두개 주어졌을 때 길이를 맞추기 위해 가장 최소의 문자를 쓸 수 있는 자리를 골라야한다. 최소의 개수를 구하기 위해서는 문자열 중 긴 문자열을 돌며 짧은 문자열과 가장 같은 문자가 많은 자리를 정하면 된다. 2. 내가 푼 코드 import java.io.BufferedReader; import java.io.IOE..
문제 출처: https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 1. 문제 접근방식 - 함수 카테고리 안에있는 문제인 만큼 d함수를 구현하는 것이 핵심이다. 2. 내가 푼 코드 public class boj4673 { static boolean[] check = new boolean[10001]; static StringBuilder sb = new StringBuilder(); public sta..
Chapter6 - 힙과 힙 정렬 6.1 힙 힙(heap)은 내부노드에 키를 저장하면서 두 가지 속성을 만족하는 이진트리 힙순서(heap-order): 모든 부모-자식 관계에서 부모노드의 키가 자식노드의 키보다 작거나 같도록 구성된 이진트리 완전 이진 트리(complete binary tree)로 구성 6.1.1 힙의 높이 n개의 키를 저장한 힙의 높이는 O(log n) 6.2 힙을 이용한 우선순위 큐 구현 힙을 이용하여 우선순위 큐 ADT 구현 가능 6.2.1 힙에 삽입 삽입 노드 z, 새로운 마지막 노드 찾음 k를 z에 저장 후 z을 내부노드로 확장 힙순서 속성 복구 Alg insertItem(k) input key k, node last output none 1. advanceLast() 2. z ..
Chapter5 - 우선순위 큐 5.1 우선순위 큐 ADT 정렬에 자주 응용 5.1.1 우선순위 큐 ADT 임의의 데이터 항목이 삽입되며, 일정한 순서에 의해 삭제되는 데이터구조 일반적인 큐와 비교했을 때 삽입과 삭제가 가능한 것은 동일하지만 일반적인 큐는 삽입 순서 그대로 삭제되고 우선순위 큐는 키 순서에 따라 삭제 5.1.2 우선순위 큐 응용 정렬(Sort): 데이터원소들을 일정한 키 순서에 의해 다시 배치하는 것 5.1.3 우선순위 큐 ADT 메서드 주요 메서드 insertItem(k, e): 키 k인 원소 e를 큐에 삽입 element removeMin() 일반 메서드 integer size() boolean isEmpty() 접근 메서드 element minElement() element min..
