Algorithm 썸네일형 리스트형 퀵정렬알고리즘 퀵정렬 알고리즘 - 피벗을 활용한 알고리즘 - 피벗을 통해서 그룹을 두 그룹씩 나누는 것을 반복한다.- 피벗이 그룹 요소가 하나일 때 최종적으로 정렬이 완료된다. PIVOT 위치에 있는 6을 기준으로 포인터 PL이 가리키는 값은 6보다 작을 경우 계속 우측으로 이동하고 6보다 클 경우 해당 위치에서 멈춘다. 가령, 값이 7인 부분에서 PL 포인터는 멈출 것이다. 반대로 PR 부분은 6보다 클 경우 계속 좌측으로 이동한다.6보다 작을 경우 해당 위치에서 멈춘다.가령, 값이 4인 부분에서 PR 포인터는 멈출 것이다. 그렇게 될 경우, 7과 4의 위치를 교환하여 다시 정렬한다.이 과정을 PL의 포인터와 PR포인터가 교차될 경우 멈춘다.그러면 정렬은 아래와 같이 바뀔 것이다. 1차 퀵소트를 진행하면 PL이 PR.. 더보기 Danji_알고리즘_sort 오늘 풀어 볼 문제는 단지에 이름 붙이기 문제입니다.문제는 다음과 같으며 풀기 전 조건을 먼저 생각해야합니다.단번에 탐색 문제라고 확인할 수 있는데, 탐색할 때의 조건을 어떻게 두면 좋을지 고민해야합니다. 우선 2차원배열 map으로 설정했다고 했을 경우, 1이 나온 곳만 탐색을 시작합니다.이 중 반복문을 두어서 1이 나온 곳을 파악하고 거기서부터 동서남북으로 탐색을 시작합니다.더이상 탐색할 곳이 없을 경우 재귀 호출을 리턴하여 멈추게합니다. 탐색 횟수를 카운트해서 메모리에 추가하고 다음 1이 나온 곳을 찾아서 탐색합니다.앞서 내용을 반복하면서 카운팅한 변수들을 메모리에 추가하여 반환하면 이 문제는 해결됩니다. 주의할 점은 아래와 같습니다. 1. 탐색할 때 기저조건은 탐색할 곳이 더이상 없을 경우가 됩니다.. 더보기 toBin_알고리즘 오늘 포스팅한 문제는 2진수 표현 방법 중, 1의 갯수를 표현하되, 큰 수부터 표현하는 것입니다.처음에는 Permutation으로 접근하여 경우의 수를 모두 뽑아낸 다음에 대소비교를 통해 출력하려 했으나,크기 비교 후 표현하기에는 코드가 깔끔하지 못했고, 뿐만 아니라 출력시엔 10진수로 고려하여 출력하기 때문에 0011과 같은 값을 표현하기에는 어려움이 많았습니다. 이러한 우여곡절을 겪은 뒤에, 재귀 호출을 통해서 1을 먼저 배열에 넣고 1의 갯수를 넘어설 경우 배열에 0을 넣을 수 있도록구현하는 것입니다. 이 후에는 배열의 길이가 전체 설정한 길이만큼 커졌을 때 (같을 경우) 배열 요소를 출력하고 함수를 리턴하는 것입니다.여기서 리턴될 때 1의 갯수를 체크하는 변수부분이 호출 전 상태로 들어오기 때문에.. 더보기 N_Queen 오늘은 N_Queen 문제를 체크해보려합니다.가장 대표적인 재귀형 문제이자, 백트래킹의 개념이 들어간 문제이기도 합니다.우선 N_Queen의 조건을 체크해봅시다. 조건1. 각 행에는 퀸을 중복해서 둘 수 없다.조건2. 각 열에는 퀸을 중복해서 둘 수 없다.조건3. 각 대각선 (사선 두 방향)은 퀸을 중복해서 둘 수 없다. 함수를 만들때 열에 대해서 n번의 재귀를 통해서 반복하는 함수를 만든다.이 함수 안에서는 n-1번째 열에 대해서 행이 0부터 n-1번째까지 반복을 통해 체크하도록 한다.이렇게하면 결국 행과 열 모두 다 도는 것과 마찬가지다. 단! 조건1과 조건2를 만족시키기 위해서는 반복을 돌 때 재귀를 통해 열에 대해서 0행에 모두 퀸을 배치시킬 경우,다음 열에 대해서는 0행이 아닌 다른 곳에 퀸을 .. 더보기 BOJ_1268_임시 반장 정하기 안녕하세요 이번에는 임시 반장 정하기 acm 대회 문제를 풀어보도록 하겠습니다. 문제에 중요한 개념이 들어가기 때문에 같이 정리하면서 알아보겠습니다. 문제는 다음과 같으며 이 문제를 풀기 위해서는 먼저 어떻게 문제를 접근해야 할 지 생각해야 합니다.문제에서 묻는 것을 문장으로 풀어서 작성해보겠습니다. 1번 학생이 1학년때부터 5학년때까지 같은 반으로 지낸 학생이 몇 명이 있는가? 2번 학생이 1학년때부터 5학년때까지 같은 반으로 지낸 학생이 몇 명이 있는가? .... n번 학생이 1학년때부터 5학년때까지 같은 반으로 지낸 학생이 몇 명이 있는가? 여기서 중요한 것은 1번 학생이 만약 2학년때 2번 학생과 같은 반이 되었다고 가정한다면, 2학년을 제외한 다른 학년에서 두 학생이 같은 반이 되었다고 하더라도.. 더보기 하노이탑 알고리즘 오늘 포스팅은 하노이탑 알고리즘에 대해서 설명드리려고 합니다.재귀함수로 표현해서 코드를 구성했는데, 다음 포스팅에서는 비재귀함수로 코드를 구성해보겠습니다.우선 기본 틀은 다음과 같습니다. 1. 첫 번째 기둥에 (1,2,3) 원반이 있고 두 번째 기둥은 비어있고 세 번째 기둥 또한 비어있습니다.2. 첫 번째 기둥에 있는 원반들을 온전히 세 번째 기둥으로 옮기는 과정을 겪어야합니다.3. 하노이탑 완성 과정의 횟수를 카운트해서 출력하겠습니다. 핵심은 원반을 그룹으로 보는 것이다. 마치 Dynamic Programming과 같은 방법이라 하면 된다.우선 글로 설명을 먼저하고 이해를 돕기 위해 그림을 첨부하겠다. 1. 0번째 원반을 제외한 나머지 1번~n-1번째의 원반을 하나의 그룹이라 생각한다.2. 1번~n-1.. 더보기 배열 요소 최대공약수 구하기 안녕하세요! 오늘은 유클리드 호제법을 활용한 배열 요소의 최대 공약수 구하기 문제를 해결해보려합니다. X라는 값을 Y로 나눌 때 나눈 값이 X%Y라면 이걸 Y로 다시 나누고 이 과정을 반복해서 하면 됩니다.예를 들어, 10과 25의 최대 공약수를 구한다고 할 때 25의 길이 만큼의 상자를 10인 상자로 채우다가 남은 5만큼의 공간을 다시 5로 채우고 더이상 채울 곳이 없을 때 나눴던 5를 반환하는 것이다.가령 22와 8이라는 숫자로 비교한다면, 길이 22만큼의 공간을 차지하는 상자에 8만큼의 공간을 차지하는 상자를 넣었을 때6만큼의 공간이 남을 것이다. 즉, 8x6만큼의 공간이 남을테고, 이를 6x6 상자로 채웠을 때 2x6만큼의 공간이 남을 것이다.따라서 2x2인 상자로 채워서 빈 공간이 없도록 만들 .. 더보기 기수변환 알고리즘 이번 포스팅에서는 10진수를 2~36진수의 기수변환을 하는 코드를 작성하려 합니다. 기수변환의 기본 구조인 틀을 이해하되, 어떻게 표현할 지 생각하면서 정리해봅시다. 다음과 같은 꼴이 나옵니다. 만약 10진수를 2진수로 기수변환을 할 경우, 나누는 값을 2로 계속 나누면서 0이 나올 때 까지 나눈 나머지를 모두 문자열처럼 합하여 표현하는 것입니다.저는 이렇게 나눈 나머지를 배열에 넣어서 2진수로 표현할 것입니다. 또 신경써야 할 것은 2진수부터 36진수까지 표현입니다. 2진수로 표현을 한다면 함수에 들어오는 값(나누는 값)에 대해서 %2 만을 배열에 넣으면 되는데, 36진수까지 표현하려면 매번 나누는 값을 변환하는 번거로움이 있을 것입니다.따라서, 36진수까지 표현하는 방법인 0~Z까지의 값을 문자열에 .. 더보기 이전 1 2 3 4 5 6 다음
