본문 바로가기

Study/Python

programmers_level2_filename 2021. 11. 15. 2018년 kakao 문제다. 정답률이 66% 정도 되었다고 나와있는데, 내 수준에서 아직까지는 조금 어려운 것 같다. 접근을 잘못한 것도 있긴 하지만 그것도 실력이기 때문에 조금은 부족하다고 느꼈다. 문제는 위와 같다. 요약하자면 문자열들이 주어지고, 문자열에서 숫자가 나오기 전까지는 HEAD, 숫자가 나오고 숫자가 끊기거나 5개 이상의 숫자가 있다면 5개까지의 숫자는 NUMBER, 그 뒤는 TAIL에 해당한다. 나는 파이썬이 stable sort를 지원해준다는 것을 알고 있었기 때문에, tail을 사용할 필요 없이 슬라이싱을 잘 만하면 문제를 풀 수 있다고 생각했다. 그래서 문자열을 합쳐주는 것 대신에 HEAD와 NUMBER를 슬라이싱 하여 딕셔너리로 저장한 다음, sort를 통해 순서를 정해준 다음..
programmers_level2_rectangle (동적프로그래밍,DP) 2021. 11. 9. 카카오 문제를 풀고 나서 연습문제 정도야 쉬어가기로 풀어야지 하는 마음으로 문제를 풀었지만, 방금 막 풀었던 카카오 문제보다 훨씬 어려웠다... 문제는 이렇다... 솔직히 문제를 보고 좀 막막했다. 어떻게 풀어야 할지 감이 오지 않아서 숨겨져 있는 수학공식이 있나 확인해보고, brute force를 할까도 고민을 해봤다. 하지만 둘 다 방법이 없었다. 어떻게 해야 할지 고민하다가, 지난번에 풀었던 land가 생각났다 언뜻 보면 리스트 하나 주고 거기서 값을 구해봐라 이거와 같은 유형이었으니, 뭔가 비슷할 것 같았다. 그래서 점화식을 고민해봤다. 사실 이 친구도 리스트의 이전 값이 다음 리스트에 영향을 미치는 엄연한 점화식이었다. 그렇게 계속 고민해보니 결국 점화식으로 해결할 수 있었다. 1. 일단 1,1..
programmers_level2_ngame (진수변환) 2021. 11. 9. 1단계 이후로 오랜만에 보는 kakao 문제다. 문제는 이렇다. 별 이상한 게임을 다한다. 문제는 길었지만 생각보다 조건이 몇 개 없었다. 진법 받아주고, 튜브가 미리 말할 숫자 개수, 인원, 순서 등만 받아주고 이를 토대로 튜브가 말할 숫자 t개만 출력하면 되는 문제였다. 문제 알고리즘 자체는 별로 어렵지 않았는데, 진법 계산이 중요했던 문제였다. 사실 진법 계산은 1학년 때부터 C언어로 단련돼 오던 유형이라 어렵지 않게 파이썬에 짜줄 수 있었다. 재귀를 사용하면 아주 쉽게 진수 교환을 구현해 낼 수 있다. 물론 16진수까지 만이다. 바꾸려는 수 n과 진법 base를 받아주고, 16진수 까지 나타내야 하기 때문에 T를 0부터 F까지인 문자열로 정의해준다. 그리고 divmod를 사용하여 n과 base를 ..
programmers_level2_land (동적프로그래밍,DP) 2021. 11. 8. 바로 문제를 보자. 문제는 위와 같다. 처음에는 보자마자 각 행에 있는 최댓값을 골라 더해주면서 만약 어떤 행의 최댓값 인덱스가 앞 행의 최댓값 인덱스와 겹치면 그 인덱스의 값을 0으로 바꿔버리고, 그중에서의 최댓값을 출력하는 식으로 코드를 짜 봤다. 문제 예제에 나와있는 예시는 쉽게 통과할 수 있었다. 하지만, 한 행에 최댓값이 여러 개일 경우 더 좋은 길이 있음에도 그 부분을 택하지 못했다. 예를 들어 [[4,3,2,1], [2,2,2,1], [6,6,6,4], [8,7,6,5]]라는 배열이 있다고 해보자. 두 번째 행에서 최댓값인 2가 3개이므로 코드는 맨 앞에 있는 2를 선택해야 하지만, 첫 번째행과의 인덱스가 겹치기 때문에 가장 인접해있는 두 번째 인덱스인 2를 선택한다. 그리고 세 번째 행에서..
programmers_level2_jadencase 2021. 10. 26. 생판 처음 보는 case의 문자열 만들기다. 문제는 다음과 같다. 처음에는 공백이 몇 개이든 상관없이 문자열을 split으로 리스트로 정의해준 다음 리스트의 첫 번째 문구 즉 [0][0] 인덱스를 upper로 만들어서 출력을 했다. 하지만, 문자열 처음이 공백이거나, 중간에 공백이 여러 개 있을 경우에 몇 개이건 상관없이 하나의 공백만을 출력하여 오류가 났다. 그래서 고민해 본 것이 공백의 뒤에 문자가 오게 되면 upper을 해서 저장해 둔 뒤 문자열을 삭제하고 그 자리에서 추가해 줄 수 없기 때문에 슬라이싱을 활용해 공백까지의 문자열과, 공백 뒤에 문자를 Upper로 바꾼 문자와 그 문자 뒤부터 끝까지의 문자열을 합해 문자열로 정의한 다음 출력을 해주면 된다. 코드는 다음과 같다. 중간에 if문을 하나..
programmers_level2_nlcm 2021. 10. 26. level 2의 그나마 쉬운 문제들이 뒤쪽에 포진되어 있는 것 같아 이제부터 맨 뒤부터 풀기로 하였다. 문제는 간단하다. 여러 개의 숫자가 나왔을 때 이 숫자들의 최소공배수를 구하는 문제였다. 처음에는 맨 첫 인덱스로 문자열을 싹 돌면서 나눠 떨어지면 몫을 arr에 저장하고, 아니면 숫자 그대로를 arr에 저장하고, 마지막까지 다 돌면 arr들을 곱하는 식으로 알고리즘을 짰다. 결과는 어림도 없었다. 최소공배수는 나눠질 수 있을 때까지 나눠야 하는데 내가 짠 알고리즘은 한 번씩만 나누면 끝났기 때문이다. 그래서 생각한 것이 2개씩 짝찌어서 최소공배수를 구하고 마지막 남은 2개의 최소공배수를 구하면 결국은 arr의 최소공배수를 구할 수 있을 것이라 생각했다. 마지막 2개 인덱스의 최소공배수를 -2의 인덱스..
programmers_level2_mostnumber 2021. 10. 25. 오랜만에 알고리즘 문제를 손대 보았다. 오랜만이라 그런지 아니면 문제가 난이도가 있어서 그런지 조금 고전을 했다. 문제는 위와 같다. 문제 자체가 복잡하지는 않다. 그 말인즉슨 알고리즘이 어려울 수도 있다는 것이다. 처음에는 보자마자 permutation을 사용해서 풀면 된다는 생각에 신나게 코드를 작성했다. 그렇게 테스트 케이스를 통과는 했지만 시간 초과 때문에 답을 통과할 수는 없었다. 그래서 이거 저거 찾아보다가. 이런 것을 발견하였다. 원래 알고 있었지만 새까맣게 까먹고 있었던 것... 문제에서 자릿수를 정해주었기 때문에 자릿수만 맞춰주고 문자열로 문자들을 비교만 해주면 자동으로 sort가 되는 문제였다. 그래서 lambda로 자릿수를 최대 1000이므로 4자리까지 맞춰주고 정렬을 진행하면 알아서..
programmers_level2_menu 2021. 10. 17. 오랜만에 2단계 문제를 풀어보자. 문제가 꽤 길다. 처음에는 문제 이해가 잘 안 돼서 2~3번 정도 읽어본 것 같다. 알고리즘을 한 번 짜 보자. 1. combination을 하기 위해 course의 크기만큼 For문을 돌린다. 2. orders의 인덱스마다 combination을 진행하기 위해 orders의 크기만큼 for문을 돌린다. 3. course의 인덱스 크기만큼 orders의 인덱스에서 combinations을 해주고 리스트로 저장한다. 4. 3번의 리스트로 저장한 값들을 딕셔너리로 재 정의해주면서 value를 1로 정의한다. 5. orders의 인덱스를 돌면서 3번을 진행해주고 딕셔너리로 저 정해주는 과정에서 4번에서 저장한 딕셔너리에 key값이 있으면 value를 +1해 주고 아니라면 va..

티스토리툴바