DevKim

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net [ 알고리즘 ] DP [ 문제 접근 ] ▶ 완전탐색의 구조인데? 경우의 수가 너무 큰데? 메모이제이션 가능하다 ! 매번 최대를 구해야하는 겹치는 부분문제 = DP 01. 입력 7 ->tri[0][0] 3 8 -> tri[1][0], tri[1][1] 8 1 0 -> tri[2][0] ,tri[2][1],tri[2][2] 2 7 4 4 ... 4 5 2 6 5 ... 02. 상태값 n행의 m열 -> dp[n][m] 03. 조건 1. tri[n][m] 이 해당 줄의 시작일..

https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net [ 자료구조 ] 스택 [ 접근 방법 ] 나와야하는 target 숫자까지 모두 스택에 push해주고 target 숫자를 pop하여 꺼내준다. 만약 현재 target의 숫자가 이 전의 target 보다 작은 경우, 한번 pop해주었을 때 해당 값이 나오면 계속 진행하고 그렇지 않으면 불가능한 경우이므로 NO를 출력하고 ..

https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net [ 자료구조 ] 스택 [ 접근 방법 ] 완전 탐색으로 구현하면 시간초과나는 문제이다. 처음에 완전 탐색으로 접근해서, 뒤에부터 앞에를 하나씩 탐색하니 시간초과가 발생하였다. 해결한 방법은, 스택을 이용하여 맨 앞부터 그 전에 스택이 담긴 원소들과 비교를한다. (1) 스택이 비어있는 경우 = 수신 받을 탑이 없다는것 (자신보다 높은 탑이 없다는 것) (2) 스택이 비어있지 않은 경우 현재의 높이와..

www.acmicpc.net/problem/14503 14503번: 로봇 청소기 로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오. 로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어 www.acmicpc.net [ 알고리즘 ] BFS,구현 [문제 접근] 이 문제는 방향에 대한 규칙만 찾으면 해결할 수 있는 문제이다 동,서,남,북을 편하게 오른쪽,왼쪽,아래쪽,위쪽이라고 했을 때, - 문제에 주어진 방향 0: 위쪽 1: 오른쪽 2: 아래쪽 3: 왼쪽 1. 가는 방향을 기준으로 무조건 왼쪽으로 회전임을 주의 - 위쪽을 바라보고 있는 경우 : 왼쪽으로 이동 - 아래쪽을 바라보고 있는 경우 : 오른쪽으로..

www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 정답률이 낮은 문제!!!! 왜냐고!!!! 왜긴왜야.. 또 시간초과지 뭐.. ㅎ ㅎ ㅎ ㅎ 에라토스테네의 체를 이용하였는데도 시간 초과가 발생했다. 그 문제를 살펴보니 #시간 초과의 이유 #1.에라토스테네스의 체를 이용하여 홀수인 소수를 구하는 과정에서 n이 입력될때마다 에라토스 함수를 돌림 #2.함수 내에서 홀수인 소수를 저장하는 리스트를 따로 생성함 #3.처음에 a 인 부분을 구하면 그..

www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제 이름을 보면 알겠지만.. 같은 문제가 메모리와 시간초과 제한만 다르게 출제되어있다. 1과 2는 sorted 내장 함수와 다른 정렬 알고리즘을 이용하여 쉽게 풀었지만, 이번 문제는 시간제한과 메모리 제한이 다음과 같다. 3 초 (하단 참고) 8 MB (하단 참고) 입력개수 N(1 ≤ N ≤ 10,000,000)로 주어져있고, 입력 수는 10,000보다 작거나 같은 자연수인 것에 비해 메모리 제한이 너무 작아서 4번이나 메..

www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 처음부터 반례까지 모두 찾아내고, 한번에 '성공!'을 받아내는걸 목표로 하고 있는 요즘. 문제 완벽하게 이해하고 반례를 찾아내는게 키포인트다. 꼼꼼하게 집중해서.! DFS로 한번에 해결~ from collections import deque que=deque() dx=[-1,1,0,0] dy=[0,0,-1,1] result=[] t=int(input()) for i in range(t): #테스트 케이스 cnt=0 #배추 ..

www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 정답률이 44%인걸보니 쉬운 문제이구나 생각했다. 토마토 문제를 풀고 푸니 너무 쉬웠다.! 10분만에 풀었다 n=int(input()) m=int(input()) graph={i:[] for i in range(1,n+1)} for i in range(m): x,y=map(int,input().split()) graph[x].append(y) graph[y].append(x) for key in graph: grap..