[알고리즘_Programmers] 6주차 문제 및 풀이 (총 5 문제)

※ 6주차 문제들... 할많하않 ^^;;

 

<문제 1번>

 

<1. 나의 풀이>

 

이 문제는 결국 풀지 못하고, 구글 신의 도움을 받아 코드를 참고하였다...

 

위 풀이에서는 짝수는 어차피 소수가 될 수 없으니, n 미만의 자연수들 중에서 홀수들만 뽑아내서 코드의 효율성을 높여주었다.

 

그리고 "에라토스테네스의 체"라는 개념을 사용하여 문제를 풀면 된다...(이름부터 정이 안가네 ㅎ)

 

"에라토스테네스의 체"라는 개념을 이해하기 위해, 아래 링크를 걸어놓은 위키피디아 사이트를 참고하였다.

ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

<2. 내 풀이보다 더 효율적인 풀이>

 

이 풀이와 첫 번째 풀이의 차이점은 숫자를 set 자료형으로 뽑아낼 때, 2부터 시작할지 3부터 시작할지 정하는 것이다.

 

이 문제...코드를 봐도 100% 완벽하게 이해가 가지 않는다..

 

블로깅 해놓은 것을 보고, 보고, 또 보고 해야겠다..ㅠ

 

 

<문제 2번>

 

Cf) 멍청하게 접근했던 방법... (이렇게 풀면 안된다 하하핳!!)

 

<1. 나의 풀이>

 

이 문제에서 포인트(?)는 최대한 많은 부서의 구매를 처리하기 위해, 예산이 적은 팀부터 처리해주는 것이다.

 

즉, 가장 먼저 d.sort()를 통해 오름차순 정렬을 수행해주어야 한다!!

 

<2. 내 풀이보다 더 효율적인 풀이>

 

while 문을 쓰면 이렇게 간단하게 풀 수 있었구나 ㅎㅎㅎ 그랬었구나.... 

 

화사가 부릅니다. "멍청이"

 

 

<문제 3번>

 

<1. 나의 풀이> = <2. 내 풀이보다 더 효율적인 풀이>

 

 

이 문제는 내용 자체도 잘 이해가 되지 않았고, "왜 이렇게 체육복을 어렵게 빌려줘야 하나.."싶은 생각도 드는 문제였다.

 

결과적으로 이 문제는 혼자서 풀어내지 못했다. 구글링을 해보니 Greedy(탐욕) 알고리즘을 사용해서 푼 것을 알 수 있었다.

 

이 문제에서 주의 깊게 살펴보아야 할 부분은 "중복이 없다"와 "여벌 체육복을 가져온 학생도 체육복을 도난당할 수도 있다"라는 조건이다.

 

########################################################################################
1. "중복이 없다"라는 말은 lost와 reserve 내의 요소 값이 unique 하다는 것을 의미한다.

(즉, lost = [1, 1, 2], reserve = [3, 3, 5, 4, 2]가 될 수 없다)

2. "여벌 체육복을 가져온 학생도 체육복을 도난당할 수도 있다"는 말은 lost 값에 reserve 값이 공통적으로 존재할 수 있다는 것을 의미한다.

(예를 들면, lost = [1, 2, 3], reserve = [3, 4, 5]처럼!)

→ 따라서 lost와 reserve에 같은 값이 있다면, 그 값은 reserve에서 제거해주어야 한다!!

########################################################################################

위 과정을 잘 처리해 주었다면, 이제 reserve를 기준으로 '왼쪽'에 있는 학생부터 빌려주는 것이 좋을지, 아니면 '오른쪽'에 있는 학생부터 빌려주는 것이 좋을지를 따져봐야 한다.

 

효율성 측면에서 보면, 체육복을 양 옆 학생에게 빌려줄 때 '왼쪽' 요소부터 탐색하는 것이 더 좋다!

(자세한 설명은 링크 걸어둔 사이크 참고!)

rain-bow.tistory.com/entry/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%B2%B4%EC%9C%A1%EB%B3%B5

[Python] 프로그래머스 - 체육복

 

이렇게 문장이 길고 내용도 이해가 잘 되지 않는 문제들을 접할 때마다, 정말 머리가 터질 것 같다..^^

(알고보니 무려 12점짜리 문제였네..)

 

그래도 알고리즘 문제들을 푸는 목적이 '사고력' 증진이기 때문에, 포기하면 안된다...(그 놈의 사고력..ㅂㄷㅂㄷ)

 

 

<문제 4번>

 

<1. 나의 풀이> = <2. 내 풀이보다 더 효율적인 풀이>

 

이 문제는 "string 모듈을 사용해서 어떻게 하면 될 것 같다..."고까지는 생각을 했는데, 그 후의 작업들을 수행해주지 못했다 ㅜㅜ...

 

결국 구글링을 통해 내가 시도하려 했던 string 모듈 사용법을 참고하였다.

 

문자의 아스키 코드 값을 반환해주는 ord() 함수를 사용한 풀이도 있었으나, 위의 string 모듈을 활용한 방법이 더 효율적인 것 같아서 string 모듈을 사용한 풀이만 첨부하였다.

 

 

<문제 5번>

 

<1. 나의 풀이> = <2. 내 풀이보다 더 효율적인 풀이>

 

이 문제는 2018년도 카카오 블라인드 채용 문제 중 하나였다고 한다.

 

카카오 기출 문제치고는 크게 어렵지 않은(?) 문제였다. 근데 난 멍청해서 그런지 푸는데 좀 오래걸렸다.

 

이 문제의 핵심은 바로 "OR 비트 연산자"이다. 비트 연산자들만 잘 사용해도 문제 풀이가 간단해진다. 

 

이러한 유형의 문제들은 잘 기억해두자!!

 

 

 

★ 여기까지 해서 알고리즘 스터디 1단계 문제(총 30문제)들은 다 풀어보았다. 다음 단계인 2단계가 날 기다리고 있네..

 

갈 길이 멀다~ 파이팅!! :)