본문 바로가기

알고리즘37

[Python] 비트마스킹 - 1094 막대기 https://www.acmicpc.net/problem/1094 1094번: 막대기 지민이는 길이가 64cm인 막대를 가지고 있다. 어느 날, 그는 길이가 Xcm인 막대가 가지고 싶어졌다. 지민이는 원래 가지고 있던 막대를 더 작은 막대로 자른다음에, 풀로 붙여서 길이가 Xcm인 막대�� www.acmicpc.net 풀이 결론부터 말하자면 입력값을 2진수로 변환했을때 1의 갯수를 찾는 문제이다. 합이 X가될때까지 계속 2로 나누고 하나를 버려야하니 2진수로 표현하는 것과 같다. 물론 구현 방식으로도 풀 수 있다. 코드 1. 입력값을 binary로 바꿔서 1의 갯수 세기 X = int(input()) answer = 0 X = bin(X) for x in X: if x == '1': answer += 1.. 2020. 8. 28.
[Python] 카카오 2019 - 블록 게임 https://programmers.co.kr/learn/courses/30/lessons/42894 코딩테스트 연습 - 블록 게임 [[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,0,0,0,0],[0,0,0,0,0,0,4,0,0,0],[0,0,0,0,0,4,4,0,0,0],[0,0,0,0,3,0,4,0,0,0],[0,0,0,2,3,0,0,0,5,5],[1,2,2,2,3,3,0,0,0,5],[1,1,1,0,0,0,0,0,0,5]] 2 programmers.co.kr 풀이 유튜브 ezsw 에서 c++로 풀이 해주신 거(링크)를 python으로 짠 코드이다. 각 모양의 블럭을 어떻게 찾아야하나 DFS라도 해야하나 .. 2020. 8. 19.
[Python] 카카오 2018 - 방금 그 곡 나의 풀이 import re def poundSign(m): m = re.sub(r'\w#', lambda x : x.group(0).lower()[0], m) return m def solution(m, musicinfos): ans ="(None)" ansT = -1 ans_dict = {} m = poundSign(m) for song in musicinfos: splt = re.split('[,:]', song) playingT = (int(splt[2]) - int(splt[0]))*60 + int(splt[3]) - int(splt[1]) splt[5] = poundSign(splt[5]) played = splt[5] * (playingT // len(splt[5])) + splt[5][:p.. 2020. 8. 19.
[Python] 슬라이딩 윈도우 1. 연속된 K개 요소의 최대 합 구하기 배열의 일정한 범위(k개 요소만큼) 1칸씩 미뤄가면서 합계 구해서 max와 비교def maxSum(arr, n, k): if not n > k: print("invalid") return -1 max_sum = 0 window_sum = sum([arr[i] for i in range(k)]) print(window_sum) for i in range(n-k): window_sum = window_sum - arr[i] + arr[i+k] max_sum = max(window_sum, max_sum) return max_sumarr = [1,3,7,4,8,4,0, 2]n = len(.. 2020. 8. 16.
[C++, Python] 투 포인터 3) BOJ 1806 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 문제 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 합이 특정값 S가 되는 부분 집합의 수를 구하는 문제에서 변형되어 합이 S이상인 부분 집합 중에 원소 개수가 가장 적은 부분집합의 원소 수를 구하는 문제이다. 만족하는 부분 집합이 없으면 0을 출력한다. 그래서 바뀐 부분이 1) start, end를 움직일때 cnt를 빼고 더해준다. 2) cnt >= mini 이면 start를 움직인다. (이전 문제에서는 sum >= S이면 이었음) 3) .. 2020. 8. 12.
728x90

티스토리툴바