 사과개발자의 일상

문제 코딩테스트 연습 - 땅따먹기 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟 programmers.co.kr 풀이과정 연속으로 놓여있는 수는 지날수 없기 때문에 하나의 행에서 선택할 수 있는 수는 가장 큰 수, 두번째로 큰 수로 두가지밖에 없습니다. 그렇게 때문에 아래와 같은 방식으로 최댓값을 구할 수 있습니다. 1. 행에서 가장 큰수 maxNum, 두번째로 큰 수 secondMaxNum 를 구합니다. 2. n-1 행의 maxNum 의 인덱스를 maxIdx, secondMaxNum 의 인덱스를 secondMaxIdx 라고 할때, n행에서 max..

문제 0) queryScore = int(tempArr[-1]) 해당 key 가 딕셔너리에 값이 있는지, 있다면 query 에 있는 점수보다 크거나 같은 점수는 몇개가 있는지 계산하기만 하면 됩니다. 하지만 만약 하나의 쿼리에 속한 점수들의 배열이 너무 길어서 검색하는 시간이 길어져 시간초과 날수도 있습니다. 이를 해결하기위해 이분탐색을 사용할 예정이므로 미리 value 들을 정렬해둡니다. for key in infoDict.keys(): infoDict[key].sort() 그리고 lower_bound 를 계산해주는 bisect_left 를 통해 query 내의 점수보다 점수가 높은 개수를 계산하여 출력하면 됩니다. answer = [] for x in query: tempArr = list(y for..

문제 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이과정 아래의 예시로 설명을 해보겠습니다. 1 10 8 17 0 0 1 0 1 1 4 2 4 3 4 5 2 4 3 4 7 4 8 4 9 4 7 5 8 5 9 5 7 6 8 6 9 6 위의 경우를 arr 에 저장해보면 아래와 같은 결과가 나옵니다. (0은 생략) 한마리의 지렁이가 서로 붙어있는 배추들을 보호할 수 있기 때문에 아래와 같이 5마리의 지렁이로 모든 배추를 보호 할 수 있습니다. 아래의 코드로 보호되지 못한 배추의 위치를 찾고 def getPosition(N..

문제 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 풀이과정 처음에는 완전탐색으로 풀었더니 시간초과가 발생했다. N = int(input()) arr = list(map(int, input().split())) answer = [] for i in range(N): answer.append(0) for j in range(i-1, -1, -1): if arr[i] < arr[j]: answer[-1] = j+1 break for a in answer: print(a, end=" ") < Stack을 사용한..

문제 cacheSize: cache.pop(0) answer += 5 return answer

안녕하세요! daily_D 입니다! 👩🏻‍💻 오늘은 페이지 교체 알고리즘 중에서 LRU에 대해서 공부해볼까요?! LRU 란? LRU(Least Recently Used)는 가장 오랫동안 참조되지 않은 페이지를 교체하는 방식입니다. LRU 는 사용된지 가장 오래된 페이지는 앞으로도 사용될 확률이 낮다는 가설에 의해 만들어진 알고리즘입니다. LRU 의 원리 LRU 를 구현하기 위해서는 캐시가 가득 찼을때, 가장 오랫동안 참조되지 않은 페이지를 찾아서 없애는 과정이 필요합니다. 페이지를 새로 참조할 때마다 연결리스트의 맨 앞에 페이지번호를 추가합니다. 그러면 맨 뒤에 있는 페이지번호가 가장 오랫동안 참조되지 않은 페이지번호가 되겠죠? 따라서 LRU의 원리는 캐시의 크기가 3인데 이미 3개의 페이지가 캐시에 들..

안녕하세요! daily_D 입니다! 👩🏻‍💻 오늘은 Python itertools 로 순열과 조합을 이용해보는 방법과 직접 구현하는 방법에 대해 알아볼까요? ➤ 순열 ( = permutations) : n 개의 원소에서 중복을 허용하지 않고 r개를 뽑아서 나열 직접구현 def permutations(array, r): for i in range(len(array)): if r == 1: yield [array[i]] else: for next in permutations(array[:i] + array[i+1:], r-1): yield [array[i]] + next itertools 사용 from itertools import permutations for i in permutations([1, 2, ..

🍋 문제링크 https://www.acmicpc.net/problem/16918 🍎 코드 제출 기록 (메모리 및 시간) 메모리 : 196844 KB 시간 : 928 ms 🥝 메모 폭탄이 들어있는곳의 문자는 숫자 0이 아니라 대문자 알파벳 O이었다는... 🍓 문제풀이 [ 순서 정리 ] 임의의 칸에 폭탄을 설치한다. - 3초 처음 1초 동안 아무것도 하지 않는다. 다음 1초 동안 폭탄이 설치되어 있지 않은 모든 칸에 폭탄을 설치하고 폭탄의 시간이 0이 된 폭탄은 폭발한다. 3번을 반복 [ 풀이순서 ] 입력받은 map을 통해 각 폭탄의 시간을 저장하고 있는 배열을 생성한다. → 처음에 들어있는 폭탄의 시간은 2로 입력 (처음 1초는 아무일도 하지 않기 때문에) N-1 초동안 아래의 과정을 반복 (처음 1초는 ..

안녕하세요! daily_D 입니다! 👩🏻‍💻 오늘은 Python 으로 문제풀이할 때 시간초과가 나는 경우 해결할 수 있는 몇가지 방법을 알려드릴까합니다! 1. sys.stdin.readline()로 입력받기 입력값을 받아 저장해하는 경우 input() 으로 구현하시는 분들이 많으실텐데 sys 라는 파이썬의 표준 라이브러리를 사용하면 훨씬 빠른 시간에 적은 메모리를 사용하여 입력 받을 수 있답니다! import sys 변수 = sys.stdin.readline() 2. 배열에 원소 추가할 때 인덱스로 접근하기 배열에 원소를 추가하면 보통 빈 배열을 만들고 append 로 추가할 때가 많은데, 이 경우 입력 받을 개수(N)를 알고있다면 N 만큼 배열을 초기화해두고 인덱스로 각자 접근해서 저장하는 것이 효율이..

🍋 문제링크 https://www.acmicpc.net/problem/17086 🍎 코드 제출 기록 (메모리 및 시간) 메모리 : 135476 KB 시간 : 1008 ms 🥝 메모 nx = x + dx[i] *1, ny = y + dy[i] *1nx = x + dx[i] *2, ny = y + dy[i] *2 이런 식으로 완전탐색을 수행하면 아래의 그림과 같이 ✔️ 부분이 확인되지 않기때문에 틀림! nx = x + dx[i] *2, ny = y + dy[i] *2 🍉 Code import copy N, M = map(int, input().split()) shark = [] for i in range(N): shark.append(list(map(int, input().split()))) dx = [-1..