시나위

https://www.acmicpc.net/problem/11562 11562번: 백양로 브레이크 서울 소재 Y모 대학교에서 대규모 공사를 진행하면서, 학교가 마치 미로처럼 변해버리고 말았다. 공사 이전까지는 어떤 건물에서 출발하더라도 다른 모든 건물로 갈 수 있는 길이 있었으나, 공 www.acmicpc.net 플로이드 와샬 알고리즘을 사용해서 풀면된다. 뒤집지 않고 갈수 있으면 0을 넣고 한번이라도 뒤집어야한다면 1을 넣어서 초기화한다. 이후 floyd-warshall 알고리즘(i에서 k를 거쳐 j를 가능 방법)을 사용해서 최솟값으로 갱신하면 된다. import sys; input = sys.stdin.readline def floyd_warshall(n, visit): for k in range(1..

https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 시뮬레이션 구현 문제이다. 시뮬레이션 문제는 풀이라고 하는게 딱히 없는 것 같다. # import sys; input = sys.stdin.readline d = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 상하좌우 def only_one_shark_left(): global sharks_pos for i in range(1, le..

https://www.acmicpc.net/problem/21924 21924번: 도시 건설 첫 번째 줄에 건물의 개수 $N$ $(3 \le N \le 10^5 )$와 도로의 개수 $M$ $(2 \le M \le min( {N(N-1) \over 2}, 5×10^5)) $가 주어진다. 두 번째 줄 부터 $M + 1$줄까지 건물의 번호 $a$, $b$ $(1 \le a, b \le N, a ≠ b)$와 두 www.acmicpc.net 최소 신장 트리 문제이다. Prim 알고리즘으로 풀었다. 인접한 정점(건물)을 추가하는 연결리스트를 만들고 신장트리를 만든다. 그리고 최소 값인 도로끼리 연결해야하므로 heap 자료구조를 사용한다. 신장트리는 정점 1부터 시작해서 인접하되 방문하지 않은 정점들을 추가한다. h..

https://www.acmicpc.net/problem/2745 2745번: 진법 변환 B진법 수 N이 주어진다. 이 수를 10진법으로 바꿔 출력하는 프로그램을 작성하시오. 10진법을 넘어가는 진법은 숫자로 표시할 수 없는 자리가 있다. 이런 경우에는 다음과 같이 알파벳 대문자를 www.acmicpc.net 손풀겸 푸는 문제 딕셔너리 자료형을 사용해서 '0'부터 '9'까지 그리고 'A'부터 'Z'까지 생성한뒤 각 자리에 맞는 값을 구해서 계속 더해주었다. import sys nums_dict = dict(zip( map(chr, range(ord('A'), ord('Z') + 1)), range(ord('A') - ord('A') + 10, ord('Z') - ord('A') + 11) )) for i..

https://www.acmicpc.net/problem/1072 1072번: 게임 김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시 www.acmicpc.net 확률 Z값을 구하고, s와 e의 중간값으로 만든 새로운 확률이 Z보다 큰 값을 찾으면 된다. 그리고 커지는 값중에 최솟값을 찾아야하니 s가 e보다 커지는 값을 종료 조건으로 반복문을 설정해서 이분탐색을 하면 된다. def main(): X, Y = map(int, input().split()) Z = (Y * 100) // X s, e = 0, X while s

https://www.acmicpc.net/problem/13022 13022번: 늑대와 올바른 단어 첫째 줄에 단어가 주어진다. 단어는 w, o, l, f로만 이루어져 있으며, 길이는 50을 넘지 않는다. www.acmicpc.net 문자열은 파이썬이 편하다. 마지막에 f가 있을거라 예상해서 f를 기준으로 단어를 나눴다(인덱스만 저장). 그리고 각각의 인덱스를 기준으로 4의 배수인지 확인하면 wwwoolllfff 같이 중간에 하나 빠져있는 단어들을 제거할수 있다. 그다음은 wlof 와 같은 단어를 제거한다. 나누어진 단어의 길이를 4로 나누면 한 단어당 나와야하는 알파벳의 갯수가 나온다. 이 개수로 wolf 각각 문자열을 곱하고 더해서 단어를 만들고 원래 기존의 단어와 비교하면 제거할수 있다. 여기까지..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net pypy에선 되는데 python에선 시간초과와 메모리 초과가 뜬다. python에서 하려면 다른 방법으로 접근해야한다. 문자 테이블을 만들어서 두 문자열을 비교했다. 비교하는 알파벳이 같으면 1로 체크하고, 같지 않으면 0으로 체크한다. 여기서 공통부분 문자(1이 체크된 것)에서 대각선 방향으로 가장 긴 배열찾으면된다. 길이를 알아야하므로 memoization을 실행할때 공통문자이고, ..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분탐색 문제이다. 높이를 오름차순으로 정렬하고 시작점은 0, 끝점은 가장 큰 값(정렬했으므로 마지막 값)으로 설정해서 이분탐색을 한다. 합이 M보다 작거나 같을때는 최솟값을 올리고, 작을때는 최댓값을 내려서 탐색한다. 이때 합도 이분탐색으로 찾는데 처음에 누적합을 구하고, 처음으로 목표값 보다 커지는 인덱스를 찾으면 해당 구간에서의 합을 쉽게 구할수 있다...

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 손 풀 겸 푼 문제. 백트래킹을 사용해서 모든 조합을 만들어내면 된다. 조건이 별로 걸지 않아서 dfs와 차이가 없다. visit = None numbers = None ans = None def backtrack(ind, limit, total, prev): global visit, numbers, ans if ind == limit: ans = max(ans, total) return for i in ran..

https://www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 모든 값을 탐색하면서 이전보다 큰 값인 경우에만 백트래킹하는 방법으로 풀었다. desc_nums = [] visit = [False for _ in range(10)] def make_number(visit): ret = 0 for i in range(9, -1, -1): if visit[i]: ret = ret * 10 + i return ret def backtrack(ind=-..