재귀함수 정의 컴퓨터가 수행하는 작업들은 대개 작은 조각들로 나누어 볼 수 있다. 그런데 우리가 들여다보는 범위가 작아지면 작아질수록 각 조각들의 형태가 유사해지는 작업들을 많이 볼 수 있다. 완전히 같은 코드를 반복해 실행하는 for 같은 반복문이 좋은 예다. 이런 작업을 구현할 때 유용하게 사용되는 개념이 바로 재귀 함수(recursive function)이다. 재귀함수란 자신이 수행할 작업을 유사한 형태의 여러 조각으로 쪼갠 뒤 그 중 한 조각을 수행하고, 나머지를 자기 자신을 호출해 실행하는 함수를 가리킨다. 조합과 순열 문제 간단한 반복문을 재귀함수로 변환하기 1. 조합 조합은 예를 들어 5개의 숫자를 4자리수 에 대한 숫자를 만들려고 할때 모든 경우를 구하는 것이다. 아래 문제를 보고 for문..
기능개발 문제 programmers.co.kr/learn/courses/30/lessons/42586 [풀이방법] 앞에 작업보다 뒷작업이 먼저 끝나면 앞에 작업이 끝날때 까지 기다려야 하므로 각 progresses 마다 배포일을 구한다음 progress 순서대로 배포일을 스택에 담았을때 다음 배포일이 스택에 있는 배포일보다 작다면 스택에 쌓고 다음 배포일이 스택에 있는 배포일보다 크다면 스택에 있는걸 모드 pop 한다음 배포일을 스택에 넣는다. progresses = [93, 30, 55] speeds = [1, 30, 5] 배포일은 [7, 4, 9] (배포일식: (100 - progress) / speed) [풀이 코드] import math def solution(progresses, speeds):..
시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity) 설계를 하고 코딩을 한다음 기능이 잘 동작하는 것은 물론이지만 좋은 성능까지 보장받기를 원한다. 때문에 우리는 자료구조와 알고리즘을 분석하고 평가할 수 있어야 한다. 평가는 2가지로 할 수 있다. 하나는 속도에 관한것(시간 복잡도) 다른 하나는 메모리 사용량(공간 복잡도)이다. 옛날에는 하드웨어가 안좋았기 때문에 메모리 사용량을 많이 고려했었지만 지금은 하드웨어가 매우 좋기 때문에 메모리 사용 보다는 실행속도에 초점을 둔다. 실행속도를 평가하기 위해 조건마다 다르게 실행해가면서 수행시간을 평가할 수는 없다. 그래서 수행시간을 재기 위해 연산의 횟수를 통해서 알고리즘의 빠르기를 판단해야 한다. 그러기 위해서는 데이터의..
주식가격 문제 programmers.co.kr/learn/courses/30/lessons/42584 이 문제는 prices 리스트 각각의 값들이 몇초 동안 가격이 안떨어지고 있었는지 return 해주면 되는 문제 이다. return 은 prices의 리스트의 개수만큼 이므로 for문으로 풀 경우 0으로 초기화 해주면 쉽게 풀수 있다. [풀이] 1. Brute force def solution(prices): answer =[0] * len(prices) for i in range(len(prices)): for j in range(i+1, len(prices)): if prices[i]
LeetCode 문제 leetcode.com/problems/two-sum/ 문제는 Input nums 정수형 리스트와 이 리스트로 만들어야할 값 target이 있고 리스트에서 target을 만들 수 있는 인덱스 2개를 구하면 된다. 첫번째로 풀 수 있는 방법은 첫번째 인덱스와 뒤에있는 나머지 인덱스와 더해보고 두번째 인덱스와 그 뒤에 있는 인덱스와 더해보는 방법이 있다. 대부분 처음에 이 방법을 떠올릴 것이다. [풀이] 1. Brute Force class Solution(object): def twoSum(self, nums, target): for i in range(len(nums)): #i 다음 인덱스부터 loop for j in range(i+1, len(nums)): # 첫번째 인덱스부터 뒤..
코딩테스트 처음 준비하는 사람을 위한 풀이방법 프로그래머스 해시(Hash)문제 https://programmers.co.kr/learn/courses/30/lessons/42576 먼저 문제를 보고 어떻게 푸는게 좋을지 사람에게 설명할수 있어야 코딩이 가능하다. 바로 풀이방법을 생각 하는게 어렵겠지만 쫌만 생각하면 한사람 씩 비교하는 방법 즉 2중포문을 사용하여 해결하는 방법은 생각할것이다. 풀이 방법이 생각났다면 바로 코딩해보자 2중포문으로 풀었더니 효율성에서 전부 실패 하였다. 이는 제한사항에 걸리기 때문이다. 2중포문은 시간복잡도 N^2 이다. 제한사항에 참여한 선수는 1명 이상 10만명 이하인데 10만을 N에 대입하면 100억이 된다. 100억이면 무조건 시간 초과로 테스트에 통과하지 못한다고 보..
재귀함수의 기본적인 이해재귀함수는 말 드대로 함수는 함수내에서 자기 자신을 다시 호출하는 함수를 의미한다. #include void Recursive(void) { printf("Recursive call! \n"); Recursive();} int main() { Recursive();}cs Recursive함수에서 Recursive()으로 자기 자신을 다시 호출한다. 실행결과는 "Recursive call" 이 계속 출력되는 무한 츠쿠요미에 걸리게 된다. 여기서 아 그렇구나 라고 이해하면 안된다. 원래는 Recursive 함수가 호출 될때 마다 계속해서 Recursive 함수의 복사본이 만들어져서 복사본이 실행되는 구조이다. 여기서 이해가 안될텐데 그림을 보자 그림은 복잡해 보이지만 실제로는 훨씬 이..
백준은 무료로 코딩테스트를 공부할수 있는 대표 사이트이다. 백준 사이트에서 어떻게 코딩테스트를 하는지 알아보자 백준 사이트 : https://www.acmicpc.net/ 사이트접속 후 먼저회원가입을 한다. 가입하기를 누르고 이메일 인증을 하면 회원가입이 된다. 회원가입을 완료한 후 카테고리 메뉴에서 전체 문제를 눌러 보면 1000번 부터 문제 번호가 보이고 가장 쉬운 1000번을 테스트로 풀어보자 문제가 보이고 예제 입력과 예제 출력이 보인다. 1 2를 입력하면 3이 나오게 하면 된다는 것 같다. 소스코드에 코딩을 작성하고 소스코드를 다 적고 제출을 누르면 자동으로 채점이된다 제출 할때 몇가지 주의점은 먼저 언어설정을 해줘야 하고 자바인경우 무조건 main클래스에 작성해야 한다 아니면 컴파일 에러난다...