박스여우 - BoxFox

■ 잡담Linked List의 장단점이 무엇입니까? 면접관님의 질문이였습니다. 지원자는 그 순간 머리를 재빠르게 굴리기 시작했지만 시원한 답변을 하지 못했습니다. 지원자는 Linked List의 구조를 숙지하고는 있었지만, 장단점에 대해서는 인지를 하고있지 못했기 때문입니다. 이번 포스팅에서는 이와같은 불상사가 발생하지 않기 위해 Linked List를 이해하고 그의 장단점에 대해 알아보도록 하겠습니다. ■ 단일 연결 리스트연결 리스트는 각각의 노드가 다음 노드를 가리키며 연결되어 있기 때문에 연결리스트라고 합니다. 단일 연결 리스트의 경우에는 각 노드가 다음 노드만을 가리키기 때문에 단일 연결리스트라고 불립니다. 단일 연결리스트에 대한 정확한 이해는 그림을 통해 확인해 보도록 하겠습니다. 단일연결리스트..

■ 잡담병합정렬에 대해서는 고등학교 1학년인 작년에 이미 배워서 직접 짜본적도 있었습니다. 하지만, 정렬 알고리즘을 사용하지 않다보니 배웠던것도 까먹게 되더군요.. 그래서 이번에는 병합정렬 알고리즘에 대해 알아보도록 하겠습니다. ■ 병합정렬병합정렬은 이름만 듣게되면 무언가 합치는 정렬이라고는 짐작이 될것 같습니다. 일부분은 맞는 말 입니다.병합정렬은 전체 원소를 하나의 단위로 분할한 후 분할한 원소를 다시 병합하는 정렬방식이며 분할정복 기법중 하나입니다. 1. 분할정렬되지 않은 데이터를 위의 그림과 같이 최소한의 크기로분할합니다. 2.합병분할한 데이터를 2 그룹씩 짝을지어 합병하고 정렬을 수행합니다. 이 과정을 반복하게 되면 최종적으로 데이터 정렬을 모두 마치게 됩니다. 3.정렬분할된 데이터를 정렬하며 ..

안녕하세요 박스여우입니다.Algorithm이번에는 선생님이 장난으로 내 주신 과제. 하노이탑에 대해 알아보도록 하겠습니다. 우선 하노이탑의 해결 과정을 알아내기 위해 Youtube의 여러 하노이탑 영상들을 찾아봤습니다.  저는 위의 두 영상을 보고 해결되는 규칙을 찾아냈습니다.위의 하노이탑 해결 과정에서 반복적으로 움직이는 블럭을 하나 찾아봅시다. 만약 위의 영상을 보고도 반복적인 모습을 찾지 못했다면 아래 영상을 통해 다시한번 살펴봅시다.  위의 영상에서 가장 작은 블럭의 움직임을 자세히 살펴보면,반복적으로 움직이고 있다는 모습이 보일 것 입니다.  가장 작은 블럭은 1번기둥, 2번기둥, 3번기둥 순으로 반복적으로 움직이고 있고,가장 작은 블럭이 한번 움직이면 가장 작은 블럭이 없는 다른 기둥의 둘중 ..

안녕하세요 박스여우입니다. 오늘은 탐색 알고리즘을 알아 보겠습니다. Algorithm 문제 상황 UN이 정상 회담때 각 국가의 대통령들에게 제공할 음료 100개를 준비했다. 하지만 대통령들을 암살할 목적으로 음료에 독극물을 타던 암살자가 붙잡혔다. 다행히 100개의 음료중 한 개의 음료에만 독극물이 타여졌다. 이 음료는 한개에 상상할 수 없을 만큼의 가격이고, 다시 제작할려면 3개월이나 기다려야 한다. 독극물은 매우 강력해서 독극물이 타여진 음료를 한 방울만 마셔도 즉사하게 된다. 여기서 독극물이 담긴 음료를 가장 적은 사람의 희생으로 찾을 수 있는 방법은? 단, 음료를 한번 시음한 사람은 다시 시음하여 독극물을 확인하지 않는다. 위의 문제 상황은 탐색 알고리즘을 유도할 수 있는 문제입니다. 아래에 답이..

안녕하세요 박스여우입니다. 이번에는 정렬 알고리즘의 최강자 퀵 정렬에 대해서 알아보도록 하겠습니다. 위 영상은 퀵 정렬 알고리즘의 이해를 돕기위해 만들어진 영상입니다. 퀵 정렬은 기준키(피벗)을 기준으로 작거나 같은 값을 지닌 데이터는 앞으로, 큰값을 지니면 뒤로 보내서작은값과 큰값을 분리해가는 방식의 알고리즘 입니다. 기준키를 left(제일 첫번째데이터)로 잡고, i값을 한개씩 증가시켜 기준키보다 큰값을 찾고,j값(right)값을 1씩 캄소시켜 기준키보다 작은값을 찾은뒤 두 데이터의 위치를 교환합니다. 계속해서 같은방식으로 진행하다가 i값과 j값이 서로 교차하면, 작은 데이터를 기준키의 데이터와 교환합니다.이렇게 되면, 기준키가 옮겨진 부분을 중심으로 앞쪽엔 작은값, 뒤쪽엔 큰값으로 나뉘게 되고,앞쪽에..

안녕하세요 박스여우입니다. 이번에 제가 풀어본 알고리즘문제 개미수열에 대해 준비했습니다. 알고리즘 문제를 풀때 가장중요한것은 규칙찾기입니다. 아래에 규칙이 설명되 있으나 스스로 규칙을 찾아 해결하는 능력을 길러야 문제해결 능력이 향상된답니다. 개미수열의 규칙은 위에서부터 1, 1이 한개있으니 11, 1이 두개있으니 12 1이 한개, 2가 한개있으니 1121 1이 두개, 2가 한개, 1이 한개있으니. 122111 1이한개, 2가두개,1이 세개있으니, 112213 ... 요런식으로 풀어나가는 수열입니다. 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 4..

안녕하세요 박스여우입니다. 요번에 새롭게 짜낸 알고리즘을 들고왔는데요, 바로 파스칼의 삼각형입니다. 알고리즘을 짜기위해선 규칙을 파악하시는게 우선입니다. 규칙이 아래에 설명되 있으니 파악하신뒤 내려보시는것을 추천드립니다. 파스칼의 삼각형은 테두리의값은 1이고, 양위쪽의 대각선의 값을더한값이 자식으로 나오는 트리구조입니다 파스칼의 삼각형의 규칙만 잘 파악하시면 배열을 이용해 쉽게 만드실수 있습니다. 1열의 첫번째와 두번째를 합친것이 2열의 2번째, 2열의 첫번째와 두번째를 합친것이 3열의 2번째, 2열의 두번째와 세번째를 합친것이 3열의 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..

다음과 같이 출력하는 알고리즘을 작성해보세요 #pragma warning(disable : 4996) #include int main(){ int input; scanf(" %d", &input); int arr[100][100] = { 0, }; int print = 1; //저장될 변수 int t = 0, l = 0; //t는 세로, l은 가로 while (1){ int checkt = t; //임시 세로 int checkl = l; //임시 가로 while (1){ arr[checkt][checkl] = print; print++; if (checkt==0){ break; } else if (checkl == input - 1){ break; } checkt--; checkl++; } if (t =..

다음과 같이 출력되는 알고리즘을 작성해 보세요 #pragma warning(disable : 4996) #include int main(){ int input; scanf(" %d", &input); //출력할 사이즈를 입력받는다. int print = 1; int t=0, l=0; //t = 세로, l = 가로 int check = input,checks=0; //check = 배열의 최대값, checks = 배열의 최소값 int arr[100][100] = { 0, }; for (int i = 0; i < input; i++){ //input 회수만큼 for문을 돌린다. for (; l < check;l++){ //맨 윗줄 가로열 저장 arr[t][l] = print; print++; } l--; /..