상상쓰

https://programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 프로그래머스 4단계 문제치고는 쉬운 문제였다. 원형이라 처음과 끝은 인접하므로 경우를 나눠서 생각했다. 1. 끝을 생각하지 않는 경우 : 1 번 부터 차례대로 인접하지 않고 N-1 번으로 갈 때 훔칠 수 있는 돈의 최댓값 2. 처음을 생각하지 않는 경우 : 2 번 부터 차례대로 인접하지 않고 N 번으로 갈 때 훔칠 수 있는 돈의 최댓값 동적 계획법으로 구현하여 1..

https://programmers.co.kr/learn/courses/30/lessons/72413 코딩테스트 연습 - 합승 택시 요금 6 4 6 2 [[4, 1, 10], [3, 5, 24], [5, 6, 2], [3, 1, 41], [5, 1, 24], [4, 6, 50], [2, 4, 66], [2, 3, 22], [1, 6, 25]] 82 7 3 4 1 [[5, 7, 9], [4, 6, 4], [3, 6, 1], [3, 2, 3], [2, 1, 6]] 14 6 4 5 6 [[2,6,6], [6,3,7], [4,6,7], [6,5,11], [2,5,12], [5,3,20], [2,4 programmers.co.kr 저번에 풀었던 '배달' 문제랑 비슷하다. 다익스트라 알고리즘을 이용하여 (s, 도작..

https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net '0' 또는 '1' 이 연속되는 집단의 개수 중 작은 것을 반환하면 된다. 얼마 전에 정규식을 배웠기에 한 번 써봤다. import sys, re S = sys.stdin.readline() answer = min(len(re.findall(r'1+', S)), len(re.findall(r'0+', S))) print(answer)

https://www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net (0, 0) 부터 시작하여 (N-3, M-3) 까지 비교하면서 더는 바꿀 수 없는 구간에 대해서 A[][] 와 B[][] 가 다르면 -1 을 반환한다. 예를 들면 0 열부터 M-3 까지 비교하여 다음 행 차례가 오면 비교했던 행에 M-2 열과 M-1 이 바꿀 수 없는 구간이다. N 이나 M 이 3보다 작으면 3*3 크기의 부분 행렬이 없으므로 같으면 0 다르면 -1 을 반환한다. 이 예외 때문에 계속 틀렸었다...

https://programmers.co.kr/learn/courses/30/lessons/60063 코딩테스트 연습 - 블록 이동하기 [[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]] 7 programmers.co.kr BFS 알고리즘으로 일어날 수 있는 조건을 주어 구현하였다. 각 조건마다 코딩하여서 조금 길다. 한 칸 이동이 예를 들면 가로로 긴 블록일 때 좌우로 한 칸의 움직임만 허용되는 건 줄 알았는데 문제를 자세히 읽어보니 위아래로 가능하여서 틀리는 이유를 찾는데 조금 애먹었던 문제였다. from collections import defaultdict, deque def solution(board)..

https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 간단하게 생각해보면 같은 부호끼리는 절댓값이 큰 순서대로 묶어서 계산해야 최댓값이 된다. 양수하고 음수를 묶어야 할 상황에는 묶지 말고 더하는 것이 최댓값이 된다. 주의해야 할 점은 1과 0이다. 1은 무조건 더하는 것이 최댓값이 된다. 그리고 0은 양수랑 남으면 더하는 것이 최대지만, 음수랑 남으면 묶어서 계산하는 것이 최댓값이 된다. 그래서 우선순위 큐를 이용하여 부호에 따라 담을 큐를 두 ..

https://programmers.co.kr/learn/courses/30/lessons/12985 코딩테스트 연습 - 예상 대진표 △△ 게임대회가 개최되었습니다. 이 대회는 N명이 참가하고, 토너먼트 형식으로 진행됩니다. N명의 참가자는 각각 1부터 N번을 차례대로 배정받습니다. 그리고, 1번↔2번, 3번↔4번, ... , N-1번↔N programmers.co.kr 토너먼트이므로 n 과 상관없이 a 와 b 는 만난다. 1부터 두 명씩 그룹을 만들고 a 와 b 가 같은 그룹일 때 answer 을 return 해주면 된다. def solution(n, a, b): answer = 0 while True: answer += 1 a = int(a / 2 + 0.5) b = int(b / 2 + 0.5) i..

https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 휴가 기간이 20일이고 캠핑장은 연속하는 8일 중 5일만 사용할 수 있다고 하자. 그러면 적어도 캠핑장이 두 번 16일 열릴 것이고 5 * 2 = 10 일을 사용할 수 있다. 남은 4일과 다음 캠핑장이 열렸을 때 사용할 수 있는 기간인 5일과 비교하여 작은 값을 더해주면 휴가 기간 캠핑장을 이용할 수 있는 기간이 된다. 14를 return 하면 된다. import sys C = 0 answe..

https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 "스카피"는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하 programmers.co.kr 풀면서 while, for 가 많이 나와서 복잡하기도 하고, 이렇게 푸는 게 아닌가 싶기도 하여 다른 방법을 생각해보려고 하였으나 배열의 길이도 짧고 해서 한 번 시도해봤다. 다행히 통과되었다. 접근 방법은 [1, 5, 6, 10] -> [1, 5, 6, 10, 1+12, 5+12, 6+12, 10+12] 설정하여 반시계방향은 +12 해서 한 방향으로만 생각하도..

https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 우선순위 큐(heapq) 를 이용해서 가장 작은 2개의 숫자의 합을 계산해주고 그 값을 또 queue 에 넣어준다. 이러한 과정을 반복하여 queue 에는 하나의 값만 남을 때까지 계속한다. 마지막으로 숫자의 합을 계속 더해준 answer 를 return 한다. import sys import heapq answer = 0 N = int(sys.stdin.readline()) que..