시나위

https://www.acmicpc.net/problem/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 삼성 기출 문제이다. 이전에 풀었던 연구소 문제를 풀었는데 그 문제는 벽을 생성해서 안전구역을 최대화 시키는 것이었다. 이번 연구소 문제는 바이러스를 M개 활성화 시켜서 전체 구역을 감염시키는 최소 시간을 구하면 된다. 이 문제를 풀기 위해 다음과 같은 순서로 구현했다. 1) 입력을 받을 때 지도(이차원배열, _map)을 생성하고, 바이러스의 모든 위치를 파악한다(viruses). 2) 모든 바이러스에서 ..

SW Expert Academy 5658. [모의 SW 역량테스트] 보물상자 비밀번호 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 삼성 기출을 대비한 문제. 문자열을 사용하는 문제이고 쉬운 문제이다. 문자열을 회전시켜가며 k번째 큰 수를 출력하면된다. 문자열을 회전시킬때 조금 쉽게 하기위해 받은 문자열의 맨 처음글자부터 N//4까지의 글자를 복사해서 뒤에 넣어주었고 반복문을 사용해서 특정 길이까지 잘라서 set에 넣어주었다. set은 중복값이 제거되므로 넣어주기만 하면 된다. 모든 문자열을 순회한 이후엔 정렬을 한뒤 찾는 자리의 값을 반환했다. def find_number(string, string_size..

SW Expert Academy 5650. [모의 SW 역량테스트] 핀볼 게임 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 구현, 시뮬레이션 문제이고 딱 삼성 기출같은 문제였다. 문제 자체는 어렵진 않았고 꽤 복잡했다. 입력을 받고 모든 점마다 시뮬레이션을 돌린뒤 가장 점수가 높은 것을 출력하면 되었는데 시뮬레이션 돌릴때 꽤 애를 먹었다. 시뮬레이션 돌릴땐 블록이 아닌 모든 점에 대해서 진행했는데 최대한 중복되는 점들을 제거 하려고 노력했다. 예를 들면 시작하자마자 벽을 만나는 경우를 제거했고(이 부분은 1점을 줘야했는지 고민하긴했다.), 진행 방향의 다음 점이 빈 곳이면 중복이 되므로 제거했다. 조건이 되..

https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 구현 문제여서 그냥 풀기만 하면된다.(사람마다 풀이가 다 다를듯...) # import sys; input = sys.stdin.readline def check(): global N, L, _map ret = 0 for r in range(N): h = _map[r][0] cnt = 1 for c in range(1, N): if h == _map[r][c]: cnt += 1 h = _map[r][c] continue..

https://www.acmicpc.net/problem/20551 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net 이진탐색 문제이고 python 함수 bisect를 사용해서 풀었다. # import sys; input = sys.stdin.readline from bisect import bisect_left def index(a, x): i = bisect_left(a, x) if i != len(a) and a[i] == x: return i return -1 def main(): ..

https://www.acmicpc.net/problem/1865 1865번: 웜홀 첫 번째 줄에는 테스트케이스의 개수 TC(1 ≤ TC ≤ 5)가 주어진다. 그리고 두 번째 줄부터 TC개의 테스트케이스가 차례로 주어지는데 각 테스트케이스의 첫 번째 줄에는 지점의 수 N(1 ≤ N ≤ 500), www.acmicpc.net 이전 문제와 같이 벨만포드 알고리즘을 사용한 문제이다. edge를 그대로 넣고 사용할수도 있고 연결 그래프를 만들어서 사용할수도 있다. 뭐가 좋을진 문제마다 다를 것 같지만 이 문제에서는 edge를 사용하는게 조금 더 빠르다. 그래프를 사용하면 필요없는 곳까지 반복해야해서 시간이 더 걸리는 듯하다. 1) edge # import sys; input = sys.stdin.readline..

https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 시뮬레이션 문제여서 문제에 나와있는 순서대로 풀었다. 더보기 import sys; input = sys.stdin.readline from heapq import heappop, heappush def main(): N, M, K = map(int, input().split()) A = [list(map(int, input().split())) for _ in range(N)] t..

https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 백트래킹 문제이다. 한글자, 두글자씩 읽어서 확인하고 마지막까지 순회했을 때 (포커의 스트레이트 같이) 모든 값이 이어지는지 확인한다. # import sys; input = sys.stdin.readline def backtrack(ind, limit): global s, stack if ind == limit: max_v = max(stack) for i in range(1..

https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트래킹 연습을 위한 쉬운 문제 # import sys;input = sys.stdin.readline def backtrack(ind=0, cnt=0): global n, m, nums, ans_set, visit if cnt == m: tmp = tuple([nums[i] for i, v in enumerate(visit) if v]) if tmp not in ans_set: ans_..

https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 그리디 알고리즘으로 풀었다. 강의 시간을 정렬한 다음 모든 강의 시간을 순회하면서 힙 answer에 데이터를 추가하거나 수정하는 방식이다. 추가하는 시간은 해당 강의실의 강의가 끝나는 시간을 나타낸다. python의 heap은 최소힙이므로 0번째(top)가 최솟값이 되고 항상 모든 강의실 중 가장 빨리 끝나는 시간을 나타내므로, 강의실을 계속 사용해도 되는지 아니면 하나 더 사용해야하는지 판단할수 있다. import sys; input = sy..