파이썬

https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 문제 풀이 처음에는 리스트 한 개와 인덱스를 이용해서 커서의 위치를 구현해주려 했으나 커서를 기준으로 오른쪽과 왼쪽의 문자를 알려주는 두 개의 리스트를 사용하면 훨씬 쉽게 구현할 수 있다는 것을 알게 되었습니다. [커서 기준 왼쪽 문자들] 커서 [커서 기준 오른쪽 문자들] 이렇게 구현하면 훨씬 쉽게 구현할 수 있다. 정답을 출력할 때 오른쪽 문자들은 마지막에 한번 뒤집어줘야한다. appen..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 풀이 문제를 읽고나서 위상정렬 알고리즘임을 어렵지않게 알 수 있었다. 최소 건설 시간을 측정하기 위해 다이내믹 프로그래밍을 사용할 것이다. 건물 완성까지의 최소 시간을 구하기 위해서는 다음과 같은 말이 성립된다. - 선행 건설 되어야하는 건물이 존재한다면 후행 건설을 실시 할 수 없다. - 이를 위해서는 선행 건설 되어야하는 건물이 모두 건설되어야 한다는 얘기이다. - 선행 건설이 없는 건물..

분리 집합(Disjoint Set, Union-Find)은 많은 알고리즘 코딩 테스트에서 중요한 자료구조로 나타납니다. 분리 집합은 여러 노드가 서로 중복되지 않는 집합으로 나뉘어 있을 때, 각 집합을 대표하는 노드 하나를 선택해 그 집합을 대표하도록 구성합니다. 분리 집합의 주요한 사용 용도는 다음과 같습니다: 사이클 판별: 주로 그래프에서 사이클이 있는지 확인할 때 사용됩니다. 간선을 하나씩 추가하면서 두 노드의 루트 노드가 같다면 사이클이 생성되는 것입니다. Kruskal 알고리즘에서 최소 신장 트리를 구할 때 사이클 확인 용도로 사용됩니다. 집합의 병합 및 찾기 연산: 두 집합을 하나로 합치거나, 어떤 원소가 어떤 집합에 속하는지 찾을 때 사용됩니다. 네트워크 연결: 여러 네트워크가 연결되어 있을..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 투 포인터 알고리즘으로 문제를 풀어주었습니다. 정렬된 용액의 값들이 들어오기에 따로 정렬해줄 필요는 없습니다. 투포인터 알고리즘 https://sunghyun98.tistory.com/25 [알고리즘] 투 포인터 투 포인터 알고리즘은 배열에서 두 개의 포인터를 사용하여 특정 목표를 달성하기 위한 기법입니다. 일반적으로 정렬된 배열에서 특정 조건을 충족하는 요소를 찾거나 연속된 서브 배열..

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 풀이 기존의 dp로만 풀어주면 시간초과가 일어난다. dp풀이는 N^2의 시간 복잡도를 가지기 때문에 N의 크기가 최대 10^6이기에 1초를 넘어서는 시간초과가 일어난다. 그래서 이분탐색을 이용해서 풀어줘야하는 문제이다. DP 코드(시간초과) n = int(input()) arr = list(map(int, input().split())) dp = [1 for i in range(n)] for i ..

https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 풀이 구현문제로써 반올림을 구현하여 문제를 풀어주었습니다. 주의: round()를 쓰면 안됩니다. round()는 정확한 반올림을 해주는 함수가 아닙니다. 코드 # 18110번 solved.ac import sys def banollim(n): if n - int(n) >= 0.5: return int(n)+1 return int(n) t = int(input()) i..

https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 풀이 계획 - 가중치가 다르게 주어진 그래프 이동을 하는 문제 - 한 정점에서 다른 모든 정점으로부터의 최단거리 계산 - 다익스트라 알고리즘 적용 코드 # 13549번 숨바꼭질 3 import sys import heapq input = sys.stdin.readline INF = sys.maxsize def rangeValid(v): if 0 dist: if..

https://www.acmicpc.net/problem/1236 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 풀이 처음에는 어떻게 풀지 고민해보았는데, 문제에서 요구하는 바는 행과 열마다 경비원이 하나씩 존재해야한다는 것이다. 어느 n행과 m열이 주어졌을 때 두 직선의 교점에 경비원이 위치한다면 한 경비원으로도 문제에서 원하는 바를 만족시킬 수 있다는 것이다. 그말은 즉슨 가장 긴 직선의 길이만큼 경비원을 배치해준다면 다른 직선의 경비원 문제는 자연스럽게 해결된다는 것이다. 코드 # 1236번..