[Coding test] (바킹독 실전 알고리즘) 기초 코드 작성 요령 II (feat. Python)

INTRO

KEY POINT

코딩테스트와 개발은 다르다

출력 맨 마지막 공백 혹은 줄바꿈이 추가로 있어도 상관이 없다.

디버거는 굳이 사용하지 않아도 된다.

 

강의에대한 내용정리는 바킹독님께서 친절하게 텍스트까지 남겨주시며 최고의 강의를 해주고 있으시니 이 블로그에서는 문제 풀이를 파이썬으로 풀어보기만 하도록 하겠습니다. 개념이나 내용이 궁금하다면 아래 링크에서 바킹독님의 강의를 듣는 것을 추천합니다.

 

기초 2주차 강의에서 진행한 실습 및 연습문제 파이썬 코드 풀이 입니다.

https://blog.encrypted.gg/923

[실전 알고리즘] 0x02강 - 기초 코드 작성 요령 II

 

 

 

문제풀이

https://github.com/encrypted-def/basic-algo-lecture/blob/master/workbook/0x02.md

GitHub - encrypted-def/basic-algo-lecture: 바킹독의 실전 알고리즘 강의 자료

다음은 바킹독님이 강의를 마치고 각 강의에 맞게 올려주신 문제집입니다.

강의자인 바킹독님꼐서는 c++언어로 문제를 풀이 하셨기 때문에 저는 파이썬으로 알고리즘을 풀어보려 합니다.

 

2강 문제집은 기초문제가 많은 관계로 제가 풀면서 헷갈렸거나 배운 부분이 있던 문제만 업로드 하도록 하겠습니다.

 

 

문제 1. 백준 10871번

https://www.acmicpc.net/submit/10871

로그인

BaaaaaaaarkingDog's Solution

My solution

 

문제에 조건에 맞게 N, X로 map함수를 이용해서 10, 5 숫자를 각각 int로 입력받고 

A수열을 만들어 둘째 줄에 입력되는 숫자들을 list에 int로 집어넣습니다.

그렇게 되면 입력된 1, 10, 4, 9, 2, 3, 8, 5, 7, 6이 list로 변환되어 A=[1, 10, 4, 9, 2, 3, 8, 5, 7, 6]이 됩니다.

여기서 저는 기존의 input() 방식으로 값을 입력 받지 않았습니다.

여기서는 발생하지 않는 문제지만 한 두줄 입력받는 문제들과 다르게, 반복문으로 여러줄을 입력 받아야 할 때는 

input()으로 입력 받는다면 시간초과가 발생할 수 있습니다. 

그래서 ​백준 문제를 풀면서 input()으로 입력값을 받지 않고 sys 모듈을 사용하는 연습을 하고 있습니다.

 

 

다음으로는 for 문을 이용해서 range(N)에 입력받은 N값이 들어가게게 되는데 문제에서 N값이 10이므로 i는 0부터 9까지 입력받게 됩니다. 이제 if 문을 활용해 list에 있는 숫자들이 입력받은 정수 X값(5)보다 작을 경우에만 값을 출력합니다.

반복문을 흐름을 대충 표현하자면 A[0] = 1 < 5의 결과값이 TRUE이기 때문에 A[0]인 1을 print하게 됩니다.

 

그리고 결과값이 TRUE 인 A[i]값들을 한칸씩 띄워서 출력해야하기 때문에 print(end=' ')을 추가로 입력해주시면 끝입니다.

 

 

문제 2. 백준 2490번

https://www.acmicpc.net/problem/2309

2309번: 일곱 난쟁이

 

 

BaaaaaaaarkingDog's Solution

My solution

기본문제임에도 불구하고 생각보다 시간이 좀 걸렸습니다. 아직 알고리즘을 짜는데 익숙하지 않은 것 같습니다.

그래서 이 문제를 여러가지 혼자 풀고 난 뒤 여러가지 방법으로 풀어봤습니다.

 

Solution 1

우선 제가 풀었던 풀면서도 무식하다 생각한 방법입니다.

모든 난장이의 값을 list에 넣어주고 sum함수를 통해 아홉 난장이의 합을 구합니다.

그리고 이중 for문을 통해 9명중에 2명을 뽑아서 그 2명의 키를 뺀 값이 100일 경우 리스트에서 그 2명을 제거

해주고 마지막에 sort 함수를 통해 리스트를 정렬해주고 반복문을 통해 한줄씩 리스트 값을 출력했습니다.

좀 더 시간을 줄이고자 했으면 하나의 경우의 수를 찾아으면 break를 넣어서 반복문을 멈추는 것도 좋았을 것 같네요.

 

처음 했던 생각은 반복문 7개를 중첩해서 할까했는데 아무리봐도 아닌거 같아서 위처럼 풀어봤습니다.

이 후 비효율 적이라 생각해 여러 파이썬 코드를 참고하면서 좋은 solution을 알게됐습니다.

 

Solution 2

파이썬에서는 조합과 순열의 라이브러리를 제공합니다.

순열은 from itertools import permutations

조합은 from itertools import combinations 에 있는 라이브러리를 이용합니다.

n! 생각을 하긴했는데 이렇게 쉽게 라이브러리로 할 수 있을 줄은 몰랐네요.. 다음부터는 사용해보겠습니다.

 

재귀함수로 푸는 방법도 있는데 바킹독님의 재귀 강의가 뒤에 준비돼 있으므로 그때 공부해보겠습니다.

 

문제 3. 백준 10093번

https://www.acmicpc.net/problem/10093

10093번: 숫자

사실 어려운 이 문제는 어렵지 않았는데 처음으로 서브테스크가 나오기도 했고 언패킹을 처음해봐서 올렸습니다.

My solution

 

다른 설명은 필요 없을거 같고 빠르게 풀고 제출했는데 틀렸습니다!가 나와서 조금 당황했습니다.

그래서 다시보니 print(a_list)로 해서 [9,10,11,12,13]으로 출력이 돼서 틀렸습니다..ㅠ

그럼 어떻게 리스트 [] 대괄호를 없앨 수 있을까 찾아보다 *을 붙여주면 대괄호 없이 출력이 되더라구요.

언패킹과 서브테스크를 통해 시간복잡도도 고려할 수 있는 문제였습니다.

 

마치며...

https://github.com/moonjoo98/Codingt_test_study

GitHub - moonjoo98/Codingt_test_study: 바킹독님이 올려주신 강의별 문제집 파이썬 풀이입니다.

원래는 강의 후 풀어야할 문제집에 모든 문제를 글에다가 다 써보려했는데 02강 연습문제 백분 10871번 문제를 제외하고는 기초적인 연습문제이기 때문에 따로 블로그에 문제풀이를 적지는 않도록 하겠습니다.

혹시 필요하신 분이 있다면 위의 깃허브 링크에 모든 파이썬 문제풀이를 업로드 해놨으니 참고하시면 될 것 같습니다.

 

여기까지 기초강의 02강 파이썬 문제풀이 였습니다. 다음으로 03강 배열로 찾아뵙겠습니다.

 

다음 강의도 화이팅..!