알고리즘 & 자료구조
-
[Algorithm] 완전탐색 (Brute-Force Search ) 알고리즘알고리즘 & 자료구조/알고리즘 2021. 6. 20. 22:04
완전 탐색이란? 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법 '무식하게 푼다'라는 의미로 Brute-Force 라고 하기도 한다. 완전 탐색 기법 완전 탐색 방법을 이용하기 위해서 여러가지 알고리즘 기법이 이용된다. -단순 Brute-Force -비트마스크(Bitmask) -재귀 함수 -순열 (permutation) -BFS / DFS (너비 우선 탐색 / 깊이 우선 탐색) 1. 단순 Brute-Force 단순히 for문과 if문 등으로 모든 case들을 만들어 답을 구하는 방법 2. 비트마스크 2진수를 이용하는 컴퓨터의 연산을 이용하는 방식 3.재귀 함수 재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식 4.순열 서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N 이므로 완전 ..
-
[Data Structure] 힙 (heap)알고리즘 & 자료구조 2021. 6. 14. 17:47
힙(heap)이란? 힙은 일종의 트리로 수의 집합에서 가장 작은 수(키)나 가장 큰 수만을 자주 꺼내올때 유용한 자료구조 힙은 완전 이진 트리를 사용하는데 완전이진트리는 자식은 항상 2개, leaf의 가장 왼쪽부터 채우는 트리구조이다. 힙에는 최대힙과 최소힙이 있는데 최소힙은 가장 작은 값이 루트이고 최대힙은 가장 큰 값이 루트이다. 1.힙이 삽입(insert) 되는 과정 here 는 현재 삽입될 위치, 인덱스는 8 5와 1을 비교한다. 1이 더작으므로 5는 here의 자리에 오게된다. 이제 here의 인덱스는 4, 4와 1을 비교한다. 1이 더 작으므로 here의 자리는 4가 들어간다. 마찬가지로 동일하게 1과 2를 비교, 2가 더 크기 때문에 here에는 2가 들어가게 된다. 이제 더이상의 부모는 없..
-
알고리즘 시각화 해서 볼 수 있는 사이트알고리즘 & 자료구조/알고리즘 2021. 3. 22. 21:12
www.pythontutor.com/visualize.html#mode=edit
-
[프로그래머스] [1차] 비밀지도 (C++)알고리즘 & 자료구조/코딩테스트 2021. 3. 6. 18:54
문제 설명 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 "공백"(" ") 또는 "벽"("#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 "지도 1"과 "지도 2"라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. "지도 1"과 "지도 2"는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도..
-
[알고리즘] 삽입 정렬(Insertion Sort)알고리즘 & 자료구조/알고리즘 2021. 3. 6. 17:32
아래의 숫자들을 오름차순으로 정렬한다고 생각해보자 1 10 5 8 7 6 4 3 2 9 버블 정렬과 선택정렬을 사용 할 수도 있지만, 삽입 정렬을 사용하면 특정상황에 따라서는 보다 효율적으로 정렬할 수 있다. 다른 정렬들은 무조건 위치를 바꾸는 방식이였지만, 삽입정렬의 다른점은 '필요할 때만' 위치를 바꾼다는 것이다. 예를들어 보자, 아래와 같은 숫자들을 오름차순 정렬한다고 했을때, 삽입정렬은 1 10 5 8 7 6 4 3 2 9 바로 옆의 10과 대소를 비교한다. 10은 1의 앞 혹은 지금 현재 자리에 있을 수 있는데, 오름차순이기때문에 현재 위치를 그대로 유지하면 된다. 그다음 10 과 5를 비교해보면, 5가 더 작기때문에 10과 5의 자리를 바꿔준다. 조금 더 쉽게 생각하면 빈칸이 있다고 생각을 해..
-
[프로그래머스]3진법 뒤집기알고리즘 & 자료구조/코딩테스트 2021. 3. 4. 18:28
문제 설명 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수입니다. 입출력 예 n result 45 7 125 229 입출력 예 설명 입출력 예 #1 답을 도출하는 과정은 다음과 같습니다. n (10진법)n (3진법)앞뒤 반전(3진법)10진법으로 표현 45 1200 0021 7 따라서 7을 return 해야 합니다. 입출력 예 #2 답을 도출하는 과정은 다음과 같습니다. n (10진법)n (3진법)앞뒤 반전(3진법)10진법으로 표현 125 11122 22111 229 따라서 229를 return 해야 합니다. 벡터의 push_ba..
-
[알고리즘] 선택 정렬 (Selection Sort)알고리즘 & 자료구조/알고리즘 2021. 3. 4. 11:28
예를 들어 *1 10 5 8 7 6 4 3 2 9 * 라는 숫자들을 오름차순으로 정렬하려고 한다고 가정해보자 사람이라면 직관적으로 보고 작은 수 를 찾아 순서대로 정렬하겠지만, 컴퓨터는 배열을 하나하나 읽기전 까지는 어떤 값이 들어있는지 알지 못한다. 따라서 정렬을 위해서는 알고리즘이 필요하다. 그 중에서도 선택정렬은 모든 배열을 탐색 후, 가장 작은 수를 앞으로 보내는 방식으로 동작한다. ex) arr[10] *1 10 5 8 7 6 4 3 2 9 * 모든 배열을 탐색 후 , 1이 가장 작은 숫자로 알맞은 위치에 있으므로, 이제는 1을 제외한 10 부터 9까지를 탐색해준다. *1 2 5 8 7 6 4 3 10 9 * 나머지 배열중에 가장 작은 수는 2이므로 arr[1] 인덱스의 값으로 넣어주고 원래 2..
-
[프로그래머스]내적(C++)알고리즘 & 자료구조/코딩테스트 2021. 3. 3. 18:34
문제 설명 길이가 같은 두 1차원 정수 배열 a, b가 매개변수로 주어집니다. a와 b의 내적을 return 하도록 solution 함수를 완성해주세요. 이때, a와 b의 내적은 a[0]*b[0] + a[1]*b[1] + ... + a[n-1]*b[n-1] 입니다. (n은 a, b의 길이) 제한사항 a, b의 길이는 1 이상 1,000 이하입니다. a, b의 모든 수는 -1,000 이상 1,000 이하입니다. 입출력 예 a b result [1,2,3,4] [-3,-1,0,2] 3 [-1,0,1] [1,0,-1] -2 입출력 예 설명 입출력 예 #1 a와 b의 내적은 1*(-3) + 2*(-1) + 3*0 + 4*2 = 3 입니다. 입출력 예 #2 a와 b의 내적은 (-1)*1 + 0*0 + 1*(-1)..
-
[프로그래머스] 시저 암호 (C++)알고리즘 & 자료구조/코딩테스트 2021. 3. 2. 22:22
문제 설명 어떤 문장의 각 알파벳을 일정한 거리만큼 밀어서 다른 알파벳으로 바꾸는 암호화 방식을 시저 암호라고 합니다. 예를 들어 "AB"는 1만큼 밀면 "BC"가 되고, 3만큼 밀면 "DE"가 됩니다. "z"는 1만큼 밀면 "a"가 됩니다. 문자열 s와 거리 n을 입력받아 s를 n만큼 민 암호문을 만드는 함수, solution을 완성해 보세요. 제한 조건 공백은 아무리 밀어도 공백입니다. s는 알파벳 소문자, 대문자, 공백으로만 이루어져 있습니다. s의 길이는 8000이하입니다. n은 1 이상, 25이하인 자연수입니다. 입출력 예 s n result "AB" 1 "BC" "z" 1 "a" "a B z" 4 "e F d" 주의점! 공백은 +n만큼을 밀어주는것이 아니라 공백으로 받아야한다. 나머지는 아스키..
-
[프로그래머스] 최대공약수와 최소공배수(C++)알고리즘 & 자료구조/코딩테스트 2021. 3. 1. 22:38
문제 설명 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다. 제한 사항 두 수는 1이상 1000000이하의 자연수입니다. 입출력 예 n m return 3 12 [3, 12] 2 5 [1, 10] 입출력 예 설명 입출력 예 #1 위의 설명과 같습니다. 입출력 예 #2 자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다. 최대공약수는 유클리드 호제법을 사용하고, 최소공배수는 두 자연수의 곱 = 최대공약수 x 최소..