조용하지않는개발Blog

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제 자체는 어렵지 않은 문제였습니다. 처음에 보고 그래프로 푸는 문제인가?! 하고 생각했는데 보니까 최소값인 치킨집을 선택하고 집에서 거리를 계산하여 최소가 되는 길이를 찾는 형식의 문제였습니다. 또한 n,m의 최대가 50, 13 이여서 반복이 조금 들어가도 시간 초과는 안나겠다는 생각을 가지고 편하게 풀었습니다. 먼저 그래프에서 치킨집과..

https://programmers.co.kr/learn/courses/30/lessons/42889 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 문제 설명 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스테이지 차이가 너무 큰 것이 문제였다. 이 문제를 어떻게 할까 고민 한 그녀는 동적으로 게임 시간을 늘려서 난이도를 조절하기로 했다. 역시 슈퍼 개발자라 대부분의 로직..

https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 문제 설명 이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다. 명령어 수신 탑(높이) I 숫자 큐에 주어진 숫자를 삽입합니다. D 1 큐에서 최댓값을 삭제합니다. D -1 큐에서 최솟값을 삭제합니다. 이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요. 제한사항 operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다. operations의..

https://www.acmicpc.net/problem/5525 5525번: IOIOI N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다. P1 IOI P2 IOIOI P3 IOIOIOI PN IOIOI...OI (O가 N개) I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 첫번째부터 IOI가 나오는지 비교하면서 있다면 IO만큼 2칸씩 이동한다. 그리고나서 다시 IOI가 나오는지 비교하면서 그때 n의 개수와 IOI 나온 개수가 일치하면 결과값으로 1개씩 추가하고 IOI나왔던 개수를 1개 빼주는 형식으로 진행한다. IOI가 아니면 다시 초기화 해주는 느낌으로 문제를 ..

https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 딕션너리를 이용하여 찾는 문제이다. 리스트를 이용하여 저장하고 찾게 된다면 2중 for문을 통해 찾아야 하기에 많은 시간이 소모 된다.시간 초과가 나올 가능성이 높음. 하지만 딕션너리를 사용하면 O(n)이기 때문에 빠르게 문제를 풀 수 있다. import sys input= sys.stdin.readline n,m= map(int,..

https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 전체적으로 읽고 예제 입력, 출력을 보고 이해하고 풀 수 있었던 문제이다. 단순하게 푼다면 정렬을 하면서 풀수있겠지만, 그렇게 푼다면 정렬할때마다 시간이 소요되기에 시간초과가 나올것이다. 그렇기에 값을 넣거나 뺄때 바로 정렬이 되는 heap을 사용하면 해결할수 있는 문제이다. 여기서 약간 문제를 꼬았는데 바로 절대값을 넣어서 조금 어..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 처음에 문제를 보고 단순하게 큰 값부터 계산하고 주변을 0으로 두면서 풀면 될까? 라는 생각을 가졌지만 여러 계산을 해보니 그렇게 풀면 발생하는 오류들이 많이 있어서 이것은 dp로 풀어야하는 문제라는 것을 파악하였다. 두개의 스티커를 1부터 차례대로 계산을 하면서 증가시키면 되는 문제였다. 1 2 3 4 5 1 50 30+10=40 max(30,100..

https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 이 문제는 정해진 숫자를 차례대로 출력 될수있게 하면 되는 문제이다. 백트래킹과 dfs를 이용해서 풀면 쉽게 풀린다. 또한 그냥 itertools의 permutations을 통해 풀면 간단하게 풀수있다. # dfs와 백트래킹 import sys input= sys.stdin.readline def dfs(x,y): if m==y: print(*x) el..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 처음에 문제를 잘못 이해해서 고생했지만 위 4개를 이어붙인 모습으로 최대가 되는 값을 찾는 문제였다. 백트래킹을 활용하면 문제를 풀 수 있지만. 문제가 되는 부분인 ㅗ,ㅜ,ㅓ,ㅏ 이 모양을 어떻게 만드느냐가 중요한 사항이다. 처음에는 4가지를 코드로 구현해서 결과를 출력해보았다. import sys dx = [0,0,1,-1] dy = [1,-1,0,0] inp..

https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 풀이 문제를 보았을때 알수있는 힌트 문제를 보고 간단하게 푸는 방법으로는 조합을 출력되게하면 끝이 나겠구나? 생각이 들었다. 파이썬에는 itertools의 combinations 가 존재하기에 이것을 이용하면 엄청 쉽게 풀 수 있다. import sys from itertools import combinations input= sys.stdin.readline n,m = map(int,input..