알고리즘
![[프로그래머스] 예상 대진표](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F9nn1U%2Fbtrb1cWlRvP%2FrClNuzhMPMCoGwWABh0Fe1%2Fimg.png)
[프로그래머스] 예상 대진표
일단 재귀함수의 개념도 다시 짚고 가야했다. 1. 문제 설명 문제 상황은 토너먼트 상황이다. n은 참가하는 참가자 수이고, a와 b의 값은 각각 a와 b가 참가하는 순서이다. 여기서 문제는 a와 b가 무조건 각 토너먼트에서 승리하고 올라간다면, 언제 2명이 경쟁하는 순간이 오느냐이다. 그림으로 보면 다음과 같다. 노란색 네모가 최초의 4번째 참가자인 a이고, 연두색 네모가 최초의 7번째 참가자인 b이다. a와 b가 대결을 하게 되는 순간은 3번째 경기 과정이고 문제에서는 이 3번째를 구하는 함수를 요구한다. 2. 어려웠던 점 1) 재귀함수 return 처음에 코드를 이렇게 작성했는데, None을 리턴하게 되었다. def dfs(n, a, b, cnt): if abs(a - b) == 1: return c..
[프로그래머스]수식 최대화
내가 했던 삽질 이 문제는 정말 삽질을 많이 했던.. 그리고... 정말 오래걸렸던 문제이다. 일단 처음에 BFS를 사용하려고 했고, 정규표현식을 사용하려고 했었다. .. 그러다가 점점 산으로 갔다. 아무튼 !!! 문제 해석 + 요구사항을 확인해보자. 1. 문제 해석 주어진 사칙연산의 개수는 *,-,+ 3가지 이다. 3가지를 활용해서 만들 수 있는 모든 연산순위를 주어진 문자열에 이용하여 연산했을 때 나올 수 있는 최대값을 구하기 2. 요구사항 1) *,-,+ 3가지 연산자를 활용하자 -> 여기서 3!임으로 6가지 밖에 없어 특별히 combination을 사용할 필요가 없다. 2) 주어진 문자열 패턴에서 연산자 순위를 적용해 우선풀이 3. 내가 실수한 것 1) 내가 만들려고 했던 함수는 다음과 같다. 3가..
![[프로그래머스] 메뉴 리뉴얼](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbkLR5Z%2FbtrbW1GKaOO%2FKgCW0nRKbuMkhO1plTbZD1%2Fimg.png)
[프로그래머스] 메뉴 리뉴얼
갑자기 글이 날라갔다.. 후... 나름 또 시간 들여서 쓴 글인데 ... 아무튼 이 문제는 문제를 꼼꼼히 읽어야 했던 그런 문제.. 1. 문제 설명 문제 각 손님들이 주문한 단품메뉴들이 문자열 형식으로 담긴 배열 orders, "스카피"가 추가하고 싶어하는 코스요리를 구성하는 단품메뉴들의 갯수가 담긴 배열 course가 매개변수로 주어질 때, "스카피"가 새로 추가하게 될 코스요리의 메뉴 구성을 문자열 형태로 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 입출력 예시 입출력 예에 대한 설명 입출력 예 #2 AD가 세 번, CD가 세 번, ACD가 두 번, ADE가 두 번, XYZ 가 두 번 주문됐습니다. 요리 5개를 주문한 손님이 1명 있지만, 최소 2명 이상의 손님에게서 주문된..
[프로그래머스]소수 찾기
에라토스테네스체 개념을 되짚어 보고, 문제 조건을 세심히 읽어야할 필요성을 일깨워준 문제이다. 그리고, 지스트 https://gist.github.com/ 라는 사이트를 알게 되었다. 코딩 테스트 볼때에 유용하게 관리할 수 있기 때문에 한번 해보려고 한다...!(언제할지는 모르겠지만 ^^)... 아무튼 나는 이 문제를 풀때 3가지 짚고 넘어가야할 부분이 있었다. 1. 에라토스테네스의 체 def eratosthenes(): prime[0] = prime[1] = False for i in range(2, 10000001): if prime[i] == True: for j in range(2 * i, 10000001, i): prime[j] = False 개념을 다시 생각해보면, 0과 1은 소수가 아닌 수로..
[프로그래머스]전화번호 목록
그렇게 어렵지 않았던 문제이고, 나는 배열을 활용해서 풀었다. 그런데, 시간초과랑 테스트 케이스에서 2~3개 정도 틀렸다. 풀이 이전에, 알고넘어가야 할 메소드만 정리한다. 문자열 클래스에서 제공되는 메소드! isdigit() -> 해당 문자열이 숫자인가? stasrtswith(a) -> a로 시작하는 문자열인가? swapcase() -> 문자열의 대소문자를 바꿔준다. 훨씬 더 많은데, 일단 이것만 기억하기로... 1. 리스트로 풀이 일단 이 문제를 해시를 사용해서 풀기에는 애매했다. 분명 내가 해시를 잘 활용할 줄 몰라서 그렇다. 일단 내가 처음 풀었던 풀이는 다음과 같다. def solution(phone_book): for idx, val in enumerate(phone_book): temp = ..
[프로그래머스]프린터
from collections import deque def solution(priorities, location): d = deque([(v, i) for i, v in enumerate(priorities)]) cnt = 0 while True: temp = d.popleft() if len(list(filter(lambda x: x[0] > temp[0], d))) > 0: d.append(temp) else: cnt += 1 if temp[1] == location: return cnt 난이도가 높은 문제는 아니었다. 하지만, 인덱스 문제가 있어서 난관이 있었던 문제 ! 배열의 인덱스를 직접 조작하거나 확인 + 원소 자체를 삭제해야 하는 그런 로직이 있는 경우, 나만의 전략을 세웠다. 최대한 fo..
![[프로그래머스]거리두기 확인하기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbHd7YU%2FbtrbPb5cxNY%2F9kTGMvQ1ZiPzJj671HNhkK%2Fimg.png)
[프로그래머스]거리두기 확인하기
기본적으로 BFS의 개념과 파이썬에서 사용하는 데크의 개념을 알고있어야 풀 수 있는 문제였다. 나는 두가지 다 제대로 몰랐기 때문에 못품 ;; 답안을 봐도 한번에 이해하기 힘들었다. 이거 레벨2 맞나...? 또르르... 아무튼 다른 블로그에서 보면서 코드를 이해한 내용을 바탕으로 문제 풀이를 해볼 예정이다. 일단 문제풀이를 하기 전에 BFS와 파이썬의 데크 개념을 정리할 것이다. 1. BFS 너비 우선 탐색이다. 문제를 풀 때 이 문제가 BFS다 라고 생각이 들면, BFS를 적용할 줄 알아야한다. 이번 문제도 동일한 부류인데, 과연 내가 실제 문제 풀이에서 이런 로직을 적용할 수 있을지는 모르겠다. 아무튼 BFS 개념을 정리한다. 1. 트리로 그려보자 BFS든, DFS든 트리를 그려서 풀이하는게 좀 더 ..
![[프로그래머스]배달](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fc76rJo%2FbtrbPcpvA7O%2FmxP1V9Cy5F7x4zS5plcgG1%2Fimg.png)
[프로그래머스]배달
다익스트라 알고리즘 + 인접행렬을 활용하는 문제였다. 나는 다익스트라 알고리즘의 개념을 완전 까먹고 있었다. 다익스트라 알고리즘 개념은 이 게시글로 포스팅했다. 혹시나 개념을 모른다면 꼭 참고해서 숙지해두길 바란다. heapq 모듈에 대해서도 복습할 수 있다. 다익스트라 풀이법과 모두 동일하다. 1. 문제 설명 N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려..