스택의 개념스택은 '쌓다'와 같은 뜻을 가진 용어로, 접시를 쌓아 놓은 형태와 비슷한 자료구조즉, 데이터를 순서대로 쌓는 자료구조마지막에 저장한 데이터를 가장 먼저 꺼내게 되는 후입선출(LIFO: Last In First Out) 구조가장 마지막에 들어온 데이터를 먼저 처리할 때 사용사용처웹 브라우저의 '뒤로가기'실행 취소(뒤돌리기)의 'undo'수식 계산 또는 수식 괄호 검사... 스택의 특징후입선출(LIFO) 구조가장 늦게 들어온 데이터가 제일 먼저 빠져나가는 구조단방향 입출력 구조데이터가 들어오는 방향과 나가는 방향이 같음정해진 방향으로만 쌓을 수 있음데이터를 하나씩만 넣고 뺄 수 있음깊이 우선 탐색(DFS)에 이용재귀 함수의 동작 흐름과 같은 구조를 가짐 자바에서 스택 사용하기메서드설명Stack ..

문제https://www.acmicpc.net/problem/22858 여담문제 이해만 하면 쉽게 풀 수 있는 문제였는데 문제 자체를 이해하지 못해서 시간을 좀 날렸다..ㅎㅎ 독해력 대체 무슨일이야풀이문제에 따르면 "Di번째 카드를 i번째로 가져오는 것이 셔플"이라고 한다. 개인적으로 이 문장을 이해하는게 조금 어려웠기 때문에 예제로 주어진 입력에 설명을 덧붙여보겠다. i가 1인 경우D1번째 카드를 1번째로 가져와야 함 (D[1] = 4)즉, 4번째 카드를 1번째로 가져와야 함S[1] = P[D[1]] = P[4] = 3i가 2인 경우D2번째 카드를 2번째로 가져와야 함 (D[2] = 3)즉, 3번째 카드를 2번째로 가져와야 함S[2] = P[D[2]] = P[3] = 5...i가 5인 경우D5번째 카드..

문제https://www.acmicpc.net/problem/20291 여담문제를 풀고난 뒤, 코드가 깔끔하지 않은 것 같아 다른 풀이들을 참고했다. 해당 블로그에서 엄청 깔끔하게 코드를 짰길래 참고해서 다시 풀었다. 항상 깔끔하게 풀지 못하는 것 같아 조금 아쉽다.. 좀 깔끔하게 푸는 습관을 들이도록 해야지!  풀이확장명을 구하기 위해 입력받은 문자열을 .로 split()한다. split()한 결과의 첫 번째 문자열은 파일명, 두 번째는 확장명일 것이다. 따라서 필요한 두 번째 문자열만 사용하면 된다. 그 후 과정은 다음과 같다.HashMap을 사용해서 입력받은 파일의 확장명이 존재하는지 확인한다.hashMap.containsKey(file)확장명이 존재하는 경우라면, 파일의 수를 1 증가하여 Hash..

문제https://www.acmicpc.net/problem/12933 여담문제를 풀고 난 뒤, 종료 조건을 체크하는 부분이 조금 아쉬워서 다른 풀이들을 참고했다. 해당 블로그의 글을 읽고 아이디어가 떠올라서 새로 풀었다. 처음에는 울음소리를 확인할 때, 확인한 울음 소리들을 리스트에 저장하고 올바른 울음소리일 때만 방문 처리를 했었다. 이는 문제를 제대로 이해하지 못하고 풀었기 때문에 정석?으로 푸는 방법이 아니었다. 예제 6번을 뒤늦게 보고 문제를 잘못 이해했다는 것을 알게 되었다. "제대로 울지 않는 오리가 있어도 제대로 우는 오리의 수만 구하면 된다"라고 생각했는데, 제대로 울지 않는 오리가 하나라도 있으면 녹음한 소리가 올바르지 않은 것이었다..ㅎㅎ 문제를 처음부터 잘 이해했더라면 최적화된 방법..

문제https://www.acmicpc.net/problem/1913 여담처음에 DFS 방식으로 문제를 풀었다. 메모리를 너무 많이 사용하길래 이 방식이 맞나싶어서 다른 풀이를 봤더니 그냥 순수 구현으로 풀 수 있는 문제였다..  순수 구현으로 푼 문제와 DFS 탐색을 통해 푼 문제의 메모리 차이가.. ㅎㅎ 풀이이 문제는 "안 → 밖" 또는 "밖 → 안"의 순서대로 하나씩 칸을 채워나가면 된다. 나는 밖에서 안으로 채우는 방식을 사용했다. 다음 사진에서 알 수 있듯이 "아래 → 오른쪽 → 위 → 왼쪽" 방향이 반복된다. 따라서 (0, 0)에서 시작해서 한 방향으로 이동하다가, 다음에 이동할 지점이 범위를 벗어나거나 이미 값이 기록된 곳이라면 방향을 변경하면 된다. 범위를 벗어난 경우x + dx[i] = ..

문제https://www.acmicpc.net/problem/7569 여담토마토 문제와 거의 유사하다. 다른 점은 2차원에서 3차원으로 변경됐다는 것 정도? 그래서 문제 제목도 같나 보다. 토마토 문제를 풀고 바로 푸는 것이라 쉽게 풀 수 있었다. 풀이토마토들이 다 익는 최소 일수를 알고 싶은 것이므로 BFS 탐색을 수행하면 된다. 언급했듯이 이전에 풀었던 토마토 문제와 거의 유사하므로, 풀이 방법은 토마토 풀이 게시글을 참고하면 된다.  주의해야 할 점은 2차원이 아니라 3차원이라는 점이다. 따라서 상하좌우뿐만 아니라 위, 아래로도 BFS 탐색을 수행해야 한다. 코드import java.util.*;import java.io.*;public class Main { s..

문제https://www.acmicpc.net/problem/17836 여담예전에 BFS 문제를 풀 때, "탐색 도중에 상태가 변하는 것이 있다면 3차원 배열로 방문 처리를 진행하자!"라는 것을 외웠다. 그래서 빠르게 아이디어를 떠올릴 수 있었다. 역시 코테는 많은 유형을 접해보고 푸는 게 답인 듯하다. 많이 풀어보자! 풀이용사가 (1, 1)에서 (N, M)까지 상하좌우로 이동하여 공주에게 도달할 수 있는 최단 시간을 구하는 것이므로, BFS 탐색을 수행하면 된다. 이때, 그람을 획득하면 성 내부의 벽을 부술 수 있다. 부술 수 있는 벽의 개수는 제한이 없으므로, 그람을 획득한다는 것은 벽이 없어진다는 것이랑 동일한 의미를 가진다.  따라서 그람을 획득하지 못한 경우와 그람을 획득한 경우의 2가지로 나누..

문제https://www.acmicpc.net/problem/7576 여담익어있는 토마토가 여러 개 주어질 수 있으므로, 익어있는 토마토들의 위치를 미리 큐에 넣는 작업이 필요하다. 이 과정에서 큐에 넣기만 하고 방문 처리를 하지 않아서 틀렸었다.. 뒤늦게라도 알아서 다행이지만 코테였다면 이유를 찾느라 고생했을 것이다. 아찔... 익숙한 문제라고 뇌 빼고 풀지 말고 차근차근 풀도록 하자! 풀이토마토들이 모두 익을 수 있는 최소 일수를 구하는 문제이다. 즉, 최단 거리를 구하는 문제와 비슷하므로 BFS 탐색을 수해하면 된다.  문제 풀이 과정은 다음과 같다.익은 토마토들이 1개 이상 주어지므로, 익은 토마토들의 위치를 큐에 저장하고 방문 처리한다.BFS 탐색을 수행하여 토마토들이 익는 일수를 구한다.box..

문제https://www.acmicpc.net/problem/10026 여담골드5치고는 간단하게 BFS 탐색을 수행하면 되는 것이라 쉽게 풀 수 있었다! 풀이같은 색으로 이루어진 구역의 개수를 찾는 것이므로, BFS 또는 DFS 탐색의 호출 횟수를 구하는 것과 같다. 따라서 단순하게 BFS/DFS 탐색을 수행하면 된다. 이때, 적록색약인 사람은 빨강과 초록을 구분하지 못하므로 초록(=G)을 빨강(=R)으로 변경한 뒤 탐색을 수행하면 된다. 자세한 내용은 아래의 코드를 참고하면 된다. 코드import java.io.*;import java.util.*;public class Main { static int N; static char[][] pictureO, pictureX; // O: 적록색약 ..

문제https://www.acmicpc.net/problem/5427 여담테스트 케이스마다 큐를 초기화하지 않아서 틀렸었다. 이런 실수가 진짜 치명적인건데....ㅎ 맞는 것 같은데 틀리면 제일 먼저 초기화와 변수를 확인하자..  풀이빌딩을 탈출할 수 있는 최소 시간을 구하는 것이므로, BFS 탐색을 이용하면 된다. 1초마다 불이 퍼지고 상근이가 이동하며, 상근이는 불이 퍼진 곳이나 퍼질 곳으로 이동할 수 없다. 따라서 불을 먼저 퍼뜨린 후, 상근이를 이동시키는 방법을 반복하면 된다. 이때, 불이 더 이상 퍼질 수 없더라도 상근이가 탈출을 하는 데에는 아무 상관이 없다. 따라서 상근이가 더 이상 움직일 수 없을 경우(= 큐가 빈 경우)에만 BFS 탐색을 종료하면 된다. 자세한 내용은 코드를 참고하면 된다...