분류 전체보기

문제알고리즘백트래킹으로 해결하는 문제이다. 꽃잎이 화단을 넘어간다면 꽃이 죽게되므로 씨앗을 심을수 있는 범위는 화단의 가장자리를 제외하고 계산하면 된다.꽃을 3개를 심으면 재귀가 종료되도록 하고, 다른 경우는 화단의 가장자리를 제외한 경우를 모두 탐색하면서 씨앗을 심고 dx,dy를 통해 꽃잎을 검사하는데, 이때 방문했다( 해당 자리에 미리 심은 씨앗이 있거나 꽃잎이 있는 경우)면 break를 통해 dx,dy반복문을 종료한다. 이때 방문하지 않았다(해당 자리에 미리 심은 씨앗이 없거나 꽃잎이 없는 경우)면 cost를 더해주고 다시 재귀를 반복한다.코드import sysinput = sys.stdin.readlinen = int(input())arr = [list(map(int, input().split()..
문제 https://www.acmicpc.net/problem/18111팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.좌표 (i, j..
문제명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다.조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다.그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다.M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라.단, 막대 과자는 길이와 상관없이 여러 조각으로 나눠질 수 있지만, 과자를 하나로 합칠 수는 없다. 단, 막대 과자의 길이는 양의 정수여야 한다.입력첫째 줄에 조카의 수 M (1 ≤ M ≤ 1,000,000), 과자의 수 N (1 ≤ N..
문제풀이정렬 후 투 포인터 사용 등의 간단한 O(nlgn) 풀이들도 존재한다. (STL은 사기이다!)필자는 O(n)풀이로, 들어오는 숫자를 인덱스로 배열을 증가시키고, 배열에 짝이 맞으면 cnt를 증가시키는 식으로 구현하였다.코드#include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int cnt = 0, n, x, arr[1000010]; fill(arr, arr + 1000010, 0); cin >> n; while (n--) { cin >> x; arr[x]++; } cin >> x; for (int i = 1; i ..
1935번: 후위 표기식2 from collections import dequedef main(): n = int(input()) arr = deque(input()) dict = [] for _ in range(n): dict.append(int(input())) xrr = deque() while arr: if len(arr)==1: # print(float(xrr[0])) print("{:.2f}".format(xrr[0])) break x = arr.popleft() # print(x) if ord(x) >= 65 and ord(x) ..
문제https://www.acmicpc.net/problem/7662 풀이1. 단순히 deque과 sort(O(N * log N))를 이용하여 이중 우선순위 큐를 모사할 시 시간 초과 발생2. heapq는 O(logN)으로 시간 초과 발생 X, 하지만 최대 힙, 최소 힙을 유지하면서 max, min 제거와 동기화를 같이 해줘야 함.3. default dict 사용 - I로 들어온 val에 대해 관리. D로 삭제 시 반영. >> 최대 힙, 최소 힙 동기화 - idx로 구분하여 관리하기에 중복 값에 대한 관리 가능.from heapq import heappush, heappopfrom collections import defaultdictinput = __import__('sys').stdin.re..
https://www.acmicpc.net/problem/11279문제널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.배열에 자연수 x를 넣는다.배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.프로그램은 처음에 비어있는 배열에서 시작하게 된다.입력첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.출력입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열..
문제N×N의 표에 수 N2개 채워져 있다. 채워진 수에는 한 가지 특징이 있는데, 모든 수는 자신의 한 칸 위에 있는 수보다 크다는 것이다. N=5일 때의 예를 보자.127915513811196211026311648142835255220324149이러한 표가 주어졌을 때, N번째 큰 수를 찾는 프로그램을 작성하시오. 표에 채워진 수는 모두 다르다.입력첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.출력첫째 줄에 N번째 큰 수를 출력한다.코드import heapqN = int(input())heap = []for _ in range(N): row = list(map(i..
https://www.acmicpc.net/problem/4435문제중간계에 전쟁이 일어나려고 한다. 간달프는 사우론에 대항하기 위한 군대를 소집했고, 여러 종족이 이 군대에 가담했다. 전쟁을 시작하기 전에 간달프는 각 종족에 점수를 매겼다.간달프의 군대의 각 종족의 점수는 다음과 같다.호빗 - 1인간 - 2엘프 - 3드워프 - 3독수리 - 4마법사 - 10사우론의 군대의 점수는 다음과 같다.오크 - 1인간 - 2워그(늑대) - 2고블린 - 2우럭하이 - 3트롤 - 5마법사 - 10중간계는 매우 신비한 곳이어서 각 전투의 승리는 날씨, 장소, 용맹에 영향을 받지 않는다. 전투에 참여한 각 종족의 점수를 합한 뒤, 큰 쪽이 이긴다.전투에 참여한 종족의 수가 주어졌을 때, 어느 쪽이 이기는지 구하는 프로그램..
https://www.acmicpc.net/problem/10799문제여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저의 배치는 다음 조건을 만족한다.쇠막대기는 자신보다 긴 쇠막대기 위에만 놓일 수 있다. - 쇠막대기를 다른 쇠막대기 위에 놓는 경우 완전히 포함되도록 놓되, 끝점은 겹치지 않도록 놓는다.각 쇠막대기를 자르는 레이저는 적어도 하나 존재한다.레이저는 어떤 쇠막대기의 양 끝점과도 겹치지 않는다.아래 그림은 위 조건을 만족하는 예를 보여준다. 수평으로 그려진 굵은 실선은 쇠막대기이고, 점은 레이저의 위치, 수직으로 그려진 점선 화살표는 레이저의 발사 방향이다.이러한..
문제https://www.acmicpc.net/problem/33848 Algorithm해당 스택의 3번 쿼리, 3 j: 최근 j개의 1번 또는 2번 쿼리를 취소한다. 취소할 수 있는 1번 또는 2번 쿼리가 j개 이상인 경우에만 주어진다. 를 수행하기 위해 이전 쿼리의 작동을 기억해야 할 필요가 있다.그렇기에 메인 스택, 임시 스택을 두어 메인 스택에는 위의 쿼리를 진행한다. 임시 스택에는 1번 쿼리 수행시 0을 집어넣고, 2번 쿼리 수행시 메인 스택에서 제거된 수를 집어 넣는다.이후에 3번 쿼리가 들어오면 j번 만큼 임시 스택에서 pop연산을 진행하여 값이 0이면 메인 스택에서 제거, 값이 0이 아니면 해당 수를 메인 스택에 집어넣는 연산을 해주면 된다. Codeimport sysinput = sys..
문제 https://www.acmicpc.net/problem/1700 문제기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면,키보드헤어드라이기핸드폰 충전기디지털 카메라 충전기키보드헤어드라이기키보드, 헤어드라이기,..
KauKoala
'분류 전체보기' 카테고리의 글 목록 (4 Page)