JUNGOL
-
JUNGOL...112일지 2021. 8. 10. 12:10
Intermediate_Coder/분할정복/Tutorial: STL Sort 1 문제 우리는 지금까지 여러가지 정렬법을 배워왔다. 정렬법에는 선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬, 합병 정렬 등이 있다. 하지만 배열을 정렬할 필요가 생길 때마다 위의 방법을 손으로 구현하는 것은 지루한 작업일 뿐더러, 손으로 코딩하다 보니깐 구현 중에 실수할 확률도 높아진다. 여러분들의 코딩능력 향상을 위해 지금까지는 숨겨왔지만, 사실 C++에는 크기 비교가 가능한 형식으로 선언된 배열을 정렬해주는 친절한 함수가 존재한다. 바로 sort()함수이다. 여기에서 크기 비교가 가능한 형식은 int나 double처럼 부등호를 사용하여 대소판별이 가능한 자료형을 뜻한다. 간단하게 예를 들자면, 3 n; int* arr =..
-
JUNGOL...111일지 2021. 8. 9. 15:31
Intermediate_Coder/분할정복/Tutorial : 퀵정렬(Quick Sort) 문제 [퀵소트(Quick Sort)] 퀵소트는 토니 호어(찰스 엔터니 리처드 호어 - Charles Antony Richard Hoare)가 개발한 알고리즘이다. 원소들간의 비교와 교환을 통하여 정렬하는 비교기반정렬 알고리즘이다. 원소들 중에 같은 값이 있는 경우 정렬후에 이들의 순서가 달라질 수 있어 불안정 정렬에 속한다. ( 3을 피봇으로 하고 전통적인 방법으로 하는 예 51, 52, 3, 2, 1) ( 22를 피봇으로 하고 아래 설명한 방법으로 하는 예 21, 3, 1, 22) N개의 데이터를 정렬할 때, 시간복잡도는 평균 O(N * logN), 최악의 경우 O(N2) 이 소요된다. 매 단계에서 적어도..
-
JUNGOL...110일지 2021. 8. 6. 14:44
Intermediate_Coder/분할정복/숫자구슬(easy) 문제 N개의 숫자 구슬이 과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼수 없고 따라서 바꿀 수 없다. 이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최대값이 최소가 되도록 하려 한다. 예를 들어 세 그룹으로 나눈다고 할 때 와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최대값은 18이 되고, 과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최대값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최대값이 17보다 작게 만들 수는 없다. 각 그룹의 합 중 최대값이 최소가 되도록 M개의 그룹으로 나누었을 때, 그 최대값을 출력하는 프로그..
-
JUNGOL...109일지 2021. 8. 5. 13:37
Intermediate_Coder/분할정복/숫자구슬(easy) 문제 N개의 숫자 구슬이 과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼수 없고 따라서 바꿀 수 없다. 이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최대값이 최소가 되도록 하려 한다. 예를 들어 세 그룹으로 나눈다고 할 때 와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최대값은 18이 되고, 과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최대값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최대값이 17보다 작게 만들 수는 없다. 각 그룹의 합 중 최대값이 최소가 되도록 M개의 그룹으로 나누었을 때, 그 최대값을 출력하는 프로그..
-
JUNGOL...108일지 2021. 8. 4. 13:28
Intermediate_Coder/분할정복/숫자구슬(easy) 문제 N개의 숫자 구슬이 과 같이 막대에 꿰어져 일자로 놓여 있다. 이들 구슬은 막대에서 빼낼수 없고 따라서 바꿀 수 없다. 이 숫자 구슬을 M개의 그룹으로 나누었을 때 각각의 그룹의 합 중 최대값이 최소가 되도록 하려 한다. 예를 들어 세 그룹으로 나눈다고 할 때 와 같이 그룹을 나누면 그룹의 합은 각각 11, 15, 18이 되어 그 중 최대값은 18이 되고, 과 같이 나누면 각 그룹의 합은 각각 17, 12, 15가 되어 그 중 최대값은 17이 된다. 숫자 구슬의 배열이 위와 같을 때는 그룹의 합 중 최대값이 17보다 작게 만들 수는 없다. 각 그룹의 합 중 최대값이 최소가 되도록 M개의 그룹으로 나누었을 때, 그 최대값을 출력하는 프로그..
-
JUNGOL...107일지 2021. 8. 3. 15:05
Intermediate_Coder/분할정복/모자이크 문제 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 정사각형 모양의 칸을 만들고, 각 칸마다 같은 색의 물감으로 색칠을 하였다. 그런데 잘못 칠해진 칸이 있음을 발견하게 되었다. 수찬이는 도화지와 색깔이 같은 색종이를 사서 잘못 칠해진 칸에 색종이를 붙이고 다시 그리는 것이 좋겠다고 생각하고 선생님께 상의를 드렸다. 선생님께서는 정해진 장수의 색종이를 사용하여 아래와 같은 조건을 따르면서 잘못 칠해진 칸을 모두 가리되, 가장 작은 색종이의 크기를 구하는 새로운 문제를 내셨다. (조건 1) 사용되는 색종이는 모두 크..
-
JUNGOL...106일지 2021. 8. 2. 16:22
Intermediate_Coder/분할정복/모자이크 문제 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 정사각형 모양의 칸을 만들고, 각 칸마다 같은 색의 물감으로 색칠을 하였다. 그런데 잘못 칠해진 칸이 있음을 발견하게 되었다. 수찬이는 도화지와 색깔이 같은 색종이를 사서 잘못 칠해진 칸에 색종이를 붙이고 다시 그리는 것이 좋겠다고 생각하고 선생님께 상의를 드렸다. 선생님께서는 정해진 장수의 색종이를 사용하여 아래와 같은 조건을 따르면서 잘못 칠해진 칸을 모두 가리되, 가장 작은 색종이의 크기를 구하는 새로운 문제를 내셨다. (조건 1) 사용되는 색종이는 모두 크..
-
JUNGOL...105일지 2021. 7. 30. 13:47
Intermediate_Coder/분할정복/모자이크 문제 수찬이는 선생님을 도와서 교실 벽면을 장식할 모자이크 그림을 그리기로 하였다. 이를 위하여 직사각형 모양의 큰 도화지를 준비하여 교실 벽에 붙이고 1cm 간격으로 가로선과 세로선을 그려서 정사각형 모양의 칸을 만들고, 각 칸마다 같은 색의 물감으로 색칠을 하였다. 그런데 잘못 칠해진 칸이 있음을 발견하게 되었다. 수찬이는 도화지와 색깔이 같은 색종이를 사서 잘못 칠해진 칸에 색종이를 붙이고 다시 그리는 것이 좋겠다고 생각하고 선생님께 상의를 드렸다. 선생님께서는 정해진 장수의 색종이를 사용하여 아래와 같은 조건을 따르면서 잘못 칠해진 칸을 모두 가리되, 가장 작은 색종이의 크기를 구하는 새로운 문제를 내셨다. (조건 1) 사용되는 색종이는 모두 크..