시나위

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 시뮬레이션 문제이다. 드래곤 커브를 만들면서 구해지는 꼭짓점을 모두 찾으면 되는 문제인데 이게 조금 복잡했다. 드래곤 커브를 만들때 다음과 같은 순서로 꼭짓점을 구했다. 1. 0세대 드래곤 커브를 구하고 현재 위치를 드래곤 커브의 마지막 점으로 설정한다. 2. 현재까지의 드래곤 커브로 다음 세대를 구한다. 1) 마지막 꼭짓점부터 역방향 순회하고, 드래곤 커브의 꼭짓점 차..

https://programmers.co.kr/learn/courses/30/lessons/81302 코딩테스트 연습 - 거리두기 확인하기 [["POOOP", "OXXOX", "OPXPX", "OOXOX", "POXXP"], ["POOPX", "OXPXP", "PXXXO", "OXXXO", "OOOPP"], ["PXOPX", "OXOXP", "OXPOX", "OXXOP", "PXPOX"], ["OOOXX", "XOOOX", "OOOXX", "OXOOX", "OOOOO"], ["PXPXP", "XPXPX", "PXPXP", "XPXPX", "PXPXP"]] [1, 0, 1, 1, 1] programmers.co.kr 시뮬레이션 문제이다. 구현만 하면 된다. def check_partition(a, b, _..

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

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/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 시뮬레이션을 요구하는 삼성 느낌의 기출이다. 주어진 조건대로 만들어주기만하면 되는데 그게 너무 오래걸리는 문제여서 구현이 오래걸렸다. 완전탐색으로 맵에 그렸다가 지웠다를 반복하면 값이 나온다. import sys; input = sys.stdin.readline answer = None N, M = None, None cctv_list, d_map, r_map = None, None, ..

https://www.acmicpc.net/problem/11811 11811번: 데스스타 젊은 제다이 이반의 임무는 데스스타에 침투하여 파괴하는 일이다. 데스스타를 파괴하기 위해서는 길이 N의 음이 아닌 정수 수열 ai가 필요하다. 그러나 이반은 이 수열을 가지고 있지 않다. 대 www.acmicpc.net 손 푸는 문제 n_ij는 a_i와 a_j가 겹치는 비트를 보여주므로 bitwise 연산자 or로 모두 합치면 쉽게 풀수 있다. import sys; input = sys.stdin.readline def main(): N = int(input()) ans = [0 for _ in range(N)] for i in range(N): for nij in map(int, input().split()): ..