DevKim

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

올해 초에 이 문제를 푼 적이 있었는데, 이번에 다시 풀 기회가 생겨 다시 한번 풀어보았다. 01.이전에 푼 방법 --> O(N) 72ms https://yeon-woo-kim.tistory.com/83 [Python] 백준 #1158 요세푸스 문제 www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net 이거 다음 요세푸스2가 정말 문제다.. 시간초과 때문에.. yeon-woo-kim.tistory.com 02. 새로 푼 방법 --> O(N) 3996ms [ 자료구조 ] 큐 [ 접근 방법 ] que를 하나 만들어, k 전까지 pop을 해서 que의 뒤에 추..

programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr [ 알고리즘 ] 단순구현 [문제 접근] 이 문제의 관건은 나 자신을 제외한 모든 사람과의 이기고,짐의 결과를 알고 있어야된다는 것이다. 이김 =1, 짐 =-1, 알 수 없음 =0으로 나타낸 리스트를 생성시켜주고 한 명의 정보에 대해서, 만약 a가 b,c,d 에게 지고 , e에겐 이겼다면, 1 ) e는 b,c,d에게 무조건 질 것이고, 2 ) b,c,d는 무조건 e를 이길 것이라는걸 알 수 있다. 이렇게 한명씩 모두 정보를 업데이트 시켜준 후, 각 행에서 0이 하나만 포함된 행을 co..

www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net [ 알고리즘 ] 시뮬레이션 [문제 접근] 문제에 제시된대로 미세먼지 확산과, 공기청정기 작동을 구현하는 문제이다. 문제대로 구현하는건 어렵지 않았는데.. 시간초과 문제가 발생하여 애를 먹었던 문제이다. 1) 5이상인 경우에만 미세먼지가 퍼지는 조건도 추가해보았고 2) deepcopy로 기존의 graph를 저장하는 방식대신 빈 리스트에 확산되는 미세먼지의 양을 저장하여 마지막에 이중 for문으로 더해주는 방식 ..

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

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net [ 알고리즘 ] BFS, 브루트포스 [문제 접근] 브루트포스 + BFS를 이용하여 해결하는 문제이다. N과 M의 범위가 크지 않은 경우라 브루트포스 방법을 생각해내었다. 벽은 3개만 추가로 설치할 수 있으므로 벽이 설치될 수 있는 경우의 수를 구하고, 이를 Counter 을 이용하여 안전지대의 개수를 counting 한 후 Max 값만 업데이트 해주면 된다. [코드] from collections import deque f..

www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net [ 알고리즘 ] 구현 [문제 접근] 이 문제는 세가지의 경우로 나눠야한다 1. 경사가 감소하는 경우 (한칸만) --> 그 전의 경사 높이-1 = 그 다음의 경사 높이 일땐 감소하는 경사의 개수가 L 이상이 되어야함 2. 경사가 증가하는 경우 (한칸만) --> 그 전의 경사 높이+1 = 그 다음 경사 높이 일땐 증가하기 전에 까지의 높이가 연속적으로 L개 이상이 되어야함 3. 경사가 같은 경우 --> 단순 check 증가 [코드] N,..

programmers.co.kr/learn/courses/30/lessons/12907 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr [ 알고리즘 ] DP [문제 접근] 코드는 굉장히 간단하지만, 이걸 생각해내기는 정말정말 쉽지 않음이 분명하다. 점화식을 한번에 찾아내기 어려웠던 문제, 개수로 따져서 그런 것 같다 간단히 설명해보자면.. dp[0] 은 아무것도 포함하지 않을 때, 즉 자기 자신만을 이용해 만들 수 있는 경우이다. 예시의 n=5, money=[1,2,5] 로 생각해보자 초기 상태의..