전체 글

문제링크 : https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또는 대각선으로 연결되어 있는 사각형은 걸어갈 수 있는 사 www.acmicpc.net 문제설명 맵에서 1은 섬을 나타내고 0은 바다를 나타낸다 섬은 상하좌우 대각선 총 8방향으로 이어져있을때, 주어진 배열의 섬의 갯수를 구하여라. 알고리즘 1. DFS 를 이용하여 8방향을 탐색 하여 컴포넌트의 갯수를 출력한다. 코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495..

문제링크 :https://www.acmicpc.net/problem/6603 6603번: 로또 문제 독일 로또는 {1, 2, ..., 49}에서 수 6개를 고른다. 로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 수 중 k(k>6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 www.acmicpc.net 문제설명 1. 수열이 주어지고 그 수열의 조합을 출력하면 되는문제 알고리즘 1. 재귀함수를 이용하여 수열의 조합을 출력하면됨 코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include#include using na..

문제링크 :https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제설명 1. N개의 단어가 주어졌을 때 길이가 짧은것부터 출력 2. 길이가 같은 건 사전순으로 출력하고 똑같은 단어는 하나만 출력 알고리즘 1. 비교함수를 정의 해준다 - 길이 순으로 정렬 -> 사전순으로 정렬 -> 똑같은 단어는 하나만 출력. 코드 12345678910111213141516171819202122232425262728293031323334353637#include#..

병합 정렬이란 분할 정복 기법을 이용한 정렬기법 이다. 기본 개념은 일단 반으로나누고 나중에 합친다. 이것이 기본 개념이다. 시간 복잡도는 O(N*logN) 이다. 알고리즘 밑에 그림을 살펴보자 . 1. 초기 상태에서 더이상 반으로 나눌수 없을 때까지 계속 분할한다. 2. 그리고 다시 병합(merge) 할 때 크기를 비교하여 병합한다. 3. 병합을 모두 마무리하면 정렬이 완료된다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 ..

계수 정렬 이란 단순히 '크기 기준' 으로 세는 알고리즘이다. 범위가 한정되어있을때 가장 빠른 속도를 낸다. 시간 복잡도는 O(N) 이다. 알고리즘 1. 사실 알고리즘 이라고 할것도 없다. 2. 그냥 배열에서 해당 숫자의 갯수를 센다음 3. 작은 값부터 갯수만큼 출력하면된다 .. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 #include int main(void) { int count[5] = { 0,0,0,0,0 }; int data[20] = { 2,3,4,1,3,5,4,2,1,3,2,4,5,1,2,3,5,4,2,3 }; // 반복문 한번으로 정렬 완료 for (int i = 0; i

힙정렬을 이해하기 위해서는 아래 3개의 정의를 알고 가야함 . 이진 트리 : 모든 노드의 자식이 2개 이하인 트리. 완전 이진 트리 : 데이터가 루트 노드 부터 시작해서 왼쪽 부터 빼곡하게 차있는 트리 형태 힙 (heap) : 완전 이진 트리의 일종으로 최댓값, 최솟값을 쉽세 추출 할 수 있는 자료구조 이다. 최대 힙 : 부모 노드가 자식 노드보다 큰 힙 최소 힙: 부모 노드가 자식 노드보다 작은 힙 힙 정렬 : 자료구조 '힙(heap)'을 이용하여 최대 힙 트리나 최소 힙 트리를 구성해 정렬 하는 방법 오름 차순으로 정렬 을 하기 위해서는 최대 힙을 사용하고 , 내림차순은 최소힙을 사용. 힙 정렬의 시간 복잡도는 O(N*log N) 이다. 정렬 순서 알고리즘 오름차순 기준 1. 현재 배열을 최대 힙구조..