Baekjoon

[C++] 7576번 : 토마토

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀이 상하좌우만 탐색이 가능하다고 주어졌습니다. 추가로 idea 자체가 2178번과 매우 유사함이 느껴집니다. 토마토가 익어가는 상황과 distance를 구해야 하는 상황이 결국 BFS를 요함을 캐치해야합니다. 다만 2178번 문제와는 달리 출발점 1에서 동시에 탐색을 수행해야할 것만 같습니다. 코드로 동시에 구현할 수는 없음을 우리는 잘 알고 있습니다.. 출발점이라는 것을 유심히..

[C++] 2178번 : 미로탐색

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 풀이 우선 첫 번째는 입력에서 볼드체로 '붙어서'를 강조하는 모습을 볼 수 있습니다. string으로 받아야겠다는 생각은 했지만, getline으로 받을 생각이었습니다. 이후.. for(auto c : s)를 통해 접근하고자 했지만 이렇게 구현할 경우 index에 접근이 불가하여 미로의 개념이 구현되지 않습니다. 이 부분은 고민하다가 해답을 참고했습니다. string s[100] 이라 함은 string 객체를 담는 1차원 배열 ..

[C++] 1926번 : 그림

https://www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 풀이 드디어 자료구조를 넘어 Theme.BFS에 진입했다. 이산수학과 자료구조에서 지겹도록 배운 BFS,DFS인데 막상 코드로 짜려니 신경써줘야 할 것이 많았다. 이 문제는 BFS의 기본문제라고 할 수 있겠다. Flood Fill이라는 idea를 채용한다고 할 수 있겠는데 Flood Fill이란 예를 들어 그림판에서 내가 양동이 아이콘을 클릭하여 어떤 도형 안쪽을 클릭하면 가득 채워짐을 알 수 있다. ..

[C++] 1021번 : 회전하는 큐

https://www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 풀이 문제 자체는 어렵지 않으나, 어떻게 코드로 구현할 지 어려웠다. 우선 왜 덱인가? 문제에서는 왼쪽과 오른쪽을 한 칸씩 이동한다고 기술되어 있지만 이는 사실 삽입/삭제과정이 일어나고 있다. 단방향이 아닌 양방향에서 push/pop이 일어나고 있으므로 deque이 가장 효율적인 자료구조일 것이다. 가장 중요한 로직은 왼쪽으로 갈 지 오른쪽으로 갈 지 정하는 조건을 설정하는 것이었는데, 적어보..

[C++] 2164번: 카드2

https://www.acmicpc.net/problem/2164 2164번: 카드2 N장의 카드가 있다. 각각의 카드는 차례로 1부터 N까지의 번호가 붙어 있으며, 1번 카드가 제일 위에, N번 카드가 제일 아래인 상태로 순서대로 카드가 놓여 있다. 이제 다음과 같은 동작을 카드가 www.acmicpc.net 풀이 정말 쉽게 풀 수 있는 문제입니다! 주어진대로 구상해보면, 큐 자료구조가 팍!하고 떠올랐다면 코드를 기술하는 것은 어렵지 않습니다. 나의 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int N; cin >> N; queue q; for (int i = 1; i

[C++] 10845 : 큐/18258 : 큐2

https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net https://www.acmicpc.net/problem/18258 18258번: 큐 2 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 www.acmicpc.net 풀이 큐는 기본기본기본 문제라 정말 쉽게 풀 ..

[C++] 2493번 : 탑

기술하기에 앞서 정말 배운 것이 많은 문제입니다. (STL 中 Pair Class,출력초과,monotonic stack) 풀이 1874번 스택 수열을 풀어보셨다면 접근 자체는 할 수 있었을 것 같습니다. 직관적으로 생각나는 풀이는 O(N^2) 풀이입니다. 하지만 주어진 범위를 보면 당연히 안되는 것을 알 수 있습니다. 처음 짠 코드는 정말 idea 자체만 겹쳤습니다. 도대체 index를 어떻게 처리해줘야할 지 모든 경우의 수를 동원해도 안되더군요. 같이 저장할 순 없을까?라는 생각을 하고 깊게 생각해보진 못했습니다. #include //첫 코드 using namespace std; int main() { cin.tie(0);ios::sync_with_stdio(0); int N, cnt = 0; cin ..

[C++] 1874번 : 스택 수열

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 풀이 사실 1시간 동안 이 문제를 풀지 못해 결국 답을 보았습니다. 추가로, 알고리즘을 아직 찍어먹는 수준으로 밖에 하지 않았지만 '알고리즘 문제 풀이 마인드'가 궁금하여 열심히 찾아본 결과 모두 중략하여 말하자면 '1시간이나 소비하지말고 30-45분 내에 떠오르지 않으면 넘기자'입니다. 1) 문제 이해 문제 이해를..

[C++] 10773번 : 제로

https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 풀이 스택을 사용하여 정말 쉽게 풀 수 있는 문제입니다. 문제의 '가장 최근에 재민이가 쓴 수를 지우게 시킨다.' 문장에서 이를 가장 효율적으로 수행할 수 있는 자료구조로 스택을 생각할 수 있었다면 구현은 어렵지 않습니다. 내 코드 #include using namespace std; int main() { ios::sync_with_stdio(0); cin.ti..

[C++] 1406번 : 에디터

https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 vector 또는 단순 배열을 이용하여 풀어볼 수 있겠구나 라고 생각할 수 있다. 그러나 수상하게도 문제에서 주어진 시간 제한이 0.3초이다. 즉 각 명령어를 수행할 때 O(n)이 아닌 O(1)인 코드를 기술해야한다.(즉 각 명령어를 수행할 때마다 문자열 전체를 봐야하는 것은 안된다! -> vector과 배열을 사용할 시 O(mn)이 되므로 불가하다.) 그에 딱 맞는 자료구조로 Linked L..