시나위

https://www.acmicpc.net/problem/10546 10546번: 배부른 마라토너 마라토너라면 국적과 나이를 불문하고 누구나 참가하고 싶어하는 백준 마라톤 대회가 열린다. 42.195km를 달리는 이 마라톤은 모두가 참가하고 싶어했던 만큼 매년 모두가 완주해왔다. 단, 한 명 www.acmicpc.net 자기전 쉬운문제 하나 Counter를 한번 사용해보기 위해 풀어봤다. import sys; input = sys.stdin.readline from collections import Counter def main(): N = int(input()) c = Counter([input().rstrip() for _ in range(2 * N - 1)]) for k, v in c.items()..

https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net Union find 알고리즘을 사용하는 문제이다. 두 노드를 받아서 연결을 시키고, 친구가 될수 있는 최소 비용도 같이 갱신한다. 모든 노드를 받은 후 전체적으로 각 노드의 root값을 한번 더 갱신하고, 각 트리의 루트 비용를 더하면 된다. # import sys; input = sys.stdin.readline from collections imp..

https://www.acmicpc.net/problem/19622 19622번: 회의실 배정 3 서준이는 아빠로부터 N개의 회의와 하나의 회의실을 선물로 받았다. 각 회의는 시작 시간, 끝나는 시간, 회의 인원이 주어지고 한 회의실에서 동시에 두 개 이상의 회의가 진행될 수 없다. 단, www.acmicpc.net DP 문제이다. #include using namespace std; #define max(x, y) (x > y) ? x : y int main(){ cin.tie(0); ios::sync_with_stdio(0); int N, i, s, e, m; int memo[100000]; cin >> N; for (i = 0; i > s >> e >> m; if (i ..

https://www.acmicpc.net/problem/9081 9081번: 단어 맞추기 입력의 첫 줄에는 테스트 케이스의 개수 T (1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스는 하나의 단어가 한 줄로 주어진다. 단어는 알파벳 A~Z 대문자로만 이루어지며 항상 공백이 없는 연속된 알 www.acmicpc.net 뒤에서부터 바꿀수 있는 값을 탐색하고, 값이 정해지면 교환한 다음 그 이후 값들을 정렬하면된다. import sys; input = sys.stdin.readline def find_answer(word_list): ret = ''.join(word_list) for i in range(len(word_list) - 2, -1, -1): # 맨 뒤는 제거 # 문자간 distance가 가..

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://programmers.co.kr/learn/courses/30/lessons/92342 코딩테스트 연습 - 양궁대회 문제 설명 카카오배 양궁대회가 열렸습니다. 라이언은 저번 카카오배 양궁대회 우승자이고 이번 대회에도 결승전까지 올라왔습니다. 결승전 상대는 어피치입니다. 카카오배 양궁대회 운영위원 programmers.co.kr 처음부터 N이 10 이라 백트래킹으로 완전 탐색을 하면 되는줄 알았다. 하지만 구현을 못해서 세시간씩이나 날려먹었다. 맞왜틀... 다시 처음부터 짜서 다행히 통과했다. 주석으로 남겨두었으니 설명은 하지 않겠다. def answer_change(before, after): for i in range(11 - 1, -1, -1): if before[i] == after[..

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..