본문 바로가기
728x90

알고리즘141

[PG/Python] N으로 표현 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/42895 코딩테스트 연습 - N으로 표현 programmers.co.kr 📌 문제 접근 방법 N으로 표현할 수 있는 숫자의 경우의 수를 생각해줬다. 우선 N은 1~8번만 사용하면 되고 그 외의 경우에는 -1을 리턴해주기 때문에 answer는 -1로 초기화한다. 인덱스를 N 사용횟수와 맞춰주기 위해 all_cases의 0번째에 빈 set을 넣어줬다. temp라는 set에 N을 i번 사용하여 나온 숫자를 저장할 것이다. set을 사용한 이유는 연산의 결과로 똑같은 숫자가 여러 번 나올 수 있기 때문에 중복을 제거해주기 위해서이다. N이 5라고 했을 때, 1번만 사용하는 경우는 5 하나밖에 없다. 2번 사용하.. 2021. 12. 22.
[PG/Python] 단어 변환 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 📌 문제 접근 방법 dfs를 사용하여 풀이하였고, 스택에 변환 횟수를 같이 저장해주었다. 만약 target 단어가 words에 없다면 바로 0을 리턴한다. words에 target이 있다면 스택에서 하나씩 pop하여 words에 있는 단어와 비교한다. words의 단어와 딱 한 글자만 다른 단어를 다시 스택에 .. 2021. 12. 22.
[PG/Python] 다단계 칫솔 판매 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/77486 코딩테스트 연습 - 다단계 칫솔 판매 민호는 다단계 조직을 이용하여 칫솔을 판매하고 있습니다. 판매원이 칫솔을 판매하면 그 이익이 피라미드 조직을 타고 조금씩 분배되는 형태의 판매망입니다. 어느정도 판매가 이루어진 후, programmers.co.kr 📌 문제 접근 방법 본인의 이름을 key값으로 추천인의 이름을 value로 recommender에 저장한다. 본인의 이익은 10%를 빼고 저장하고 temp에 10%만 다시 담는다. 계속해서 부모 노드(추천인)을 타고 올라가면서 10%만 담는 과정을 반복한다. 추천인이 -가 되거나 temp에 담긴 값이 0이 되면 반복문을 멈춘다. (0일때 안멈추면 .. 2021. 12. 17.
[PG/Python] 배달 📌 문제 https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 📌 문제 접근 방법 다익스트라 알고리즘을 사용하였다. 우선 각각의 노드간의 연결 관계를 인접행렬에 저장해주었다. 연결 관계가 2개 이상인 경우도 있기에, 이미 값이 있다면 최소의 거리를 저장하도록 했다. distance라는 리스트를 만들어서 여기에 해당 노드까지 가는 최소 거리를 저장하였다. 항상 출발지는 1번 노드이므로 1번 .. 2021. 12. 16.
728x90

티스토리툴바