문제https://codeforces.com/contest/1968/problem/D난이도백준기준 G5~G3쯤 될 것 같다.알고리즘 분류DFS, 게임이론, 수학풀이코포 치면서 이 문제 되게 좋았던 것 같다. 이름에서부터 게임이 들어가있듯이 게임이론에 대한 최소한의 이해를 하고 있으면 조금 도움이 된다. 일단 알고 들어가야 하는 것은 양쪽 플레이어는 항상 최선을 다해서, 최대의 점수를 얻기 위해 노력을 하고 이 문제에서 양쪽 플레이어는 서로에게 영향을 주지는 못한다. 따라서 각각 얻을 수 있는 최대 점수를 구해주면 된다.점수는 1초 마다 현재 플레이어의 idx에 해당하는 score의 점수를 얻는다. 그리고 플레이어는 idx와 순열에 따라 이동을 하거나 하지 않을 수 있다. 문제에서 플레이어의 맨 처음 위치..
분류 전체보기
내리막 길!https://d2gd6pc034wcta.cloudfront.net/tier/13.svg시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초128 MB84978242651742928.392%문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.https://upload.acmicpc.net/0e11f3db-35d2-4b01-9aa0-9a39252f05be/-/preview/현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다...
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 문제 분석 분류 자료구조 스택 문제 설명 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성..
문제 https://www.acmicpc.net/problem/17198 Algorithm R인 지점에 유의하여 B부터 L까지의 거리를 저장하는 visited 배열을 선언한 뒤 BFS를 수행한다. B인 지점을 1로 초기화하는 것과 L로 이동하는 거리는 카운트하지 않으므로, 답안 출력 시 -2 연산에 유의한다. Code #include #include #include #include using namespace std; #define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0); typedef long long ll; typedef pair pii; typedef pair pll; char graph[11][11]; int visited[11][11]; pi..
https://www.acmicpc.net/problem/1181 1181번: 단어 정렬 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. www.acmicpc.net 문제 분석 분류 문자열 정렬 문제 설명 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 길이가 짧은 것부터 길이가 같으면 사전 순으로 단, 중복된 단어는 하나만 남기고 제거해야 한다. 입력 첫째 줄에 단어의 개수 N이 주어진다. (1 ≤ N ≤ 20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 ..
문제 링크 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 방법 문제 자체는 간단합니다. 1231234 에서 3개의 숫자를 뺀 가장 큰 숫자가 3234라는 것을 사람은 쉽게 생각할 수 있을 것입니다. 숫자 지우는 과정을 단계별로 살펴보겠습니다. 1231234에서 숫자를 하나빼서 만들 수 있는 가장 큰 숫자는 가장 앞의 1을 뺀 231234입니다. 다른 어느 위치의 숫자를 지워도 이 숫자보다 클 수 없습니다. 231234에서 숫자를 하나빼서 만들 수 있는 가장 큰 숫자는 앞선 이유와 동일하게 31234입니다. 마찬가지..
https://school.programmers.co.kr/learn/courses/30/lessons/12909 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def solution(s): li=[] for i in s: if i=='(': li.append(i) elif i ==')' and len(li)>0: li.pop() else: return False if len(li)!=0: return False return True 단순 스택 문제이다. 입력받은 s를 돌며 (면 받아주고 )일 때 스택이 안비어있다면 아직 안닫혔으므로 팝해주고 그게 아니라..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 스케쥴링 기법 중 SJF(Shortest Job First)에서 아이디어를 얻어와 문제를 해결했다. Shortest Job First란, 수행해야할 Job 중에 가장 수행 시간이 짧은 Job을 먼저 수행하여 convoy effect(https://www.geeksforgeeks.org/convoy-effect-operating-systems/)를 방지하는 스케쥴링 기법이다. 이 문제에서..
https://www.acmicpc.net/problem/10828 10828번: 스택 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 문제 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오. 명령은 총 다섯 가지이다. push X: 정수 X를 스택에 넣는 연산이다. pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다. size: 스택에 들어있는 정수의 개수를 출력한다. empty: 스택이 비어있..
https://www.acmicpc.net/problem/22252 풀이 1 정보 파는 고릴라이름 , k개 , 정보의 가치 2 정보 살 고릴라 이름 , 구매할 정보 개수 시간제한 2초 , 쿼리 최대 수 1e5 , 정보 리스트의 원소 최대 개수 1e5 , 최대 고릴라의 수 1e5 , 최대 정보를 구매 할 수 1e5 최악의 경우 : 1e5 * (파이썬 리스트 정렬 nlogn) → 시간초과 ⇒ 정렬해서 큰 값 뽑아내는거 아님 우선순위큐 힙큐 사용 1일시 hash_map에서 고릴라를 찾고 데이터를(힙큐 속성) 넣어준다 2일시 hash_map에서 고릴라를 찾고 힙큐를 꺼내서 데이터를 뽑아내고 다시 저장 나의 실수 코드 import heapq n=int(input()) hash_map={} result=0 for ..
https://www.acmicpc.net/problem/1769 1769번: 3의 배수 문제가 잘 풀리지 않을 때, 문제를 바라보는 시각을 조금만 다르게 가지면 문제가 쉽게 풀리는 경험을 종종 해 보았을 것이다. 여러 가지 방법이 있지만 그 중 하나로 우리가 풀고 싶은 문제를 www.acmicpc.net 문제 큰 자연수 X가 주어질 때, 각 자릿수의 합이 한 자리수가 될 때 까지 몇 번의 과정을 거쳤는지 출력하고, 둘째 줄에는 그 한 자리 수가 3의 배수이면 "YES", 아니면 "NO"를 출력한다. 풀이 - 큰 수는 1,000,000 자리 이하의 수임에 주의한다. -> string 이용 - cnt++를 해주며 횟수를 저장하고, s의 각 자릿수의 합을 계산한다. #include #include using..
https://www.acmicpc.net/problem/16935 16935번: 배열 돌리기 3 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → www.acmicpc.net 문제 크기가 N×M인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 총 6가지가 있다. 1번 연산은 배열을 상하 반전시키는 연산이다. 1 6 2 9 8 4 → 4 2 9 3 1 8 7 2 6 9 8 2 → 9 2 3 6 1 5 1 8 3 4 2 9 → 7 4 6 2 3 1 7 4 6 2 3 1 → 1 8 ..
