https://www.codetree.ai/missions/5/problems/output-value-based-on-odd-even-numbers?&utm_source=clipboard&utm_medium=text

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

홀수 짝수에 따른 출력값


정수 N이 주어지고, N이 홀수인 경우에는 1부터 N까지의 홀수를, N이 짝수인 경우에는 2부터 N까지의 짝수의 합을 출력하는 프로그램을 재귀 함수를 이용하여 작성해보세요.

 

입력 형식

첫 번째 줄에 정수 N이 주어집니다.

  • 1 ≤ N ≤ 100

출력 형식

첫 번째 줄에는 출력하는 모든 수의 합을 출력합니다.

 

입출력 예제

예제1

입력:

5

 

출력:

 

9

 

 

 

 

내가 짠 코드


n = int(input())

def f(n):
    if n==1:
        return 1
    if n==2:
        return 2
    
    return n+f(n-2)

print(f(n))

재귀함수 문제이다. 우선 n 을 입력받은 후 홀수이면 지금까지의 홀수의 합을, 짝수이면 지금 까지의 짝수의 합을 출력해야한다.

 

우선 베이스케이스를 정의하자.

이 문제에서는 홀수가 들어오면  n==1 일때가 베이스케이스가 되고 짝수가 들어오면 n==2 일 때가 베이스케이스가 되므로 각각 1, 2 를 리턴할 수 있도록 한다.

 

그 후 재귀적으로 처리가 가능한데, 짝수일 때 짝수만 더하려면 n-2 번째를 호출하여 자기 전전 녀석을 호출해야한다.

홀수일 때도 마찬가지다. 자기 자신 + 자기 전전 녀석 호출이 필요하다. 따라서 리턴값은 n+f(n-2) 가된다.

728x90

 

https://www.codetree.ai/missions/5/problems/factorial?&utm_source=clipboard&utm_medium=text

 

Factorial


팩토리얼이란 차례로 곱한다는 뜻으로, 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 n!로 나타낸다. 재귀함수를 이용하여 n! 값을 구하는 프로그램을 작성해보세요.

0! = 1

1! = 1

2! = 2

3! = 6

n! = n * (n-1)!

...
와 같이 정의된다.

 

입력 형식

첫 번째 줄에 정수 N이 주어집니다.

  • 1 ≤ N ≤ 10

출력 형식

첫 번째 줄에 N! 값을 계산하여 출력합니다.

 

입출력 예제

예제1

입력:

5

 

출력:

120

 

 

 

 

내가 짠 코드


n = int(input())

def f(n):
    if n==1 :
        return 1
    
    return f(n-1)*n

print(f(n))

이것도 재귀함수의 기본적인 문제 중 하나이다. 

팩토리얼이란, 차례로 곱한다는 뜻으로, 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 n!로 나타낸다. 

 

재귀함수 문제이므로 가장 먼저할 것은 베이스케이스를 생각하는 것이다. 이 문제에서는 n==1 일때는 n-1 이 존재하지 않으므로 n==1 일때는 1을 리턴하도록 한다. 그 외에는 재귀적으로 처리가 가능하다. 자기 자신 곱하기 밑에 애들이므로 n*f(n-1)이다. 

728x90

피보나치 수열이란 이전 두 항의 합이 그 다음 항이 되는 수열을 의미합니다.

예를 들어 첫 번째 원소를 1, 두 번째 원소도 1이라 하면 그 다음 항은 2, 3, 5, 8 .. 이 됩니다.

N번째 피보나치 수를 구하는 프로그램을 작성해보세요. 단, 재귀함수를 이용하여 문제를 해결해주세요

 

입력 형식

첫째 줄에는 N이 주어집니다.

  • 1 ≤ N ≤ 20

출력 형식

N번째 피보나치 수를 출력합니다.

 

입출력 예제

예제1

입력:

3

출력:

2

 

 

 

 내가 짠 코드

 


n = int(input())

def f(n):
    if n ==1:
        return 1
    if n==2:
        return 1
    
    return f(n-1) + f(n-2)

print(f(n))

기본적인 재귀함수 문제이다. 

 

피보나치 수란, 

피보나치 수열이란 이전 두 항의 합이 그 다음 항이 되는 수열을 의미한다.

1, 1, 2, 3, 5, 8, .. 과 같은 수열을 말한다.

 

 

n 을 입력받은후 피보나치 수를 출력해야한다.

이때 베이스 케이스에 주의해야하는데 n==1 이거나 n==2 일 때는 n-1 혹은 n-2 가 0이나 음수가 나와 정의할 수 없기 때문에 따로 정의해야한다. 1,2 일때는 1을 리턴하도록 하고 그게 아닌경우는 n-1 과 n-2 번째 수를 합하도록한다. 

 

728x90

https://www.codetree.ai/missions/5/problems/square-of-each-digit/description

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

 

각 자리 숫자의 제곱


8자리 이하의 정수 N이 주어지면 재귀함수를 이용하여 각 자리 숫자의 제곱의 합을 출력하는 프로그램을 작성해보세요.

입력 형식

첫 번째 줄에 정수 N이 주어집니다.

  • 1 ≤ N ≤ 99,999,999

출력 형식

첫 번째 줄에 정수 N의 각 자리 숫자의 제곱의 합을 출력합니다.

 

 

 

 

내가 짠 코드

 

n = int(input())

def f(n):
    if(n<10):
        return n*n
    
    return f(n//10) + (n%10)*(n%10)


print(f(n))

우선 각 자리의 제곱을 구해야한다. 베이스 케이스에 대하여 n이 10 보다 작다면 더 이상 재귀함수를 진행할 필요가 없어진다. 이때는 n의 제곱을 리턴해준다. 그리고 다른 케이스에 대해선 다음 자리수를 호출해야하므로 f(n//10) 을 통해 10으로 나눈 몫을 인자로 넣어서 호출한다. 그리고 호출한 수에 해당 n 을 10으로 나눈 나머지 즉, 가장 마지막 자리에 있는 수의 제곱을 더한다. 이렇게 베이스케이스가 될 때까지 반복한다면 계속해서 마지막 자리수의 제곱을 더하므로 모든 자릿수의 제곱의 합을 구할 수 있다.

728x90

 

 

https://www.codetree.ai/missions/5/problems/sum-from-1-to-a-certain-number-2?&utm_source=clipboard&utm_medium=text

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

 

1부터 특정 수까지의 합 2


 

정수 N이 주어지면 재귀함수를 이용하여 1부터 N까지의 합을 구하여 출력하는 프로그램을 작성해보세요.

 

입력 형식

첫 번째 줄에 정수 N이 주어집니다.

  • 1 ≤ N ≤ 100

출력 형식

첫 번째 줄에 1부터 N까지의 합을 출력합니다.

 

 

 

 

내가 짠 코드


n = int(input())

ans = 0
def sum(n):
    if(n==0):
        return 0
    
    return sum(n-1) + n

print(sum(n))

 

굉장히 간단하다 우선 n 을 입력받은 후 sum 재귀함수를 정의한다. 베이스 케이스인 0에 대해 0이 들어오면 0을 리턴한다. 0이 아닌 수 라면 sum (n-1) 을  호출하고 그 수에 n을 더한 수를 리턴한다 예를들어 1일 경우는 sum(0) + 1 이고 2일 경우는 sum(1) + 2 이고

3일 경우는 sum(2) + 3 이된다.

따라서 sum(n) 은 0 + 1 + 2 + 3 + .. + n 이 될것이다.

 

 

728x90

 

 

 

이번 실력 진단에는 최고 점수를 기록했다. !

610 점으로 아직도 많이 부족하지만 지난번보다 60점 가량 올랐다. 

 

이번 피드백을 보면 백트래킹을 공부하라해서 다음주는 백트래킹에 대한 공부를 할 예정이다.

 

 

이번 주에 푼 문제들이다. 완전 탐색, 재귀 함수 에 대한 문제를 몇가지 풀었다. 이 중 몇몇은 블로그에 따로 정리하였다. 

 

 

 

 

푼 문제들 정리


 

1. 한 가지로 열리는 자물쇠 / 완전탐색

https://dodenkr.tistory.com/81

 

[코드트리] 한 가지로 열리는 자물쇠 /완전탐색

https://www.codetree.ai/missions/5/problems/one-way-lock?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코

dodenkr.tistory.com

 

2. 아름다운 수열 2/ 완전 탐색

 

https://dodenkr.tistory.com/79

 

[코드트리] 아름다운 수열 2 / 완전 탐색

https://www.codetree.ai/missions/5/problems/beautiful-sequence-2?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의

dodenkr.tistory.com

 

3. 특정 구간의 원소 평균값 / 완전 탐색

 

https://dodenkr.tistory.com/78

 

[코드트리] 특정 구간의 원소 평균값 / 완전 탐색

https://www.codetree.ai/missions/5/problems/elemental-mean-value-for-a-particular-interval?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩

dodenkr.tistory.com

 

4. 구간 중 최대 합 / 완전탐색

 

https://dodenkr.tistory.com/76

 

[코드트리 챌린지] 구간 중 최대 합/ 완전탐색

https://www.codetree.ai/missions/5/problems/max-sum-of-subarray?&utm_source=clipboard&utm_medium=text 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직

dodenkr.tistory.com

 

728x90

 

 

https://www.codetree.ai/missions/5/problems/one-way-lock?&utm_source=clipboard&utm_medium=text 

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

 

한 가지로 열리는 자물쇠


1부터 N까지 숫자를 중복해서 뽑아 총 3자리를 만들어야 하는 자물쇠가 하나 주어집니다. 이 자물쇠는 특이해서 한 자리라도 주어지는 조합과 거리가 2 이내라면 열리게 됩니다.

예를 들어, N = 6이고 주어진 조합이 (1, 2, 3) 이라면, 이 자물쇠는 (5, 4, 6)일 때 두 번째 자리의 숫자 차이가 2 이내가 되므로 열리게 됩니다. 자물쇠 번호가 (1, 5, 6)인 경우에는 첫 번째 자리의 숫자 차이가 2 이내가 되므로 열리게 됩니다. 만약 자물쇠 번호가 (6, 6, 6) 이라면 숫자 차이가 2 이내인 위치가 없으므로 열리지 않습니다.

N과 조합이 주어졌을때 자물쇠가 열리게 되는 서로 다른 조합의 수를 구하는 프로그램을 작성해보세요. 단, (1, 2, 3)과 (3, 2, 1)은 다른 가짓수로 셉니다.

 

입력 형식

첫 번째 줄에는 N이 주어집니다.

두 번째 줄에는 조합에 해당하는 정보 a, b, c가 공백을 사이에 두고 주어집니다.

  • 1 ≤ N ≤ 100
  • 1 ≤ a, b, c ≤ N
  •  

출력 형식

첫 번째 줄에 가능한 서로 다른 조합의 수를 출력합니다.

 

입출력 예제

예제1

입력:

6
1 2 3

 

출력:

210

 

 

 

 

내가 짠 코드


n = int(input())

a, b, c = list(map(int, input().split()))
cnt = 0
for i in range(1, n+1):
    for j in range(1, n+1):
        for k in range(1, n+1):
            if abs(i-a)<=2 or abs(j-b)<=2 or abs(k-c)<=2:
                cnt += 1

print(cnt)

 

한 자리씩 완전 탐색하면 된다. 일단 수는 1부터 n까지 이므로 모든 세 자리 수를 (1, n+1) 의 레인지로 잡으면 된다.

 

그리고 조건 설정에서 각자리수가 입력한 a,b,c 와 각각 차이가 2이하면 되므로

abs(i-a)<=2 이거나 abs(j-b)<=2 이거나 abs(k-c)<=2 이면

카운팅한다.

 

abs() 는 절댓값을 만들어주는 함수

 

728x90

 

https://www.codetree.ai/missions/5/problems/beautiful-sequence-2?&utm_source=clipboard&utm_medium=text 

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.

www.codetree.ai

아름다운 수열 2

N개의 숫자로 이루어진 수열 A와 M개의 숫자로 이루어진 수열 B가 주어집니다. 수열 B의 각 원소들의 순서를 바꿔 나오는 수열을 아름다운 수열이라고 합니다. 수열 A에서 길이가 M인 연속 부분 수열들 중 아름다운 수열의 수를 세는 프로그램을 작성해보세요.

예를 들어 수열 B를 “4 6 7“이라 했을 때 "4 6 7", "4 7 6", "6 4 7", "6 7 4", "7 4 6", "7 6 4"는 모두 아름다운 수열이 됩니다.

 

입력 형식

첫 번째 줄에는 N, M이 공백을 사이에 두고 주어집니다.

두 번째 줄에는 수열 A에 해당하는 N개의 숫자가 공백을 사이에 두고 주어집니다.

세 번째 줄에는 수열 B에 해당하는 M개의 숫자가 공백을 사이에 두고 주어집니다.

  • 1 ≤ N ≤ 100
  • 1 ≤ M ≤ 100
  • 1 ≤ 입력으로 주어지는 숫자 ≤ 100

출력 형식

첫 번째 줄에 수열 A의 연속 부분 수열들 중 아름다운 수열의 수를 출력합니다.

 

입출력 예제

예제1

입력:

8 3
2 4 6 7 5 7 6 4
4 6 7

 

출력:

2

 

예제 설명

첫 번째 예제에서 수열 A의 연속 부분 수열 중 아름다운 수열은 [4, 6, 7], [7, 6, 4] 총 2개가 있습니다

 

 

 


 

이번 문제는 못풀어서 해설을 봤다.

해설에 공부할 만한 코드가 있어서 블로그로 공부하려한다.

 

 

코드


 

우선 시작점을 잡아야한다. 구간의 길이는 m 으로 정해져 있다. 시작점은 0부터 마지막은 인덱스를 넘으면 안되므로 마지막원소인 n에서 m을 빼고+1

어떤수 ~ 마지막원소 [n-1] 까지의 개수가 m개가 되어야하므로

(n-1) - (어떤수의 인덱스) + 1 = m

(어떤수 인덱스) = n-1+1-m

따라서 끝 범위는 포함하지 않으므로 여기에 다시 +1을 하면

 

for i in range(n-m+1)이다.

 

주목할 것은 sorted 함수인데

 

만약 a 구간원소를 정렬후 b도 졍렬 후 비교했을 때 같다면 같은 원소로 구성되어있는것이다.

 

sorted 함수를 활용하자!

n, m = tuple(map(int, input().split()))

a = list(map(int, input().split()))
b = list(map(int, input().split()))
cnt = 0
#시작점 잡기
for i in range(n-m+1):
    if sorted(a[i:i+m]) == sorted(b):
        cnt += 1
        
print(cnt)
728x90

+ Recent posts