https://school.programmers.co.kr/learn/courses/30/lessons/176963 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 파이썬의 dictionary 자료형 문법을 잘 활용할 줄 알면 간단하게 풀 수 있는 문제이다. dictionary에서 key를 가지고 값을 가져올 때, dict[key] 로 가져오는 경우 해당 Key가 없으면 에러를 발생시킨다. 에러를 발생시키고 싶지 않은 경우에는 dict.get(key) 로 가져오면 None을 반환한다. def solution(name, yearning, photo): yea..
알고리즘💻
https://school.programmers.co.kr/learn/courses/30/lessons/178871 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 단순하게 players 배열을 순회하는 방식으로 구현을 한다면, 당연하게 시간초과가 나는 문제였다. 파이썬의 dictionary 자료구조를 이용해서 인덱스를 value로, 이름을 key로 갖는 dict로 바꿔서 인덱스를 더 빠르게 알아낼 수 있도록 구현해야 한다. enumerate 메소드를 사용해서 리스트를 dictionary로 변환하는 문법에 익숙하지 않아 구글링을 했는데, 앞으로 많이 쓰일 ..
https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 처음에는 그리디 문제라는 걸 깨닫지 못하고.. 거리를 직접 구해서 비교하려고 하다가 그림을 몇 번 그려보니.. 그냥 정렬을 해서 중간 값을 출력하면 된다는 것을 깨달았다. 이렇게 간단하게 풀리는 문제였다니! 항상 그리디를 의심하자.. import sys input = sys.stdin.readline N = int(input()) house = list(map(int, input().split())) house.sort..
https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 아파트 층을 한 방향으로 연결된 그래프(리스트) 라고 생각을 하고 BFS로 풀면 간단히 풀 수 있는 문제이다. graph 배열을 만들어서 INF로 채워넣고, 처음 방문하게 되면 이전 위치의 값에서 1을 더한 값을 저장했다. import sys from collections import deque input = sys.stdin.readline F, S, G, U, D = map(int, input().spli..
https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 0과 1이 모여있는 집단(?) 의 갯수를 구해서 더 적은 쪽을 출력하면 되는 문제였다. cnt = [0, 0] 을 만들어서 주어진 문자열을 순회하면서 앞의 문자와 뒤의 문자가 달라질 때마다 해당하는 인덱스에 카운트를 했다. 이때 주의할 점은 '0011' 과 같은 경우에 마지막 11이 카운트가 되지 않기 때문에 주어진 문자열의 맨 뒤에 '2'를 추가해서 무조건 카운트가 되도록 했다. import s..
https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 처음에는 정말 단순하게 이중 for문을 사용해서 생성자가 있는지 없는지 체크하는 방식으로 아래와 같이 코드를 작성했다. for i in range(1, 10001): flag = True for j in range(1, i): num = j for k in str(j): num += int(k) if (num == i): flag = False b..
https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 아이디어를 찾는 게 꽤나 어려웠던 문제이다. 처음에는 가격을 그래프로 그렸을 때 꼭짓점을 찾아서 꼭짓점의 앞에서 주식을 사고 꼭짓점에서 팔고, 또 계속 사다가 다음 꼭짓점에서 팔고 이런 식으로 하면 되지 않을까? 싶었지만 꼭짓점이 고점이 아닌 경우 해당 지점에서 주식을 매도하는 것보다 주식을 매수하는 게 더 이득이 크기 때문에 해당 접근 방식은 틀렸다. 단순하게 다시 생각해보니, 일단..
https://www.acmicpc.net/problem/9009 9009번: 피보나치 입력 데이터는 표준입력을 사용한다. 입력은 T 개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 테스트 데이터의 수를 나타내는 정수 T 가 주어진다. 각 테스트 데이터에는 하나의 정수 n www.acmicpc.net 하나의 양의 정수가 주어질 때, 피보나치 수들의 합이 주어진 정수와 같게 되는 최소 개수의 서로 다른 피보나치 수들을 구하라. 이때 피보나치 수는 증가하는 순서대로 출력 그리디 알고리즘이라는 것을 생각하고 규칙을 찾으면 간단하게 풀 수 있는 문제였다. 처음에는 피보나치라고 해서 dp를 사용해야 하나 했는데.. 다시 생각해보니 그럴 필요가 전혀 없었다. 피보나치 수를 생각해보면 f(n+1) = f(n)..
https://www.acmicpc.net/problem/14891 14891번: 톱니바퀴 첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 www.acmicpc.net 문제의 설명대로 말 그대로 "구현"하는 문제였다. 다만 문제의 조건을 이해하는 게 어려웠는데, 톱니바퀴가 회전 된 후의 상태로 비교하는 게 아니라 회전하기 전 상태를 기준으로 비교하는 것이라서 먼저 회전을 시키면.. 다음 번 톱니바퀴가 도는지 안도는지 확인할 때 어려움이 있었다. 톱니바퀴를 회전시킨다는 점에서 큐를 사용해야 한다는 것과, 재귀를 사용해야겠다는 아이디어가 떠올라 구현을 일단 해..
https://www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 평범한 다익스트라 문제에 방문하지 못하는 정점의 조건을 더한 문제이다. 중간에 현재 방문한 정점과 연결된 정점이 방문할 수 있는 정점인지를 확인하는 조건문을 추가했다. import sys, heapq N, M = map(int, input().split()) check = list(map(int, input().split())) graph = [[] for _ in ra..
