본문 바로가기

알고리즘 자료구조

[백준] 1158 요세푸스 문제 🖊️문제 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(≤ N)가 주어진다. 이제 순서대로 K번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, K)-요세푸스 순열이라고 한다. 예를 들어 (7, 3)-요세푸스 순열은 이다. N과 K가 주어지면 (N, K)-요세푸스 순열을 구하는 프로그램을 작성하시오. 🖊️문제 풀이 public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //n,k 입력 i.. 더보기
[프로그래머스] 나누어 떨어지는 숫자 배열 🖊️문제 array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수, solution을 작성해주세요. divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하세요. 🖊️문제 풀이 import java.util.*; class Solution { public int[] solution(int[] arr, int divisor) { ArrayList list = new ArrayList(); for(int i : arr){ if(i%divisor==0) { list.add(i); } } if(list.isEmpty()){ list.add(-1); } list.sort(Comparator.naturalOrder()); int.. 더보기
[백준] 10818 최소, 최대 https://www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 🖊️문제 N개의 정수가 주어진다. 이때, 최솟값과 최댓값을 구하는 프로그램을 작성하시오. 🖊️ 문제풀이 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); //배열 길이, 배열 값 입력 int .. 더보기
[백준] 회전하는 큐 1021번: 회전하는 큐 (acmicpc.net) 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 🖊️문제 지민이는 N개의 원소를 포함하고 있는 양방향 순환 큐를 가지고 있다. 지민이는 이 큐에서 몇 개의 원소를 뽑아내려고 한다. 지민이는 이 큐에서 다음과 같은 3가지 연산을 수행할 수 있다. 첫 번째 원소를 뽑아낸다. 이 연산을 수행하면, 원래 큐의 원소가 a1, ..., ak이었던 것이 a2, ..., ak와 같이 된다. 왼쪽으로 한 칸 이동시킨다. 이 연산을 수행하면, a1, ..., ak가 a2, .. 더보기
[자료구조와 함께 배우는 알고리즘 입문] 6.정렬 알고리즘(2) 3. 단순 선택 정렬 3-1. 단순 선택 정렬 알아보기 가장 작은 요소는 맨 앞으로, 두 번째로 작은 요소는 맨 앞에서 두 번째로 이동하고 그 다음으로 작은요소, 또 그 다음으로 작은요소를 옮겨주면서 정렬해주는 알고리즘이다. 쉽게 표현하면 아래와 같은 과정을 통해 정렬을 시키는 것이다. 3-2. 단순 선택 정렬 적용 static void swap(int[] a, int idx1, int idx2){ int temporay = a[idx1]; a[idx1] = a[idx2]; a[idx2] = temporay; //idx1의 데이터 값을 임시 변수에 저장하고 //idx1과 idx2데이터 교환 } static void selectionSort(int[]a, int n){ for (int i = 0; i < .. 더보기
[프로그래머스] 같은 숫자는 싫어요 🖊️문제 배열 arr가 주어집니다. 배열 arr의 각 원소는 숫자 0부터 9까지로 이루어져 있습니다. 이때, 배열 arr에서 연속적으로 나타나는 숫자는 하나만 남기고 전부 제거하려고 합니다. 단, 제거된 후 남은 수들을 반환할 때는 배열 arr의 원소들의 순서를 유지해야 합니다. 예를 들면, arr = [1, 1, 3, 3, 0, 1, 1]이면 [1, 3, 0, 1]을 return 합니다. arr = [4, 4, 4, 3, 3]이면 [4, 3]을 return합니다. 배열 arr에서 연속적으로 나타나는 숫자는 제거하고 남은 수들을 return하는 solution함수를 완성해 주세요. 🖊️풀이 public static int[] solution(int []arr) { //stack 생성해서 배열에 저장된 값.. 더보기
[백준]25556 포스텍 https://www.acmicpc.net/problem/25556 🖊️문제 포닉스는 길이가 N인 순열 A 네 개의 비어 있는 스택을 가지고 있다. 길이가 N인 순열이란,1이상 N이하의 서로 다른 정수 N개가 임의로 나열된 수열을 말한다. 스택이란 자료구조의 한 종류로 가장 나중에 삽입한 자료가 가장 먼저 나오는 후입선출 (Last In First Out, LIFO)의 특성을 가지고 있다. 포닉스는 PPC를 맞아 더러워진 순열을 청소하려 한다. 순열을 청소하는 것은 다음과 같은 과정을 통해 순열을 오름차순으로 정렬하는 것을 뜻한다. 즉 순열을 1,2,3,⋯N으로 만들어야 한다. 순열 A의 원소들을 앞 원소부터 순서대로 네 개의 스택 중 하나에 삽입한다. 순열 A의 모든 원소를 스택에 삽입했다면, 네 개 .. 더보기
[자료구조와 함께 배우는 알고리즘 입문] 6. 정렬 알고리즘 (1) 1. 정렬 알고리즘이란? 1-1. 정렬이란? 정렬은 다들 알고 있는 것처럼 데이터를 순서에 따라 나열하는 것이다. 정렬 알고리즘을 이용해 데이터를 정렬하면 데이터 검색이 조금 더 쉬워지게 된다. 1-2. 정렬 알고리즘의 안정성 정렬 알고리즘은 안정된 알고리즘 / 안정되지 않은 알고리즘으로 나눌 수 있다. 안정된 정렬은 키값이 같은 요소의 순서가 정렬 전후에도 유지되는 것이다. 1-3. 내부 정렬과 외부 정렬 내부 정렬은 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때 사용하는 알고리즘이다. 외부 정렬은 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때 사용하는 알고리즘이다. 외부 정렬의 경우 알고리즘이 복잡해지고 별도의 팔일 등이 요구된다. 1-4. 정렬 알고리즘의 핵심요소 : 교환,.. 더보기
728x90

티스토리툴바