본문 바로가기

Programming/Algorithm 193

해쉬 테이블(Hash Table) Hash Table 저장되는 데이터는 키와 값이 하나의 쌍을 이룬다. 키가 존재하지 않는 값은 저장할 수 없다. 그리고 모든 키는 중복되지 않는다. 가장 쉬운 예로 다세대 주택이나 아파트의 우편함입니다. 우편함의 경우 호수가 키가 되고 우편함에 들어있는 우편물이 값이 됩니다. 자료구조의 테이블은 사전구조라고도 불린다. 더불어 맵이라 불리기도 합니다. 123456789101112131415161718192021222324252627#pragma warning(disable:4996) #include typedef struct _empInfo{ int empNum; // 직원의 고유번호 int age; // 직원의 나이}EmpInfo; int main(void){ EmpInfo empInfoArr[1000].. 2018. 5. 7.
Recursion (재귀함수) 재귀는 수학이나 컴퓨터 과학 등에서 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻합니다. 주로 이 방법은 함수에 적용한 재귀 함수의 형태로 많이 사용됩니다. 재귀함수는 반드시 탈출 조건이 있어야 합니다. 그렇지 않으면 무한히 호출되어 프로그램이 멈추게 됩니다.(무한루프) 아래는 간단하게 Factorial 을 구현한 코드입니다. 1234567891011121314151617#include int factorial(int n) { printf("%d ", n); if (n 2018. 5. 7.
배열기반 리스트(ArrayList) #include #include "ArrayList.h" int main(void) { List list; // 구조체 변수 선언. int data; ListInit(&list); // 선언한 변수 초기화. LInsert(&list, 11); LInsert(&list, 11); LInsert(&list, 22); LInsert(&list, 22); LInsert(&list, 33); printf("current data num : %d \n", LCount(&list)); if (LFirst(&list, &data)) { printf("%d ", data); while (Lnext(&list, &data)) printf("%d ", data); } printf("\n\n"); if (LFirst(&lis.. 2018. 5. 7.
크루스칼 알고리즘(Kruskal's algorithm) 목차 개요최소 스패닝 트리크루스칼 알고리즘크루스칼 알고리즘의 구현문제 개요 크루스칼 알고리즘은 무향 연결 그래프가 주어질 때, 최소 스패닝 트리라고 부르는 서브 그래프를 찾는 알고리즘입니다. 크루스칼 알고리즘은 유니온 파인드 자료구조에 사용합니다. 최소 스패닝 트리(minimum spanning tree) 해당 그래프의 모든 정점을 포함하는 트리 형태의 서브 그래프를 뜨샇ㅂ니다. 왼쪽 그래프에서 스패닝 트리를 하나 찾아보면 오른쪽 트리가 나옵니다. 스패닝 트리는 여러개 있을 수 있습니다. 그런 스패닝 트리들 중에서 간선의 가중치의 합이 가장 작은 스패닝 트리를 최소 스패닝 트리라고 부릅니다. 최소 스패닝 트리 중 하나를 찾음으로서 간선의 가중치의 합의 최솟값을 찾는 알고리즘입니다. 크루스칼 알고리즘 크루.. 2018. 5. 4.
유니온 파인드(Union-find) 목차 개요초기화간단한 방법최적화 단계 1최적화 단계 2 - 유니온 파인드 트리유니온 파인트 트리 - 코드문제 개요 집합을 관리하는 자료구조로서, disjoint set이라고 부르기도 합니다. 이 자료구조를 활용하면 아래의 두 가지 연산을 수용할 수 있습니다. 요소 에이와 요소 비가 같은 집합에 속하는지 확인.요소 에이가 속한 집합과 요소 비가 속한 집합을 병합. 이런 식의 두 연산을 효율적으로 하기 위한 자료구조가 유니온 파인드, disjoint set 입니다. 초기화 초기 상태는 각각의 요소가 따로 따로 집합에 속하는 상태입니다. 이 상태를 만들어 주는 간단한 방법으로 아이번째 요소는 아이번째 집합에 속한다 라고 지정하는 방법이 있습니다. 간단한 방법 same_set()함수의 시간복잡도는 O(1) me.. 2018. 5. 3.
백준 13460 구슬 탈출 2 1. 큐가 먼저 끝나는 경우도 있음.2. 10이되기 전에 끝나는 경우에도 처리를 해주어야 합니다.3. cnt 와 종료조건에 대해서 명확하게 합니다.4. 시간에 관해서 ++ 와 종료조건에 대해서 명확하게 합니다.5. 10번이하이므로 10번까지 가능합니다. 10번 돌렸는데, 정답을 못찾으면 리턴합니다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211.. 2018. 4. 14.
백준 12100 2048 1. 아이디어를 명확하게 구현하기.2. 흐름을 말로 설명하고 나서, 코드를 구현하도록 합니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151.. 2018. 4. 14.
백준 3190 뱀 1. 문제를 꼼꼼히 읽습니다.2. 사용하는 변수와 자료구조를 고려하여 선택합니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124/*3190 뱀19:45 시작합니다.20:2439분컷설계 과정1. 문제를 꼼꼼하게 읽습니다.2. 설계를 완벽하게 합니다. (예제 3개 돌리기)3. 경우의 수를.. 2018. 4. 14.
백준 13458 시험 감독 풀이 과정1. 총감독관에 대해서 더해주고2. 부감독관에 대해서 더해주면 됩니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960/*19:37 6분 컷시험 감독 13458설계 과정1. 문제를 꼼꼼하게 읽습니다.2. 설계를 완벽하게 합니다. (예제 3개 돌리기)3. 경우의 수를 나열 합니다.4. 초기화 변수를 확인합니다.5. 가지치기를 합니다.6. 예제와 동일한 변수를 선언하고 사용합니다.풀이 과정.총 감독관의 숫자를 먼저 계산하고,부 감독관의 숫자를 나누기로 계산합니다.*/ #include #include using namespace std; int N, .. 2018. 4. 14.
백준 14499 주사위 굴리기 설계 과정1. 문제를 꼼꼼히 읽습니다.2. 설계를 정확하게 합니다. (예제 3개 돌리기)3. 경우의 수를 나열합니다.4. 초기화 변수를 확인합니다.5. 가지치기를 합니다.6. 예제와 동일하게 변수를 선언하고 사용합니다. 풀이 과정1. 주사위를 굴린다음에,2. 주사위의 바닥면과 맵을 비교해줍니다.3. 주사위의 윗면을 출력합니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071.. 2018. 4. 14.

티스토리툴바