관광이 블로그

안녕하세요 감자코딩에 감자개발자입니다. 이번에 살펴볼 알고리즘 문제는 조세퍼스 문제 1158번 문제입니다.문제 링크 1158 조세퍼스 문제 https://www.acmicpc.net/problem/1158 조세퍼스 문제 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초256 MB139386986528552.089%문제조세퍼스 문제는 다음과 같다.1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 M(≤ N)이 주어진다. 이제 순서대로 M번째 사람을 제거한다. 한 사람이 제거되면 남은 사람들로 이루어진 원을 따라 이 과정을 계속해 나간다. 이 과정은 N명의 사람이 모두 제거될 때까지 계속된다. 원에서 사람들이 제거되는 순서를 (N, M)-조세퍼스 순열이라고 한다. 예를 들어 (7, 3..

안녕하세요, 감자코딩에 감자개발자입니다. 이번에 포스팅할 백준알고리즘 문제는 1406 에디터 문제인데요, 명령으로해서 문자열들을 처리할 수 있는지 여부를 알 수 있었던 문제였습니다. 그럼 풀이 들어갈게요! 문제 링크 에디터 1406번문제https://www.acmicpc.net/problem/1406 문제한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다.이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커..

안녕하세요 감자코딩에 감자개발자입니다. 오랜만에 포스팅을 하게 되었는데요. 1일 1알고리즘 포스팅을 할예정이라 알고리즘을 많이 올리게될것같습니다. 쇠막대기 10799번 문제 링크https://www.acmicpc.net/problem/10799문제여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않..

안녕하세요 감자코딩에 감자개발자입니다^^ 오랜만에 포스팅을 하는데요. 오늘 알아볼 알고리즘개념은 트리 입니다. 자료구조론에서 가장 기본중에 기본이면서 중요한 개념을 살펴보도록 하겠습니다. * 트리(Tree)란? 임의의 노드에서 다른 노드로 가는 경로(path)는 유일하다.회로(cycle)가 존재하지 않는다.(사이클이 없는 그래프)모든 노드는 서로 연결되어 있다.정점의 개수(Vertex)간선의 개수 (Vertex - 1)엣지(edge)를 하나 자르면 트리가 두 개로 분리된다.엣지(edge)의 수 |EE| 는 노드의 수 |VV|에서 1을 뺀 것과 같다. * 트리 구조에서의 용어 정리 (1). 노드(Node) 보통 데이터 트리 구조에서의 하나의 데이터들이 하나의 영역을 차지하는 곳을 노드라고 한다. (2). ..

감자 코딩에 감자개발자입니다. 이번시간에 살펴볼 개념은 Quick sort 퀵정렬입니다. 1. 퀵정렬의 특징 1) 불안정한 정렬2) 다른원소와 비교했을때 "비교 정렬"이라 칭합니다.3) 매우 빠른정렬방식4) 분할정복 방식(divide and conquer) -큰 문제를 작은문제 1,2로 분할하는 방식5) 시간복잡도 O(nlogN) 2. 퀵정렬 과정 1) 리스트 하나의 요소 Selection "pivot"2) 피벗 기준으로 피벗보다 작으면 "왼쪽"3) 피벗 기준으로 피벗보다 크면 "오른쪽"4) 피벗 제외한 왼쪽/오른쪽 리스트 다시 재정렬(순환호출)5) 부분 리스트들이 더이상 분할 불가능할때까지 반복한다.

감자 코딩에 감자 개발자입니다. 이번에 살펴본 내용은 알고리즘의 Sort중 하나인 합병정렬(Merge Sort)입니다. 1.합병 정렬(Merge Sort) 시간복잡도와 공간복잡도 합병정렬 (InsertSort)의 시간복잡도는 밑이 2 인 O(nlogn) 왜 이렇게 시간복잡도가 나올까요?바로 합병정렬의 가장큰 특징인 분할후 -> 합병이라는 것때문입니다. N -> N/2 형식으로 나누게되므로 계속분할되면 nLogN만큼의 복잡도가 나오게됩니다. 2. 합병 정렬 원리 합병정렬이란? 전체 원소를 하나의 단위로 분할 한후 분할한 원소를 다시 합병하는 방식이다. 원리) 1. 전체 원소를 1로 분할할때 까지 분할하여 계속해서 진행한다. 2. 다 나누어 졌으면, 그 원소들을 다시 비교하면서 Merge한다. - 예시 40..

감자 코딩에 감자 개발자입니다. 이번에 살펴볼 내용은 알고리즘의 Sort중 하나인 삽입 정렬(Insertion Sort)입니다. 1.삽입 정렬(Insertion Sort) 시간복잡도와 공간복잡도 삽입정렬 (Insertion)의 시간복잡도는 O(N^2) 2. 삽입 정렬 원리 가장 먼저 삽입 정렬에서의 원리를 살펴봅시다.가장 Array[0]에 있는 값과 Array[1],[2].....[N]까지의 값과 비교를 해갑니다.이때, Array[0]와 비교해가면서 값의 크기를 비교합니다.값이 더 작으면Array[0]와 값을 바꿔치기해줍니다.그리고, 바꿔치기한 값으로 부터 지금까지 진행비교 중이던 인덱스부터 다시 비교를 시작합니다. 예를 들어 Array[0] 과 비교를해서 가다가 Array[2]에서 Array[2]값이 ..

감자 코딩에 감자 개발자입니다. 이번에 살펴볼 내용은 알고리즘의 Sort중 하나인 선택정렬(SelectionSort)입니다. 1.선택정렬(SelectionSort) 시간복잡도와 공간복잡도 선택정렬(SelectionSort)의 시간복잡도는 O(N^2) 공간복잡도는 하나의 배열만을 사용하여 정렬하기 때문에 O(N)입니다. 2. 선택정렬 원리 크기가 N인 배열 1,2,3......N까지의 배열이 있다고 생각을 해봅시다. 이제 처음부터 비교를 하기 시작합니다. 1. 맨처음 Index[0] 값을 기준으로 index[1], index[2] ...... index[N]까지의 값들을비교합니다. 2. 이중에서 Index[0] 값과 비교하여 가장 작은수를 index[0]와 위치를 변경해줍니다. 3. 그다음 Index[1]..

감자코딩에 감자개발자입니다. 이번에는 워밍업 문제로 다이아몬드 찍어보기를 해보겠습니다. 등차수열로 이용하여 다이아몬드를 형성하였습니다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * Created by kgh on 2018. 8. 17. * Blog : http://kgh940525.tistory.com * Github : http://github.com/kgh940525 */ // comment: Diamond - Star public class Diamond_Star{ public static void main(String args[]) throws IOException ..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * Created by kgh on 2018. 8. 18. * Blog : http://kgh940525.tistory.com * Github : http://github.com/kgh940525 문제 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 예제 입력..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * Created by kgh on 2018. 8. 18. * Blog : http://kgh940525.tistory.com * Github : http://github.com/kgh940525 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 49603 16098 10473 32.213% 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 ..

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; /** * Created by kgh on 2018. 8. 18. * Blog : http://kgh940525.tistory.com * Github : http://github.com/kgh940525 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 49603 16098 10473 32.213% 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 ..

안녕하세요 감자코딩에 감자개발자입니다. 이번시간에 알아볼 개념은 점근적 표기법과 시간복잡도와 공간복잡도 입니다. 1. 알고리즘 성능분석 - 시간 복잡도(Time Complexity) : 알고리즘의 수행시간 분석결과- 공간 복잡도(Space Complexity) : 알고리즘의 메모리 사용량에 대한 분석결과 * 점근적 표기법(Asymptotic notations) 1) 빅오 표기법(O notation) - 내가 생각하는함수가 다른 기준이되는 함수보다 아래쪽에 있다. 아무리 느려진다고해도 기준함수보다는 빠르다. 빅오표기법에 대한 간략한 내용입니다. 이제 빅오표기법에대한 예를 한번 확인해보겠습니다. 예)3n+1 = O(n^2) n>=n0에 대해 3n+1 =4을 만족하면 위의 식은 항상 성립한다. 요약하자면, f..

/* 문제 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 대나무를 먹는다. 그런데 단 조건이 있다. 이 판다는 매우 욕심이 많아서 대나무를 먹고 자리를 옮기면 그 옮긴 지역에 그 전 지역보다 대나무가 많이 있어야 한다. 만약에 그런 지점이 없으면 이 판다는 불만을 가지고 단식 투쟁을 하다가 죽게 된다(-_-) 이 판다의 사육사는 이런 판다를 대나무 숲에 풀어 놓아야 하는데, 어떤 지점에 처음에 풀어 놓아야 하고, 어떤 곳으로 이동을 시켜야 둘 다 소중한 생명이지만 판다가 최대한 오래 살 수 있는지 고민에 빠져 있다. 우리의 임무는 이 사육사를 도와주는 ..

#include #include using namespace std; int main() { int n; // 입력 최대붕어 int fish_price[1001]; // 붕어 가격 int dp[1001]; // 붕어 저장 dp scanf("%d", &n); // 붕어 수 입력 // 붕어 가격 입력 for (int i = 1; i