친구들과 매일매일 스터디를 진행하고 있다. 온라인 개학중이라 하루종일 집에 있으니 나태해지는 느낌도 많이 들었고 마음을 잡기가 많이 힘들었다. (특히 블로그 글쓰는게 가장 힘들었다.😅) 그러다 학교 친구들과 함께 매주 발표주제를 정해서 발표, 블로그 글 작성의 루틴을 반복하고 있다. 스터디를 통해서 내 기초를 돌아볼 수 있어서 좋았다. 첫번째 주제는 자료구조, 알고리즘 이었는데 스터디 진행 당시 코딩테스트를 준비하고 있어서 접근법이라는 꽤나 어려운 주제를 선택했다.
발표 자료는 https://www.slideshare.net/ssuser4913c5/study1stsineunjj 위 링크에서 볼 수 있다. 자료의 내용은 문제 -> 문제 접근법 -> 구현코드 형식으로 되어있다. 블로그 에서는 굳이 python으로 작성된 예시 코드를 삽입하지 않을 예정이니 궁금하신 분들은 발표 자료 내의 코드를 참고하시면 된다. 그리고 글에 나온 접근법이 최선의 답도 최적의 답도 아닌 작성자의 접근 과정, 순서로 그냥 "아 이렇게 접근 하셨구나" 정도로 넘어가주시면 될 것 같다.
알고리즘 접근법이라고는 하지만 코딩 테스트 내용에 SQL도 있어서 어떻게 SQL 문제를 접근하고 풀었는지도 작성해 볼 예정이다.
블로그에서 작성되는 모든 문제는 출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges 의 문제를 바탕으로 접근하고 풀었다. 블로그에서 작성한 문제 외에도 코딩 테스트, 알고리즘 연습하기에 좋은 문제가 많으니 참고하시면 된다.
해쉬문제인데 해쉬써서 푼 느낌인가?
위의 문제는 프로그래머스 해쉬로 구분 된 문제고, 해쉬로 접근하려고 했던 문제다. 일단 이 문제를 전체적으로 읽어보면 사실 해쉬보다는 숫자 계산이 핵심인 느낌이 든다. 확률과 통계라는 과목을 배워보셨다면 문제 자체가 비슷하다고 느낄 수 있다. 확률과 통계 과목을 배웠기 때문에 문제를 풀 때도 이거 종류별로의 옷 갯수만 안다면 쉽게 풀 수 있을 것 같았다.
작성자는 알고리즘 문제를 읽었을 때 숫자 계산으로 답을 도출 할 수 있는 문제, 경우를 나눠 계산해야 하는 문제 크게 두가지 중 무엇인지 부터 확인하는 작업을 하는데 간단하게 숫자 계산으로 해결 할 수 있는 문제라면 대부분 공식이 존재한다. 위의 문제도 경우의 수에 따른 숫자 계산 문제이므로 각 종류별 옷 갯수 + 1 한 값을 모두 곱한 후 -0을 하는 공식으로 문제를 해결 할 수 있다.
숫자계산 문제인데 이건 공식 없는데요?
위와 같은 문제는 문제를 나누자면 숫자 계산으로 답을 도출 하는 문제로 볼 수 있다. 하지만 1번째 문제에서 이야기 했던 것과는 다르게 공식이 없는 문제이기도 하다. 이러한 문제는 예시 혹은 어떤식으로 숫자를 계산해야 하는지 알려주는 편이다. 그렇다면 이러한 문제는 계산을 문제에서 원하는 대로 순서대로 작업하면 쉽게 답을 구할 수 있다.
읽어보면 1번째가 모든 금액을 줄 수 있다면 준다는 내용이다. 그렇다면 코드에서도 요청 된 예산들을 다 더한 값을 국가예산보다 낮은지 확인한다. 만약 첫번째 조건을 만족한다면 요청 예산 중 제일 높은 금액이 답이 된다.
2번째 조건은 첫번째 조건이 만족하지 않을 때의 이야기 인데 두번 째 조건이 핵심이 된다. 첫번째 조건에서는 요청한 예산 중에 높은 갚이 답이 되는데 두번째 조건에서는 사용자가 직접 특정한 정수 상한액을 계산해서 그 보다 높은 값들 중 최대로 줄 수 있는 값이 답이 된다.
이러한 문제에서 최대 값을 주려고 하는 것은 평균 값으로 예산들이 상대적으로 작은지 큰지를 비교하는 경우가 정답이 되는 경우가 많다. 따라서 2번째 조건에서 말하는 특정한 정수 상한액은 예산안들중의 평균 값으로 가정하고 계산 할 수 있다. 그 평균 값 보다 작은 예산은 할당 해주고 평균 값 보다 큰 값들은 전부 다 할당 해 줄수 없으므로 남은 예산안을 가지고 줄 수 있는 가장 큰 예산을 할당해줘야 한다. 가장 큰 금액은 남은 예산안을 남은 지역구 수로 나누면 현재의 상황에서 줄 수 있는 가장 큰 예산안이 나온다.
소수가 몇개인지 확인하는 공식이 있나요?
위의 문제는 쉽게 숫자 계산으로 답을 구할 수 있는 문제로 보일 수 있다. 하지만 우리는 가지고 있는 숫자를 더해서 몇개의 소수를 만들 수 있는지 계산 하는 공식을 알 수는 없다. 그 이유는 소수끼리 더하면 소수가 나온다는 보장 또한 없고 어떻게 계산해야 하는지도 모르기 때문이다.
그렇다면 어떻게 문제를 해결 할 수 있을까? 이럴 때는 꽤 무식한 방법이 문제를 해결하는데 도움이 될 수 도 있다. 제한 사항을 잘 읽어보면 nums에 들어있는 숫자 갯수가 50개인 생각보다 적은 숫자이다. (사람이 직접 계산한다면 많겠지만 우리는 컴퓨터가 대신 사칙연산을 해주니 적은 숫자로 볼 수 있다.) 따라서 숫자가 많지 않으므로 모든 숫자들을 3개씩 다 더해보고 그 더한 숫자가 소수인지 확인해보면 어떨까? 꽤 무식한 방법이긴 하지만 공식으로도 해결 할 수 없다면 이런식으로 답을 해결 할 수 있다.
SQL JOIN문제는 누워서 떡먹기
SQL문제가 코딩 테스트에 나온다면 대부분 JOIN, GROUP BY 문제 중 하나일 것이다. JOIN을 써야하는 문제라면 테이블이 여러개일 경우이다. 테이블이 여러개라 JOIN을 해야하는 경우라면 우리가 신경써야 할 것은 딱 하나 어떤 JOIN으로 문제를 해결 할 것인가이다. JOIN도 매우 여러가지가 있다. 어떤 JOIN인지 구분을 하는 가장 쉬운 방법이자 애용하는 방법은 수학시간에 배운 집합 그림을 그려보는 것이다. 아래 그림 처럼 말이다.
이 문제는 읽어보면 A 테이블에도 B 테이블에도 원하는 값이 있어야 함으로 INNER JOIN으로 해결 할 수 있다. 그 이후에는 간단하게 WHERE 구문만 작성해주면 된다.
GROUP BY는 어떨 때 쓰나?
아까 SQL문제는 대부분 JOIN과 GROUP BY 문제 중 하나라고 했다. 근데 JOIN은 테이블 여러개로 JOIN을 쓰는지 알겠는데 GROUP BY는 언제 써야하는지 감이 잘 잡히지 않을 수 있다. GROUP BY는 대부분 컬럼에 종류가 여러개 있을 때 사용한다. 위의 문제 처럼 동물 테이블의 type이라는 컬럼이 개, 고양이와 같은 종류가 여러개 있을 때 GROUP BY를 사용한다고 보면 된다. 예시로는 학생 테이블의 정보가 있는데 각반의 인원수를 세는 SQL문이라던지 각 성별의 나이 평균을 구하는 문제등이 GROUP BY가 쓰이는 문제라고 볼 수있다. 따라서 위의 문제는 GROUP BY 구문을 간단하게 이용하여 해결 할 수 있다.
간단하게 발표에서 풀어보았던 문제들을 블로그에서 어떻게 접근하는지 더 자세하게 작성해 보았다. 글에서 작성한 접근법, 해설이 정답이라고는 할 수 없다. 그냥 알고리즘을 다른 사람은 어떻게 풀었나 하는 가벼운 마음으로 읽으시면 될 것 같다.
