노는 게 제일 좋아

이것도 BFS의 기본이라고 볼 수 있다. www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 이전 문제의 최단경로의 경로문제라고 해도 무방하다. 하지만 약간 꼬아놨으니 BFS의 시작점이 여러군데다. 근데 뭐 별다를 거 없다. 시작점을 큐에 다 넣고 시작하는 것과 같이 얘도 똑같이 해주면 된다. #맞는 풀이 다만 최적화는 되어있지 않은 풀이 #include #include #define X first #define Y second using nam..

이 문제도 이전 문제와 형제문제라고 할 정도로 BFS의 기본을 알려준다 [프로그래밍언어(Programming Language)/C || C++] - 백준, BOJ, 2178번 C++ [CPP] www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net 바로 이 문제가 BFS가 탐색한 노드의 수를 알려주는 것인데 뭐 메모리랑 관련이 있다고만 해두겠다. **사실 큐에 쌓이는 노드가 더 메모리랑 관련있지만..뭐 그렇다. # 맞는 풀이 #include #include using n..

경로 탐색의 핵심은 탐색 방법이다. 그 중 얘는 BFS다. www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 왜 BFS일까?는 최단경로를 찾아야하기 때문이다. DFS는 최단경로를 보장하는 방법이 아니다. 어떠한 경우에 대해서도 최단경로를 찾기 위해서는 BFS를 쓸 수 있다. 일반적으로 메모리는 DFS보다 BFS가 많이 먹을 수 있는..가능성이 높다 나는 이것을 논리가 맞다고 생각하고도 엄청 많이 틀렸다. 바로 입력에 대해서 확인을 소홀히 해서 그렇다. 이 문제에서 입력은 공백없이 주어졌다. ..

어렵지 않지만 생각을 잘해야 하는 문제 220227에 다시 풀어보니 생각이 안나는 어려운 문제.. 거의 일년만에 다시 푸네.. ㅋㅋㅋㅋㅋ 값이 확정되는 때가 언제더라 생각하고 있었다. www.acmicpc.net/problem/2504 2504번: 괄호의 값 4개의 기호 ‘(’, ‘)’, ‘[’, ‘]’를 이용해서 만들어지는 괄호열 중에서 올바른 괄호열이란 다음과 같이 정의된다. 한 쌍의 괄호로만 이루어진 ‘()’와 ‘[]’는 올바른 괄호열이다. 만일 www.acmicpc.net 괄호가 나왔으니 스택에 쌓아가면서 할 것이란 것은 예상을 했다. 하지만 또 문제였던 것이 괄호를 닫을 때 이것이 멀리 있는 괄호가 닫히는 것인지 가까이 있는 괄호가 닫히는 것인지 구분을 하지 못한다는 큰 맹점이 생긴다. EX) ..

2022.02.25 다시 풀어보았다. 21년 4월에 풀고 거의 1년만이다. 문제다. www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 물론 살펴보면서 규칙을 찾는 것은 많이 어렵지는 않았다. 스택에 쌓아가면서 생기는 쇠막대기의 개수를 테스트 케이스와 비교해보면서 규칙을 찾았다. 여기서 중요한 것은 스택만 이용하면 안된다. 스택만 이용하면 ()를 처리하는지 멀리떨어져있다가 삭제되어서 ()가 되어서 삭제되는지 알 수 없다. 때문에 나는 다른 방법을 이용했다. 문자열 자체를 ..

물론 생각은 한 번에 났으나 구현이 20분은 걸렸다. www.acmicpc.net/problem/1021 1021번: 회전하는 큐 첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 www.acmicpc.net 처음 문제보면서.. ?? 어떤 자료구조를 쓸까.. 만약 shift를 하면 앞 뒤 둘다에서 삭제 삽입이 일어나는구나. -> Deque를 쓰자. Double ended queue 왼쪽으로 미는 거랑 오른쪽으로 미는 거랑 구분을 해야겠다. **덱을 복사해서 쓰고 이동횟수가 적은 쪽을 다시 원본으로 복사해서 쓰자. -> 다른 방법이 바로 생각안나서 N도 적어서 ..

22.03.01 다시 풀어봄 모든 문제를 기록하긴 좀 그렇고 내가 이해가 한 번에 안된 것들을 다시 이해시키고자 한다. www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제를 보자. 탑을 하나씩 세운다고 생각하자. 탑을 세울 때, 내 왼쪽에 수신할 탑이 없으면 0 수신할 탑이 있으면 해당 수신 탑의 index를 출력하면 되겠다. 5개의 탑 높이를 입력받는다. 6 9 5 7 4 순서대로 탑을 세우자. 위의 방법으로 해결하기 위해서는 왼쪽에 있는 탑들에 대한 ..

이번엔 스택을 알아보자 스택은 First In Last Out으로 삽입과 삭제 연산이 동일한 장소에서 일어나는 자료구조다. 역시 삽입, 삭제 연산에 있어서 상수 시간복잡도를 가진다. FILO구조는 다시 말하면 LIFO구조다. 마지막에 들어온 것이 먼저 나온다는 이야기다. 데이터를 역으로 추적할 때와 같은 상황에 사용한다. 연결리스트와 유사한 자료구조라고도 한다. (연결리스트로 스택 구현가능) 스택 같은 경우에는 중위-후위 변환 재귀함수와 같은 함수 호출 구현 **웹브라우저의 뒤로가기 (페이지기록) 문서 어플리케이션,에디터의 Ctrl + z , undo 기능등과 같은 곳에 쓰인다. 스택은 배열, 동적배열(Vector), 연결리스트로 구현이 가능하다. push(), pop()이 같은 장소에서 일어나고 que..

자료구조의 큐에 대해서 알아보자 First In First Out의 구조를 가지고 있으며 방향성이 있는 자료구조이다. 삽입과 삭제 연산이 일어나는 곳이 다르다는 이야기다. -> 이 개념이 가장 중요하다. 이러한 일을 처리할 때 쓰는 것이다. 또한 삽입,삭제 연산에 있어서는 상수의 시간복잡도를 가진다. ** 주로 순차적으로 진행되어야 하는 일을 스케줄링할 때 사용된다. 주로 우리의 일상적으로 쓰는 곳에 있다. 줄을 서서 기다리는 모든 것들이 큐와 같다. ** 큐를 CPP에서 사용하기 위해서는 헤더를 사용해서 포함시켜야 한다. 큐를 선언할 때 원소가 될 자료형을 선언하며 크기는 선언하지 않았다. 하지만 enqueue와 dequeue를 사용하는 대신 push() 와 pop()를 사용하며 -> push는 bac..

문제 설명 전화번호부에 적힌 전화번호 중, 한 번호가 다른 번호의 접두어인 경우가 있는지 확인하려 합니다. 전화번호가 다음과 같을 경우, 구조대 전화번호는 영석이의 전화번호의 접두사입니다. 구조대 : 119 박준영 : 97 674 223 지영석 : 11 9552 4421 전화번호부에 적힌 전화번호를 담은 배열 phone_book 이 solution 함수의 매개변수로 주어질 때, 어떤 번호가 다른 번호의 접두어인 경우가 있으면 false를 그렇지 않으면 true를 return 하도록 solution 함수를 작성해주세요. 제한 사항 phone_book의 길이는 1 이상 1,000,000 이하입니다. 각 전화번호의 길이는 1 이상 20 이하입니다. 같은 전화번호가 중복해서 들어있지 않습니다. 입출력 예제 ph..