관광이 블로그

감자 코딩에 감자 개발자입니다. 이번에 살펴본 내용은 알고리즘의 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 max_score(int a, int b) { return a > b ? a : b; } int main(void){ int stair_num; // 계단수 변수 int stair_score[301] = {}; // 계단수 300 int store[301] = {}; // 계단 저장 배열 변수(dp) scanf("%d", &stair_num); // 계단수 입력 // 계단 점수 입력 for (int i = 1; i = 2){ store[2] = store[1]+stair_score[2]; } for(int i=3; i

#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

안녕하세요 감자코딩에 감자개발자 입니다. 벌써 일요일이 끝나고 월요일이네요. 저는 이번에 공부해볼 강의는 알고리즘중에 꽃이라고 할 수 있는 Dynamic Programming(동적계획법)에 대해서 공부하겠습니다. 1. 동적계획법이란 무엇인가? 간단히 말해서 큰문제를 작은문제로 나누어서 푸는 기법이라고 할 수 있습니다.=(유사) 분할정복방법과 비슷합니다. 2. 동적 계획법의 대표적인 예이항계수(nCr)의 계산이라고 할 수 있습니다. 3. 메모이제이션(memoization) 이란? 동적계획법에서는 중복을 막기위해서 저장된 값을 배열에 저장한 뒤, 다음 계산이 필요할때는 저장된 값을 불러와서 중복을 없애면 함수호출이 줄어들게 됩니다. 그러면, 시간복잡도도 훨씬 줄어들게 됩니다. 밑에 예제는 피보나치 수열에 관..

안녕하세요. 감자코딩에 감자개발자 입니다. 이번강의에서 다룰 내용은 엠베딩 방법론입니다. 1. 단어를 벡터화하는 방법론 3가지를 설명드리겠습니다. 대표적인 벡터화 방법론은 Word2Vec, Glove, FastText 가 있습니다.이중에서 가장 큰 특징은 단어 동시 등장 정보(word's of no-occurence)를 보존한다는 점입니다. 2. Word2Vec 이란? 단어를 벡터로 바꾸어주는 방법론입니다. 3. Word2Vec의 종류? CBOW(Continuous Bag of Words) 와 Skip-Gram 방식 두가지가 있습니다. CBOW 방식 예) 감자코딩은 _____ 하는것을 좋아한다. ___에 들어갈 단어를 예측할 수 있으신가요? 주변단어를 통해 중심단어를 맞추어내면서 벡터화로 만드는 방식을 ..

/*유기농 배추 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 21498 7021 4937 32.333% 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. (한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있다고 간주한다) 한나가 배추를 재배하는 땅은 ..

/* 단지번호붙이기 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 19045 7136 5006 38.328% 문제 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 입력 첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N..