본문 바로가기
반응형

분류 전체보기701

백준 1041 주사위 c++ (탐욕법) 문제 출처 : https://www.acmicpc.net/problem/1041 1041번: 주사위 첫째 줄에 N이 주어진다. 둘째 줄에 주사위에 쓰여 있는 수가 주어진다. 위의 그림에서 A, B, C, D, E, F에 쓰여 있는 수가 차례대로 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, 쓰여 있는 수 www.acmicpc.net 문제 주사위는 위와 같이 생겼다. 주사위의 여섯 면에는 수가 쓰여 있다. 위의 전개도를 수가 밖으로 나오게 접는다. A, B, C, D, E, F에 쓰여 있는 수가 주어진다. 지민이는 현재 동일한 주사위를 N3개 가지고 있다. 이 주사위를 적절히 회전시키고 쌓아서, N×N×N크기의 정육면체를 만들려고 한다. 이 정육면체는 탁자위에 있으므로, 5개의 면만 보인다.. 2021. 7. 20.
백준 1038 c++ 감소하는 수 (완전 탐색) 문제 출처 : https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 문제 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 출력하는 프로그램을 작성하시오. 0은 0번째 감소하는 수이고, 1은 1번째 감소하는 수이다. 만약 N번째 감소하는 수가 없다면 -1을 출력한다. 입력 첫째 줄.. 2021. 7. 19.
[알고리즘] 퀵 정렬(Quick Sort) 퀵 정렬(Quick Sort)이란? 리스트에서 하나의 피벗(Pivot)을 정하고, 이를 기준으로 피벗보다 작은 요소들, 피벗보다 큰 요소들로 두 개의 부분 리스트를 만들고(Divide : 분할), 정렬 후 다시 결합(Conquer : 정복)을 재귀적으로 반복하는 방법으로 원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다. 퀵 정렬(Quick Sort)의 특징 1. 주어진 배열(입력 배열) 이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다. //주어진 배열만으로 정렬을 할 수 있다. //메모리가 제한적인 경우에 이점이 있다. 2. 중복된 값은 입력 순서와 동일하게 유지된다는 보장을 할 수 없는 불안정 정렬(Unstable Sort)이다 3. .. 2021. 7. 19.
백준 1025 제곱수 찾기 리뉴얼!! c++, Kotlin (완전 탐색) 문제 출처 : https://www.acmicpc.net/problem/1025 1025번: 제곱수 찾기 첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. 둘째 줄부터 N개의 줄에 직사각형 격자판에 쓰여 있는 수가 주어진다. 모두 한자리이다. N과 M은 9보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 문제 지민이는 천장을 보다가 직사각형 격자판을 생각했고, 각 칸에 숫자를 한 자리씩 적어 놓았다. 수업시간이 너무 지루해서 지민이는 행의 숫자가 등차수열이고, 열의 숫자도 등차수열을 이루는 서로 다른 칸의 수열을 생각해 보았다. 그리고 나서 그 수열의 수를 모두 이어 붙였다. 이렇게 만든 수 중에 가장 큰 제곱수를 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 세로 크기 N과 가로.. 2021. 7. 18.
[알고리즘] 삽입 정렬 (Insertion Sort) 삽입 정렬(Insertion Sort)이란? 앞(왼쪽)의 원소들이 정렬되어 있다는 가정 하에 적절한 위치에 삽입하는 방법으로 원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다. 삽입 정렬(Insertion Sort)의 특징 1. 주어진 배열(입력 배열)이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다. //주어진 배열만으로 정렬을 할 수 있다. //메모리가 제한적인 경우에 이점이 있다. 2. 코드가 직관적이며 정렬 알고리즘 중에 난이도가 쉬운 편이다. 3. 중복된 값은 입력 순서와 동일하게 정렬되는 안정 정렬(Stable Sort)이다. 4. 손 안의 카드를 정렬하는 방법과 유사하다. 5. 시간 복잡도는 Best : O(N), Avg : O.. 2021. 7. 18.
[알고리즘] 버블 정렬 (Bubble Sort) 버블 정렬(Bubble Sort)이란? 서로 인접한 두 원소를 검사하여 더 작거나 큰 값을 반복적으로 앞으로 보내는 방법으로 원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다. 버블 정렬(Bubble Sort)의 특징 1. 주어진 배열(입력 배열)이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다. //주어진 배열만으로 정렬을 할 수 있다. //메모리가 제한적인 경우에 이점이 있다. 2. 코드가 직관적이며 정렬 알고리즘 중 구현 방법이 가장 간단하다. 3. 중복된 값은 입력 순서와 동일하게 정렬되는 안정 정렬(Stable Sort)이다. 4. 시간 복잡도는 최선, 평균, 최악의 경우 모두 O(N^2)이며 모든 정렬 중에 가장 비효율적인 정렬 .. 2021. 7. 18.
[알고리즘] 선택 정렬 (Selection Sort) 선택 정렬(Selection Sort)이란? 주어진 리스트에서 최솟값을 찾아(선택) 맨 앞으로 보내는 방법으로 원소들을 작은 순, 혹은 큰 순으로 정렬하는 알고리즘 중 하나이다. 선택 정렬(Selection Sort)의 특징 1. 주어진 배열(입력 배열)이외에 다른 추가 메모리를 요구하지 않는 제자리 정렬(in-place sorting) 알고리즘이다. //주어진 배열만으로 정렬을 할 수 있다. //메모리가 제한적인 경우에 이점이 있다. 2. 코드가 직관적이며 정렬 알고리즘 중에 난이도가 쉬운 편이다. 3. 중복된 값은 입력 순서와 동일하게 유지된다는 보장을 할 수 없는 불안정 정렬(Unstable Sort)이다. // 짜기 나름이다. 아래 코드는 stable하다. 4. 시간 복잡도는 최선, 평균, 최악의.. 2021. 7. 18.
프로그래머스 풍선 터트리기 c++ (dp) 2022-06-18 코틀린 추가 문제 출처 : https://programmers.co.kr/learn/courses/30/lessons/68646 코딩테스트 연습 - 풍선 터트리기 [-16,27,65,-2,58,-92,-71,-68,-61,-33] 6 programmers.co.kr 문제 설명 일렬로 나열된 n개의 풍선이 있습니다. 모든 풍선에는 서로 다른 숫자가 써져 있습니다. 당신은 다음 과정을 반복하면서 풍선들을 단 1개만 남을 때까지 계속 터트리려고 합니다. 임의의 인접한 두 풍선을 고른 뒤, 두 풍선 중 하나를 터트립니다. 터진 풍선으로 인해 풍선들 사이에 빈 공간이 생겼다면, 빈 공간이 없도록 풍선들을 중앙으로 밀착시킵니다. 여기서 조건이 있습니다. 인접한 두 풍선 중에서 번호가 더 작은 풍선을 터트리는 행위는 최대 1번만.. 2021. 7. 17.
백준 1516 게임 개발 c++ (위상 정렬) 문제 출처 : https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다. 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 .. 2021. 7. 16.
반응형

티스토리툴바