Stack
-
2667.단지번호붙이기알고리즘/백준 BAEK JOON 2020. 5. 21. 23:40
이번에 풀어볼 문제는 단지번호붙이기이다. 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 생각보다 이상한곳에 막혀서 시간낭비를 했다. 시간은 1시간 30분정도 걸렸고 목표한 시간보다 30분이나 초과되었다. 사실 30분컷 낼 수 있었는데 이걸 코드하나를 잘못집어넣어서 하루종일 걸렸다.. 후... DFS를 이용해서 풀었고 이 문제의 포인트는 Stack를 이용하되 Stack에 자신이 이동한 부분의 좌표를 넣어주는 것이다. 그래야지 DFS로 쭈욱 탐색하다가 막혔을 때 다시 돌아가서 탐색하지 않은 방향으로 탐색을 진행..
-
5430.AC알고리즘/백준 BAEK JOON 2020. 4. 13. 18:10
이번에 풀어볼 문제는 백준의 5430번 AC이다. 난이도가 많이 어렵기보단 센스가 필요한 거 같다. 문제를 보도록 하자. .....?????? 5430번: AC 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. www.acmicpc.net #include #include #incl..
-
11866.요세푸스 문제 0알고리즘/백준 BAEK JOON 2020. 4. 6. 23:57
이번 문제는 백준의 11866 요세푸스 문제 0이다.11866번: 요세푸스 문제 0첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000)www.acmicpc.net문제를 이해하는 건 금방했는데 원형으로 배열을 만들어야하나 하는 생각을 했고굳이 그럴 필요가 없다고 생각해서 포인터로 예외처리를 하려고 하였으나너무나 비효율적이었고 결국 queue를 사용해서 풀었다. 조금만 쉽게 생각하면 됬는데.. 허허.. #include #include using namespace std; int main() { int n, k; cin >> n >> k; // 길이와 K번째 순서 입력 queueq; // queue for(int i=1; i
-
1874.스택 수열알고리즘/백준 BAEK JOON 2020. 4. 2. 23:59
이 문제는 그렇게 어려운 문제는 아니였지만 굉장히 헷갈리긴 했다. Stack과 Queue문제를 꽤 풀어본 것이 도움이 되었던 것 같다. 스택과 큐에 대한 다른문제들도 풀었지만 난이도가 너무 쉽다고 느껴 굳이 남기지 않았다. 하지만 처음에 문제를 거꾸로 이해해버렸고 반례를 만나서야 잘못 이해했다는 것을 알아챘다. 아직 반례를 생각해 내는 것이 굉장히 서툰 것 같다.. 어쨌든 결과적으로 다 구현하고 나서 시간초과가 났는데 그러한 이유는 아래와 같다. #include #include #include using namespace std; int main() { queueans; // 부호정답이 저장될 queue queue q; // 입력받을 queue stack t; // 수열이 가능한지 ..
-
1226.미로1 & 1227.미로2알고리즘/SW Expert Academy 2020. 3. 26. 00:16
이번문제는 미로1과 미로2이다. 문제는 간단하다. 주어진 출발지에서 주어진 목적지까지 갈 수 있나 없나를 체크하는 알고리즘을 구현하는 것이고 나는 DFS를 이용하기로 했다. 문제는 queue강의에서 출제되었지만 나는 DFS를 Stack을 이용해서 구현해보았다. 앞서 stack과 queue를 나름 많이 다뤄보아서인지 사용이 자연스러워진거같다. 처음 시작할 때는 분명 헷갈렸던 것 같은데.. ㅎㅎ 미로1과 미로2는 MAX를 16이나 100이냐 말고 코드가 달라진게 없어서 한 번에 포스팅했다. #include #include #include using namespace std; #define MAX 16 // 100 int dx[4]={-1,1,0,0}; // X축 이동 int dy[4]=..
-
1218. 괄호 짝짓기 풀이알고리즘/SW Expert Academy 2020. 3. 4. 19:34
이번에 풀어볼 문제는 괄호 짝짓기이다. 알고리즘 문제는 간단하게 풀이만 적도록 하려고 한다. 대충 이러한 문제이다. * 이번 문제를 풀면서 중요하게 기억해야할 내용 * 1. stack 사용법과 다음 테스트 케이스를 위해 stack을 비워줘야함 2. 어떤식으로 탐색을 진행할 것인지 파악 -> 한쪽 형태의 모양을 스택에 우선 넣고나서 비교 3. 가장 중요한건 문제를 제대로 파악하는 것 -> 단순히 짝만 맞추는 것이 아니다. 문제에는 상세히 설명하지 않아서 안나왔지만 가장 처음과 마지막은 괄호는 항상 '(' ')' 이런식으로 닫는 형태여야하며 ')' '(' 이렇게 는 자릴 바꾸면 한쌍이겠지만 문제에서는 한쌍으로 인정하지 않는다... #include #include using namespace std; int ..