관광이 블로그

안녕하세요 감자코딩에 감자개발자입니다^^ 오랜만에 포스팅을 하는데요. 오늘 알아볼 알고리즘개념은 트리 입니다. 자료구조론에서 가장 기본중에 기본이면서 중요한 개념을 살펴보도록 하겠습니다. * 트리(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..

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

/* 토마토 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 128 MB 30813 8424 5397 26.207% 문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창..

/* 숨바꼭질 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 2 초 128 MB 35272 9761 6127 24.946% 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정..

안녕하세요 감자코딩에 감자개발자 입니다.이번에 살펴볼 내용은 백준알고리즘에 2178번 미로 문제입니다. 문제 링크https://www.acmicpc.net/problem/2178 /* 문제 N×M크기의 배열로 표현되는 미로가 있다. 1 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 0 1 1 미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다. 입력 첫째 줄에 두 정수 N, M(2≤N, ..

안녕하세요! 관광이 개발블로그의 관광이 입니다이번에 알아볼 STL의 종류중 하나인 VECTOR에 대해서 살펴보겠습니다. 1. Vector Container VectorContainer는 자동으로 메모리가 할당되는 배열이라고 합니다. 대표적인 메소드로는- v.front() - 가장 앞 위치- v.back() - 마지막 위치- v.push_back() - 가장마지막에 원소 push- v.pop_back() - 가장 마지막 원소 pop 맨뒤쪽에서 삽입과 삭제가 가능하다. 2. Vector Container 사용시 필요한 사항#include == vector v; 라고 가정.== 참조 한다는 것은 해당 데이터를 리턴 한다는 뜻입니다. v.assign(5, 2);- 2의 값으로 5개의 원소 할당. v.at(idx..