구현 구현은 특별한 알고리즘이 아닌 모든 알고리즘을 통틀어 구현이라고 한다. 보통 알고리즘 문제를 풀 때 아이디어는 알겠지만 구현을 하지 못해 풀지 못하는 경우가 상당하다. 이는 프로그래밍 언어 문법에 익숙하지 않은 탓이기 때문에 이 또한 그리디 처럼 자주, 많이 풀어보는 방법밖에 없다. 그럼에도 불구하고 문제들을 더 효율적으로 풀고 접근해야하는 방법은 정해져 있다. 지금부터 그것들을 알아볼 예정이다. 1. 메모리 -C나 C++에서는 int나 long long등을 통해 변수에 자료형을 붙여서 메모리를 할당해준다. 문제에서 요구하는 메모리를 보고 거기에 맞춰 변수를 지정하는 것이 중요하다. 2. 파이썬에서의 리스트 크기 -파이썬은 다른 언어와 다르게 변수가 없다. 하지만 메모리 할당은 똑같이 이루어진다. ..

1이 될 때까지- 이것이 코딩테스트다 문제 : 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다. 1. N에서 1을 뺀다. 2. N을 K로 나눈다. 예를 들어 N이 17, K가 4라고 가정하자. 이때 1번의 과정을 한 번 수행하면 N은 16이 된다. 이후에 2번의 과정을 두 번 수행하면 N은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N을 1로 만드는 최소 횟수이다. N과 K가 주어질 때 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오. 입력 조건: 첫째 줄에 N(2

큰 수의 법칙- 이것이 코딩테스트다 문제 : '큰 수의 법칙'은 일반적으로 통계 분야에서 다루어지는 내용이지만 동빈이는 본인만의 방식으로 다르게 사용하고 있다. 동빈이의 큰 수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징이다. 예를 들어 순서대로 2, 4, 5, 4, 6으로 이루어진 배열이 있을 때 M이 8이고, K가 3이라고 가정하자. 이 경우 특정한 인덱스의 수가 연속해서 세 번까지만 더해질 수 있으므로 큰 수의 법칙에 따른 결과는 6+6+6+5+6+6+6+5인 46이 된다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서..

그리디 알고리즘 그리디의 의미는 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 이다. 필자는 이러한 의미에 대해 애매하게만 들렸고 전혀 감이 오지 않았다. 때문에 문제를 풀면서 이 알고리즘의 감을 조금씩 잡았다. 그래서 얻은 결론은 이렇다. "최소한의 아이디어(대충 생각한 것)를 떠올리고 이것이 정당한지 검토한다면 답을 도출한다." 예를들어 B라는 문제에 대해 A라는 아이디어가 떠올랐다고 가정하자. 우리는 이 A라는 아이디어가 이 문제에 쓰일 수 있는지, 혹시 A를 쓰다가 반례가 생기는 건 아닌지를 검토해야한다. 이러한 검토가 합리적이라면 이 문제는 결국 풀린다. 이 유형은 창의력을 기르는 유형이다. 이 때문에 시간안에 빠르게 알고리즘을 생각하는 능력을 기르는 것이 중요하다. 책에 있는 문제를 한번..

떡볶이 떡 만들기(Python) 문제 : 오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다. 동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춰준다. 절단기에 높이(H)를 지정하면 줄지어진 떡을 한 번에 절단한다. 높이가 H보다 긴 떡은 H 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다. 예를 들어 높이가 19, 14, 10, 17cm인 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 차례대로 4, 0, 0, 2cm이다. 손님은 6cm만큼의 길이를 가져간다. 손님이 왔을 때 요청한 ..

부품 찾기(Python) - 이것이 코딩테스트다 문제 : 동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자. 예를 들어 가게의 부품이 총 5개일 때 부품 번호가 다음과 같다고 하자. N = 5 [8, 3, 7, 9, 2] 손님은 총 3개의 부품이 있는지 확인 요청했는데 부품번호는 다음과 같다. M = 3 [5, 7, 9] 이때 손님이 요청한 부품 번호의 순서대로 부품을 확인해 부품이 있으면 yes를, 없으면 no를 출력한다..