![]()
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 ..
https://www.acmicpc.net/problem/2346 2346번: 풍선 터뜨리기 1번부터 N번까지 N개의 풍선이 원형으로 놓여 있고. i번 풍선의 오른쪽에는 i+1번 풍선이 있고, 왼쪽에는 i-1번 풍선이 있다. 단, 1번 풍선의 왼쪽에 N번 풍선이 있고, N번 풍선의 오른쪽에 1번 풍선 www.acmicpc.net 요세푸스 문제 비슷한 유형이다. 원형 큐 혹은 덱을 사용해서 풀 수 있는데 나는 덱을 이용하여 풀었다. 일단 문제를 해결하기 위해서 값을 빼낼 위치 한 곳을 정해주어야 한다. 왼쪽으로 이동, 오른쪽으로 돌리는 연산은 각각 append(popleft())와 appendleft(pop())로 구현을 할 수 있다. 맨 처음 덱의 상태이다. 3 2 1 -3 -1 popleft해준 뒤 나..
![]()
https://www.acmicpc.net/problem/25603 25603번: 짱해커 이동식 첫 번째 줄에 정수 $N$, $K$가 주어진다. ($1 \le K < N \le 100\,000$) 두 번째 줄부터 $N$개의 기업 의뢰의 비용이 주어진다. 비용은 $1$ 이상 $10^9$ 이하의 정수이다. www.acmicpc.net 알고리즘 분류 자료구조 우선순위 큐 매개 변수 탐색 이분탐색 문제 짱해커 이동식은 상대방의 디스크에 자신의 이름을 남겨 자신이 왔다간 것을 알린다. 이동식에게 인정받기 위해 오늘도 수많은 기업들의 보안담당자들은 모의해킹 의뢰를 하기 위해 줄을 선다. 모든 의뢰를 받아들이기엔 너무 부담이 됐기 때문에, 각 의뢰들을 수행하는 데 필요한 비용을 측정해 최대한 비용이 적게 드는 의뢰들..
