[Programmers] - 순위 (그래프) with Python

📎 간략한 문제 정리 n명의 권투선수의 승패가 배열로 주어집니다. 이 배열에서 승패를 기준으로 순위를 매겼을 때, 위치가 확정되어있는 사람의 수를 구하는 문제입니다. 📈 문제 분석 예시의 배열을 분석해보면에서 4는 3번에게 이기고, 4는 또 2번에게 이기고, ... 2번은 5번에게 이깁니다. 이를 기준으로 생각해보면 2는 1, 3, 4에게 지고 5번에게 이기므로 반드시 4위에 위치합니다. 1을 제외하고 생각해보면 4, 3, 2, 5의 위치는 서로 결정이 되지만 1이 4 앞에 올 수도, 4와 3 사이에 올 수도, 그리고 3과 2 사이에 올 수 있으므로 1, 3, 4의 위치는 확정되지 않습니다. [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 🙋‍♂️ 내가 처음 생각한 해결 방법 처..
알고리즘 학습/프로그래머스 2021. 4. 22. 16:04
[Programmers] - 방문 길이 (Summer/Winter Coding(~2018)) with Python

📎 간략한 문제 정리 좌표평면상의 점 이동을 추적하여 이동 거리를 계산하는 문제입니다. 단 이동 루트가 중첩되는 경우 한 개의 이동거리만 계산합니다. 📈 문제 분석 조심해야할 부분은 좌표평면의 사이즈가 정해져 있는 점입니다. 정해진 범위를 벗어나는 이동 명령은 아예 무시합니다. 포인트는 이동한 위치를 체크하는 것인데 시작점과 끝점을 묶은 튜플로 표현할 수 있습니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 겹치는 부분을 제거하기 위해 여러가지 방법이 있을 수 있습니다. x좌표, y좌표가 더 작은 점을 왼쪽 기준점으로 두어 검색하여 존재 여부를 확인하고 추가할 수 있지만 이렇게 sort를 하게되면 O(N)이므로 비효율적입니다. Dictionary를 사용할 수 있지만 기준을 맞추기 위해서는 결국 sort를 해야..
알고리즘 학습/프로그래머스 2021. 4. 21. 22:50
[Programmers] - 게임 맵 최단거리 (찾아라 프로그래밍 마에스터) with Python

📎 간략한 문제 정리 시작점 (0, 0)에서 도착점 (n-1, m-1)에 도착하기까지 최단거리를 구하고, 도착이 불가능할 경우 -1을 출력하는 메소드를 구현합니다. 📈 문제 분석 최단거리를 찾는 문제는 전형적인 BFS 문제로 BFS를 구현하며 도착점에 도착하면 그때까지의 depth를 출력하면 됩니다. 🙋‍♂️ 내가 처음 생각한 해결 방법 이 문제는 최단거리이기 때문에 BFS가 더 적합해보이지만 DFS로도 한번 같이 구현해보았습니다. 💻 풀이한 코드 # BFS def solution_bfs(maps): from collections import deque n, m = len(maps), len(maps[0]) visited = [[-1 for _ in range(m)] for _ in range(n)] v..
알고리즘 학습/프로그래머스 2021. 4. 21. 19:49
프로그래머스 - 올바른 괄호의 갯수 (level 4 연습문제) [Python]

문제 programmers.co.kr/learn/courses/30/lessons/12929 코딩테스트 연습 - 올바른 괄호의 갯수 올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모 programmers.co.kr 문제 상황 - 괄호쌍의 개수를 입력받아 만들 수 있는 서로 다른 괄호쌍의 종류의 수를 출력한다. 해결 전략 - 1, 2, 5, 14, 42로 증가하는 전형적인 카탈랑수 문제이다. 코드 1 2 3 4 5 6 def factorial(n:int) -> int: if n == 1: return 1 return n*factorial(n-1)..
알고리즘 학습/프로그래머스 2021. 1. 12. 22:53
프로그래머스 - 이중우선순위큐 (Heap) [Python]

문제 programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 문제 상황 - operations를 순회하며 명령어가 "I 숫자" 이면 큐에 숫자를 삽입하고, "D 1"은 큐에서 최댓값을 삭제하며 "D -1"은 큐에서 최소값을 삭제한다. 해결 전략 - 문제는 파이썬에는 최소힙만 구현이 되어있고 최대힙이 구현되어있지 않다. 즉, 최소값을 삭제하는 것은 O(1)로 가능하지만 최대값은 그럴 수 없다. 그래서 python의 heapq의 내장함수인 nlargest를 활용한다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 def solution(operations:list) -> list: import heapq..
알고리즘 학습/프로그래머스 2021. 1. 12. 22:06
프로그래머스 - 점프와 순간 이동 (Summer/Winter Coding(~2018)) [Python]

문제 programmers.co.kr/learn/courses/30/lessons/12980 코딩테스트 연습 - 점프와 순간 이동 OO 연구소는 한 번에 K 칸을 앞으로 점프하거나, (현재까지 온 거리) x 2 에 해당하는 위치로 순간이동을 할 수 있는 특수한 기능을 가진 아이언 슈트를 개발하여 판매하고 있습니다. 이 아이언 슈 programmers.co.kr 문제 상황 - 연료를 사용하여 점프를 하거나, 연료 사용없이 지금까지 이동해온 거리만큼 순간이동을 하여 움직이는데 목표점을 정확히 도착하는데 최소의 연료로 도착할 때 연료 소비량을 계산한다. 해결 전략 - 최대한 2배가 되는 것을 활용해야 하고 점프를 최소화 해야한다. 역으로 생각하여 2배로 이동하는 것을 최대로 활용하기 위해 주어진 n을 2로 나..
알고리즘 학습/프로그래머스 2021. 1. 10. 18:46
프로그래머스 - 예상 대진표 (2017 팁스타운) [Python]

문제 programmers.co.kr/learn/courses/30/lessons/12985 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 문제 상황 - 1번부터 n번까지 사람이 게임을 진행한다고 할 때 a, b는 모든 게임에서 이긴다는 조건으로 게임을 진행한다. a와 b가 만날 때까지 진행된 게임의 수를 계산한다. 해결 전략 - 주어진 수를 2로 나누며 같아질 때까지 반복하여 그 횟수를 출력한다. 코드 1 2 3 4 5 6 7 8 9 def solution(n,a,b): cnt =..
알고리즘 학습/프로그래머스 2021. 1. 10. 14:07
프로그래머스 - 다트 게임 (2018 KAKAO BLIND RECRUITMENT) [Python]

문제 programmers.co.kr/learn/courses/30/lessons/17682 코딩테스트 연습 - [1차] 다트 게임 programmers.co.kr 문제 상황 - 3번의 다트 게임을 시행하는데 총 점수를 계산한다. 점수 계산법은 S,D,T와 #, * 를 활용한다. 해결 전략 - 정규 표현식을 사용하면 편할 수 있을 것 같지만 문제의 난이도가 낮아 단순한 문자열 탐색으로 가능하다. 문자열을 순회하며 게임 하나의 케이스로 판별하는 조건을 정의하여 게임의 점수를 계산해 나간다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 def get_score(dart:str) -> int: if dart[-1] ..
알고리즘 학습/프로그래머스 2021. 1. 10. 13:29
1 2 3 4 5 6