본문 바로가기

Algorithm

 (129)
소문난 칠공주 (1941번) - 백준 (BOJ) https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 백준 - 소문난 칠공주 (Rigging the Bovine Election) (1941번) 난이도 : Gold 3 알고리즘&자료구조 : Simulation (구현) & Combinations (조합) import sys input = sys.stdin.readline from itertools import combinations def _adjs(r, c): if 0 < r: yield r-1, c ..
호텔 방 배정 (64063번) - 프로그래머스 (Programmers) https://school.programmers.co.kr/learn/courses/30/lessons/64063 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 - 호텔 방 배정 (64063번) 자료구조&알고리즘 : 유니온 파인드 (Union Find) 난이도 : Lv 4 2019 카카오 개발자 겨울 인턴십 기출문제이다. 오랜만에 유니온 파인드를 활용해서 풀 수 있는 문제였다. (유니온 없이 파인드만 적용했다.) import sys sys.setrecursionlimit(pow(10, 9)) class Hotel(): def __init__(..
감시 (15683번) - 백준 (BOJ) https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 백준 - 감시 (15683번) 난이도 : Gold 4 알고리즘&자료구조 : Simulation (구현) & DFS (깊이우선탐색) import sys input = sys.stdin.readline from copy import deepcopy class Office(): def __init__(self, N, M): self.blind = 64 dr = [1, -1, 0, 0] dc ..
너 봄에는 캡사이신이 맛있단다 (15824번) - 백준 (BOJ) https://www.acmicpc.net/problem/15824 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 백준 - 너 봄에는 캡사이신이 맛있단다 (15824번) 난이도 : Gold 2 알고리즘&자료구조 : Prefix Sum (누적합) Time Complexity : O( NlogN ) class Spicy(): def __init__(self, N): rem = 1_000_000_007 peppers = sorted(map(int, input().split())) for i in range(1, N): peppers[i] = (peppers[i-1]+peppers[i]) % r..
가르침 (1062번) - 백준 (BOJ) https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 백준 - 가르침 (1062번) 자료구조&알고리즘 : Combinations (조합) & Bitmask (비트마스크) 난이도 : Gold 4 처음에 비트마스크 안 쓰고 그냥 리스트로 기록해서 풀었는데 PyPy3에서는 통과했지만, Python3는 시간 초과가 나왔다. 그래서 Bitmask를 적용했더니 Python3에서도 통과했다. import sys input = sys.stdin.readli..
징검다리 건너기 (64062번) - 프로그래머스 (Programmers) https://school.programmers.co.kr/learn/courses/30/lessons/64062 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 - 징검다리 건너기 (64062번) 자료구조&알고리즘 : 우선순위 큐 (Priority Queue) 난이도 : Lv 3 2019 카카오 개발자 겨울 인턴십 기출문제이다. 처음에 파라메트릭 서치 (Parametric Search) 로 풀어봤는데, 효율성에서 5개 케이스 정도가 시간 초과가 발생했다. ''' Parametric Search 효율성 시간 초과 ''' class Steppin..
사냥꾼 (8983번) - 백준 (BOJ) https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 백준 - 사냥꾼 (8983번) 난이도 : Gold 4 알고리즘&자료구조 : Sorting (정렬) | Binary Search (이진 탐색) import sys input = sys.stdin.readline class Hunter(): def __init__(self): M, N, L = map(int, input().split()) sh..
문자열 압축 (60057번) - 프로그래머스 (Programmers) https://school.programmers.co.kr/learn/courses/30/lessons/60057 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 프로그래머스 - 문자열 압축 (60057번) 자료구조&알고리즘 : Exhaustive Search (완전 탐색) 난이도 : Lv 2 def solution(s): miny = n = len(s) for thr in range(1, (n>>1)+1): acc = 0 std = s[:thr] cnt = 1 for i in range(thr, n, thr): if std == s[i:i+thr]: cn..

티스토리툴바