![]()
문제 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 너비 우선 탐색을 이용하여 구현한다. 최소 날짜를 저장할 cnt, 안 익은 토마토 수를 저장할 zero, 익은 토마토의 위치를 저장할 q를 정의한다. 이중 반복문을 통해 익은 토마토라면 q에 append 하고, 안 익은 토마토의 개수를 확인한다. 만약 안 익은 토마토가 없다면 0을 출력한다. 만약 안 익은 토마토가 있다면 dfs를 수행한다. - q가 빌 때까지 반복한다...
문제 https://www.acmicpc.net/problem/2161 2161번: 카드1 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 코드 #include #include #include #include #include using namespace std; int main() { deque dq; deque dqw; int n = 0; cin >> n; for (int i = 0; i 2) { int f = 0; while (dq.size() != 2) { dqw.push_back(dq.front()); dq.pop_fro..
![]()
https://www.acmicpc.net/problem/11559 11559번: Puyo Puyo 총 12개의 줄에 필드의 정보가 주어지며, 각 줄에는 6개의 문자가 있다. 이때 .은 빈공간이고 .이 아닌것은 각각의 색깔의 뿌요를 나타낸다. R은 빨강, G는 초록, B는 파랑, P는 보라, Y는 노랑이다. www.acmicpc.net 알고리즘 분류 구현 그래프 이론 그래프 탐색 시뮬레이션 너비 우선 탐색 문제 뿌요뿌요의 룰은 다음과 같다. 필드에 여러 가지 색깔의 뿌요를 놓는다. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어진다. 뿌요를 놓고 난 후, 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어진다. 이때 1연쇄가 시작된..
![]()
1012번: 유기농 배추 (acmicpc.net) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 코드 import sys input = sys.stdin.readline dx= [0,0,1,-1] dy= [1,-1,0,0] t = int(input()) for _ in range(t): m,n,k=map(int,input().split()) #가로세로 배추개수 qocn=[[0]*(m+2) for i in range(n+2)] #배추밭배추위치 visitdi = {} #전체적으로이미방문했나 ans=0 for i in ran..
![]()
문제 설명 미로를 탈출하는 최단 거리를 구하는 문제이다. 최단 거리를 구해야 하기에 깊이 우선 탐색이 아닌 너비 우선 탐색을 사용하였고, 입력이 붙어서 들어오기에 먼저 string으로 받고 인덱스 하나 하나 집어 넣어주었다. bfs를 도는 중에는 상하좌우를 검사하여 인덱스를 벗어나지 않고/방문하지 않았고/이동할 수 있는 위치일 때 큐에 삽입하였다. 그리고 처음 알았는데 queue.push 대신 queue.emplace를 쓰면 속도도 더 빠르고 pair같은 구조체를 make_pair를 사용하지 않고 바로 집어 넣을 수 있어 편했다. 최단 거리를 구하는게 조금 어려웠는데, 그냥 2차원 배열을 새로 만들어서 기록해주는게 제일 편한듯 했다. 코드 #include using namespace std; int N,..
![]()
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 문제 코드 import sys input = sys.stdin.readline n = int(input()) check = list() y = 1 count = list() flag = 0 for _ in range(n): num = int(input()) while y
![]()
문제 https://www.acmicpc.net/problem/1918 풀이 중위표기식에서 후위표기식으로 변환하는 것은 스택을 활용하여 풀 수 있다. 후위표기식의 방식에 따라, 계산할 문자를 먼저 문자열에 두고 기호는 스택에 넣어두었다가 출력하면 된다. 하지만, 연산자의 우선순위에 의해 추가적으로 고려해주어야 한다. 우선순위가 더 낮은 연산자가 나오면 더 높은 연산자를 먼저 처리해준다. 또한, 괄호가 나오는 경우 괄호가 닫히는 순간에 괄호가 시작되었던 부분까지 고려하여 변환하면 된다. 코드 formula = input() precedence = {'+': 1, '-': 1, '*': 2, '/': 2} stack = [] postfix = '' for c in formula: if c.isalpha():..
https://www.acmicpc.net/problem/1874 문제 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성을 가지고 있다. 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 이때, 스택에 push하는 순서는 반드시 오름차순을 지키도록 한다고 하자. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop 연산을 수행해야 하는지를 알아낼 수 있다. 이를 계산하는 프로그램을 ..
0. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 문제 풀이 트럭이 다리에 올랐다가 다시 내려오는 과정에서 stack 자료 구조를 떠올렸지만 stack 자료 구조 자체에 (트럭, 상태) 값을 들여보내는 로직으로 한참 생각하다가 아이디어는 결국 인터넷에서 빌리고 만 문제였다 ㅠ.. 0과 트럭 무게를 이용하여 다리 위의 실제 트럭 상태를 저장하며 푸는 아이디어가 매우 중요하다 ! 2. 코드 아래는 시간초과 코드이다. from coll..
![]()
문제 https://www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L ≤ 1,000,000) 강산이가 백스페이스를 입 www.acmicpc.net 풀이 커서를 기준으로 왼쪽, 오른쪽을 나누어 저장하기 위해 deque를 생성한다. (왼쪽 deque | 오른쪽 deque) 입력받은 문자열을 for문으로 하나씩 확인한다. - 왼쪽 deque이 비어있지 않고, '-'라면 왼쪽 deque를 pop 한다. - 왼쪽 deque이 비어있지 않고, ''라면 오른쪽 deque에서 popleft 한 값을 왼쪽 deque에 append 한다. - 위..
![]()
문제 해설 절대값 힙이라는 자료구조를 우선순위 큐로 만들어 구현했습니다. c++의 우선순위 큐는 가장 큰 값이 출력이 되는데, 절댓값이 가장 작은 값을 출력해야기에 -를 붙혀 push하였습니다. 그리고 연산자 오버로딩으로 절댓값이 같을 때 더 작은 수를 출력하도록 했습니다. 코드 #include using namespace std; struct cmp { bool operator()(int a, int b) { if (abs(a) == abs(b)) return a abs(b); } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); priority_queue pq; int N; ci..
문제 https://www.acmicpc.net/problem/1614 1614번: 영식이의 손가락 1, 2, 3, 4, 5, 4, 3, 2, 1, 2, 3, 4, 5, 4, 3 위와같이 세면 총 15를 셀 수 있다. 2번째 손가락을 3번 이용했으니 더 이상 사용할 수 없다. www.acmicpc.net 코드 #include using namespace std; #define LL long long int main() { LL f = 0; LL n = 0; cin >> f; cin >> n; LL ans = 0; if (n != 0) { if (f == 1 || f == 5) { ans += n * 8; if (f == 1) { cout
