본문 바로가기

Study/Python

programmers_level2_targetnumber 2021. 10. 8. 지난번에 공부한 dfs, bfs를 활용하여 이 문제를 풀어보자 문제는 다음과 같다. dfs를 활용하면 될 것 같다. 우선 알고리즘 먼저 짜 보자. 1. 리스트에 0을 정의해준다. 2. tmp리스트를 정의한 다음 1번에서 정의해준 리스트에 있는 인덱스를 기준으로 number의 0부터 인덱스를 더한 것과 인덱스를 뺀 것을 리스트에 append 해준다. 3. 1번에서 정의해준 리스트에 tmp를 저장한다. 4. 2,3번을 반복해준다. 5. 저장해둔 리스트에서 target이 몇 개 있는지 확인해준다. 코드 자체는 어렵지 않다. dfs, bfs를 공부하는 데에 오래 걸렸을 뿐이다..
BFS,DFS 2021. 10. 8. 프로그래머스 문제를 풀다가 bfs, dfs문제를 만나게 되어 공부를 해야겠다 싶어 공부를 해봤다. BFS(너비 우선 탐색) 우선 bfs는 breadth-first-search의 약자로 최대한 넓게 이동한 다음, 이동할 수 없게 되었을 때 밑으로 이동하는 것이다. 쉽게 그래프로 보자면 위와 같다. 루트 노드에서 인접 노드를 먼저 탐색하는 방법이다. 즉 가장 멀리 떨어져 있는 노드를 젤 나중에 찾아가는 방법으로 최단 경로를 찾을 때 많이 사용하는 탐색 방식이다. 큐를 이용해서 구현할 수 있으며 시간 복잡도는 접점을 V, 간선을 E라고 한다면 인접 리스트 O(V+E)가 되고, 인접 행렬은 O(V^2)가 된다. 파이썬 코드로 한번 구현해보자. 처음에는 list를 이용하여 pop 하는 형식으로 구현했지만 효율성 ..
programmers_level2_spicy 2021. 10. 7. 매운 것을 싫어하는 사람으로서 좋지 않은 문제인 것 같다. 보자마자 min heap을 사용하면 아주 이지하게 풀릴 것이라고 생각했다. 일단 알고리즘 먼저 생각해보자. 1. scoville의 순서가 뒤죽박죽 일 수 있으니 sorted로 정렬 먼저 해준다. 2. 정렬한 리스트를 heapq.heapify를 사용하여 heap으로 만들어 준다. 3. while문을 사용하여 heap의 첫 번째 인덱스가 k보다 커질 때까지 반복문을 돌린다. 4. 만약 특별한 방식을 사용해야 하는 인덱스 2개가 없으면, 즉 heap의 길이가 1이면 -1을 return 해준다. 5. heap의 첫 번째 인덱스가 k보다 작으면 첫 번째 인덱스와 두 번째 인덱스를 pop 해주고 특별한 방식을 통해 계산된 값을 heap에 넣어주고, 섞은 횟..
programmers_level2_functiondevelop 2021. 10. 7. 스택과 큐를 사용해야 하는 문제인 것 같다. 문제를 풀다가 갑자기 약속이 잡혀서 나도 모르게 타임어택을 하였다. 일단 문제는 별로 어려워 보이지 않았다. 알고리즘을 먼저 생각해 보자. 1. prgresses의 길이만큼 for문을 돌린 다음에 100에서 progresses의 각 인덱스를 뺀 뒤 speeds의 인덱스로 나눈다. 2. 1번에서 나눌 때 소수점이 나오면 안 되고 제한사항 4번에 하루의 끝에 배포가 이뤄진다 하였으니 소수점은 올려버린다. 3. 1,2번을 통해 구한 것들을 새로운 리스트로 정의해 준다. 4. 3에서 정의한 리스트의 길이만큼 for문을 돌리고 첫 번째 index를 max로 설정한고, 배포 개수인 cnt를 1로 설정해준다. 5. 두 번째 인덱스가 max보다 크면 하나만 배포되어야 하기 ..
programmers_level2_124country 2021. 10. 6. 124의 나라다. 뭔 놈의 나라가 1,2,4만 쓴다. 사실문제를 보고 3진법으로 변환하는 것과 비슷하다는 생각을 했다. 그래서 실제 3진법 변환과 비슷하게 코드를 짰다. 하지만 아래와 같이 딱 하나가 효율성 테스트를 통과하지 못해 문제를 넘어갈 수 없었다. 위 코드에서 while문 때문에 문제인가 싶어서 계속 생각을 해보다가 에라 모르겠다 하고 다시 채점을 해봤는데 맞게 나왔다.... 후 얘 때문에 상당히 많은 시간을 투자했는데 이렇게 허무하게 끝나버렸다. 그래도 다른 사람의 풀이를 한 번 봐 보았다. 오... 저번 박스 문제도 그렇고 규칙을 아주 나이스 하게 찾으신 분이 많은 것 같다. 이건 뭐 배울 수 없는 부분이니 ㅎㅎ..
programmers_level2_goodrectangle 2021. 10. 5. 2단계 3번째 문제다. 저번 문제를 아주 이지하게 풀어 자신감이 넘쳐서인지 이번 문제는 조금 당황했다. 문제를 보면 프로그래밍을 요구한다기보다 규칙 찾을 수 있어?라고 물어보는 것 같았다. 그래서 프로그래머스 처음으로 a4용지를 써서 알고리즘을 짜보았다. 처음 짰던 알고리즘은 다음과 같다. 1. 가로 세로 모두 소수이면 판별식을 쓴다. 2. 가로 세로 모두 소수가 아니면 최대공약수로 나눈 다음 판별식으로 보내고 다시 최대공약수를 곱해준다. 위와 같이 알고리즘을 짜고 코드를 짜 보니 몇몇 개의 테스트 케이스가 실패했다. 생각해보니 소수인지 아닌지를 따질게 아니라 3,8처럼 서로소인 것을 따졌어야 했다. 그래서 소수 판별 함수를 싹 지우고 알고리즘을 다시 짜보았다. 1. 둘 중에 하나가 1이면 완성되는 사각..
programmers_level1_prime 2021. 10. 5. 1단계라 쉽겠지 라는 생각으로 문제를 풀었다가 호되게 당했다. 문제는 간단하다. 그냥 소수를 구하는 문제다. 아무 생각 없이 for문 두 개 사용해서 소수 구하는 알고리즘을 짰다가, 마지막 테스트 케이스 3개와 효율성 검사에서 모조리 fail이 떠버렸다. for문 두 개를 쓰면 안 된다는 생각에 이거 저거 생각을 해보고 구현을 해보았지만, for문 두 개를 안 쓰고서야 내 머리에선 답이 나오지 않았다. 그래서 이번 문제는 구형님의 도움을 조금 받았다. 검색해보니 에라토스테네스의 체를 사용하여 풀어야 한다고 나왔다. 에라토스테네스 체는 만약 숫자가 소수이면 자기 자신을 제외한 나머지 자신의 배수들은 소수에서 제외하는 형식으로 소수 검사를 실시한다. 이렇게 되면 숫자 하나만 검사하면 그 숫자의 배수는 전부 ..
programmers_level2_openchat 2021. 10. 3. 2번째 문제다. 저번 문제를 약 2시간 동안 풀어서 이번 문제도 그 정도 걸리겠거니 하고 시작했다. 문제는 위와 같다. 딱 보면 할게 많아 보이지만 문제를 자세히 보면 별거 없다. 옵션이 3개밖에 안되기 때문이다. 그리고 user id를 보자마자 딕셔너리와 해시값 둘 중에 하나를 사용하면 쉽게 풀 수 있을 것이라 생각했다. 그리고 알고리즘을 짜 보았다. 1. 문자열로 들어오는 문장을 하나하나 쪼개서 다시 리스트에 정의해준다. 2. 1번에서 정의해준 리스트의 길이만큼 for문을 돌려서 enter과 change가 나오면 뒤에 있는 uid와 name을 딕셔너리에 저장해준다. 3. 다시 1번 리스트의 길이만큼 for문을 돌려서 enter나 leave가 나오면 딕셔너리의 정보를 참조하여 문장을 리스트에 저장한다...

티스토리툴바