분류 전체보기
-
[프로그래머스] [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 최소..
-
[프로그래머스] 2016년 (C++)알고리즘 & 자료구조/코딩테스트 2021. 2. 28. 21:32
문제 설명 2016년 1월 1일은 금요일입니다. 2016년 a월 b일은 무슨 요일일까요? 두 수 a ,b를 입력받아 2016년 a월 b일이 무슨 요일인지 리턴하는 함수, solution을 완성하세요. 요일의 이름은 일요일부터 토요일까지 각각 SUN,MON,TUE,WED,THU,FRI,SAT 입니다. 예를 들어 a=5, b=24라면 5월 24일은 화요일이므로 문자열 "TUE"를 반환하세요. 제한 조건 2016년은 윤년입니다. 2016년 a월 b일은 실제로 있는 날입니다. (13월 26일이나 2월 45일같은 날짜는 주어지지 않습니다) 입출력 예 a b result 5 24 "TUE" 1월1일이 금요일이란 단서를 이용해서 날짜들을 합쳐 일주일로 나눠 요일을 계산해주는 방법을 사용하도록 한다. stinrg da..
-
[프로그래머스] 콜라츠 추측(C++)알고리즘 & 자료구조/코딩테스트 2021. 2. 27. 20:52
문제 설명 1937년 Collatz란 사람에 의해 제기된 이 추측은, 주어진 수가 1이 될때까지 다음 작업을 반복하면, 모든 수를 1로 만들 수 있다는 추측입니다. 작업은 다음과 같습니다. 1-1. 입력된 수가 짝수라면 2로 나눕니다. 1-2. 입력된 수가 홀수라면 3을 곱하고 1을 더합니다. 2. 결과로 나온 수에 같은 작업을 1이 될 때까지 반복합니다. 예를 들어, 입력된 수가 6이라면 6→3→10→5→16→8→4→2→1 이 되어 총 8번 만에 1이 됩니다. 위 작업을 몇 번이나 반복해야하는지 반환하는 함수, solution을 완성해 주세요. 단, 작업을 500번을 반복해도 1이 되지 않는다면 –1을 반환해 주세요. 제한 사항 입력된 수, num은 1 이상 8000000 미만인 정수입니다. 입출력 예..