Programming

[C++] 7569번: 토마토

https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 풀이 7576번도 토마토였는데 또 토마토다! 실제로 idea도 7576번의 토마토를 그대로 따른다. 차이는 오로지 2차원이냐 3차원이냐다. 여기서 또 다른 utility인 tuple을 사용할 수 있다. 2차원 -> pair / 3차원 이상 -> tuple (pair과 utility는 STL 같지만 utility 라이브러리에 저장되어 있다.) https://modoocode...

[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차원 배열 ..

[JS] 콜백함수 설명(사용법이 아닌, definition 탐구)

Nodejs를 공부하다가 콜백함수에 대해 찾아보았다. 사용법이 아닌 콜백함수 자체에 대해 명료하게 설명한 댓글이 있어 필사한다. 함수를 호출할 때 call이라는 표현을 씁니다. (전화를 거는 것과 같은 의미로 씁니다.) 이건 흐름제어에 대한 주도권과도 관계가 있는데요. 개발자가 주도권을 잡고 필요한 함수를 호출하는게 일반적인 개발의 흐름입니다. 제공되는 라이브러리 함수 등은 모두 주도권을 가진 개발자가 직접적으로 호출해야 하죠. 이건 내가 (주도권을 가진 사람을 A라고 명명) 전화를 걸어야만 전화 받는 사람(B라고 명명하자)이 전화를 받고 무엇인가를 행하는 것과 같은 개념입니다. 이 때 전화를 받은 B가 A가 요청한 일을 하다가 또는 다한 후에 A에게 무언가를 요구할 수 있습니다. 그런데 이 때 B가 A..

[C++] 1926번 : 그림

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

[C++] 5430번 : AC

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net 풀이 결론부터 말하자면 문자열 파싱 부분에서 막혔다. 그리고 코드가 더럽다. 골드 문제는 정말 쉽지 않구나를 느꼈다. 우선 어째서 덱인가? vector로 접근하고 R에서 reverse method를 사용하고 push까지 사용하게 된다면.. 심상치 않은 주어진 범위에 시간초과가 날 것이라고 생각하였다. 문제에서 요구하는 'push'와 '역으로접근하기'는 deque 자료구조가 가장 효율적으로 수행할 수 있었다. R과 D의 구현에 있어서는 Toggle ide..

[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 ..