알고리즘

선택 정렬(selection sort)- 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법- 선택 정렬은 구현 방법이 복잡하고, 시간 복잡도도 O(n^2) 으로 효율적이지 않아 코딩테스트에서는 많이 사용하지 않는다.    선택 정렬의 핵심 이론최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 선택 정렬의 핵심이다.         선택 정렬 과정1. 남은 정렬 부분에서 최솟값 또는 최댓값을 찾는다.2. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.3. 가장 앞에 있는 데이터의 위치를 변경해(index ++) 남은 정렬 부분의 범위를 축소한다.4. 전체 데이터 크기만큼 index가 커질 때까지, 즉 남은 정..

[ 성능 요약 ] 메모리: 52336 KB, 시간: 440 ms [ 분류 ] 재귀(recursion) [ 문제 설명 ] 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다. 아래 그림은 원판이 5개인 경우의 예시이다. [ 입력 ] 첫째 줄에 첫 번째 장대에 쌓인 원판의 개수 N (1 ≤ N ≤ 20)이 주어진다. [ 출력 ] 첫..

[ 성능 요약 ] 메모리: 22240 KB, 시간: 352 ms [ 분류 ] 정렬(sorting), 구현(implementation) [ 문제 설명 ] N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. [ 입력 ] 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. [ 출력 ] 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. import java.util.Scanner; public class 수정렬하기 { public static void main(String[] args) { Scanner sc = new Sca..

[ 스택 (Stack) ]: 삽입과 삭제 연산이 후입선출 (LIFO : Last-In First-Out) 로 이루어진 자료구조* 우선탐색 (DFS:Depth First Search), 백트래킹 종류의 코딩에 효과적이다. ( 후입선출은 개념 자체가 재귀함수 알고리즘 원리와 일맥상통하기 때문이다. )스택은 값을 넣는 곳과 빼는 곳이 일치한다. 새 값이 스택에 들어가면 top이 새 값을 가리킨다.스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어있으므로 결과적으로는 가장 마지막에 넣었던 값이 나오게 된다.     * 스택 관련 용어1) top : 데이터의 삽입과 삭제가 발생하는 위치를 가리키는 용어2) push : top 위치에 새로운 데이터를 삽입하는 연산3) pop : top 위치에..

[ 성능 요약 ] 메모리: 19352 KB, 시간: 268 ms [ 분류 ] 사칙연산(arithmetic), 수학(math) [ 문제 설명 ] 세준이는 기말고사를 망쳤다. 세준이는 점수를 조작해서 집에 가져가기로 했다. 일단 세준이는 자기 점수 중에 최댓값을 골랐다. 이 값을 M이라고 한다. 그리고 나서 모든 점수를 점수/M*100으로 고쳤다. 예를 들어, 세준이의 최고점이 70이고, 수학점수가 50이었으면 수학점수는 50/70*100이 되어 71.43점이 된다. 세준이의 성적을 위의 방법대로 새로 계산했을 때, 새로운 평균을 구하는 프로그램을 작성하시오. [ 입력 ] 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 ..

[ 성능 요약 ] 메모리: 17708 KB, 시간: 208 ms [ 분류 ] 구현(implementation), 수학(math), 문자열(string) [ 문제 설명 ] N개의 숫자가 공백 없이 쓰여있다. 이 숫자를 모두 합해서 출력하는 프로그램을 작성하시오. [ 입력 ] 첫째 줄에 숫자의 개수 N (1 ≤ N ≤ 100)이 주어진다. 둘째 줄에 숫자 N개가 공백없이 주어진다. [ 출력 ] 입력으로 주어진 숫자 N개의 합을 출력한다. [ 문제 링크 ] https://www.acmicpc.net/problem/11720 import java.util.Scanner; public class P11720_숫자의합 { // N개의 숫자가 공백 없이 써 있다. 이 숫자를 모두 합해 출력하는 프로그램을 작성하시오...