문제 https://www.acmicpc.net/problem/2178 풀이 (1, 1)에서 (N, M)까지 가는 최단 거리를 구하는 문제였다. 무조건 N, M까지 도달할 수 있다는 가정이 있는 문제였다. min[x][y]에 (1, 1)에서 (x, y)위치까지 갈 수 있는 최단거리를 저장해주었다. 현재 위치가 (r, c)였을 때 한칸 씩 이동하면 이동거리는 min[r][c] + 1 가 된다. 즉, 현재 위치에서 한칸 이동한 값이 min[x][y]보다 작으면 재귀함수를 통해 목표 지점 (N, M)까지 진행하도록 짰다. //한번도 진행하지 않은 길이거나 길을 한칸 갔을 때 최단거리가 맞다면 if(min[x][y] == 0 || min[x][y] > min[r][c] + 1) { //최단 거리를 다시 기록해주..

문제 https://www.acmicpc.net/problem/2644 풀이 당연히 DFS로 풀어야 한다고 생각했는데 BFS로 푸는 사람이 더 많은 것 같다.. 촌수는 깊이 아니냐고....... 왜 BFS로 푸는게 더 좋다고 하는거지? 아는 사람 알려주기 약속~~ 촌수 관계를 담는 그래프 평소처럼 2차원 배열로 하려다가 어떤 블로그에서 이렇게 하길래 따라 해봤다. //전역 std::vector graph; //main문 graph.assign(n+1,std::vector(0, 0)); DFS bool DFS(int v) { if(v == b) return true; ++result; visited[v] = true; //연결된 노드만 탐색 for(int i=0; i HTML 삽입 미리보기할 수 없는 소스

문제 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 X가 3가지 연산을 이용해 K가 되는 최소 연산 횟수를 구하는 문제다. X에서 x-1, x+1, x*2를 할 수 있으니 3^n의 모든 경우의 수를 싹싹 뒤져서 만드는게 맞는걸까? 아무리 생각해봐도 아닌 것 같아서 검색의 도움을 받았다. 하지만 싹싹 뒤지는게 맞았었다. 수학 공식으로 풀 수 있을거라 생각했는데 내가 검색을 잘 못한건지 못 찾았다. 최단 시간을 구..

문제 https://www.acmicpc.net/problem/1260 문제는 간단하게 DFS와 BFS를 구현하는 문제다. 당연히 DFS와 BFS의 개념을 알아야 풀 수 있다. 풀이 노드와 간선으로 이루어진 그래프를 표현하기 위해 2차원 배열을 선언해주었다. #define MAX 1001 int arr[MAX][MAX]; 입력 받은 그래프의 노드 a와 b의 연결을 아래처럼 표현해주었다. std::cin >> a >> b; arr[a][b] = arr[b][a] = true; 이미 방문한 노드를 재방문 여부를 확인할 bool 타입 배열도 선언해주었다. bool visited[MAX] = {false, }; DFS DFS는 시작 노드 (v)로부터 가장 인접한 노드를 찾는 탐색이 반복되기 때문에 재귀함수를 이..

문제 https://www.acmicpc.net/problem/5076 5076번: Web Pages Input will consist of a number of lines of HTML code, each line containing from 0 to 255 characters. The last line will contain a single # character – do not process this line. Within the text of each line will be zero or more tags. No angle bracket will www.acmicpc.net 풀이 파싱하는게 제일 어려운 문제로 괄호 문제랑 비슷하게 풀었다. text 를 예시로 들겠다. 는 스택에 넣어준다. 는 스택의..

문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 풀이 최근에 stack문제만 모아서 푸니까 그냥 ktx타고 봐도 스택 문제였다... 배열로 풀다가 인덱스 쫌쫌따리 따라가기 귀찮아서 라이브러리를 이용해서 풀어주었다! 소스 HTML 삽입 미리보기할 수 없는 소스

문제 https://www.acmicpc.net/problem/5397 풀이 커서를 기준으로 컨테이너를 두개로 나눠서 >, > T; while(T--) { std::string code; std::cin >> code; std::stack c1, c2; char temp; char c; for(int i=0; i

문제 https://www.acmicpc.net/problem/2841 풀이 2차원 배열로 풀어도 되지만 top index를 데리고 다니기 싫어서 stack으로 풀었다. 지금 누르고 있는 줄의 프렛을 저장하는 변수를 생성했다 자료구조를 시각화 하면 대충 아래처럼 생각하면 된다 stack[줄] = [프렛 | 프렛 | ... ] 누르려는 음 stack[줄]의 가장 높은 프렛 누르려는 음을 하나 더 누르면 된다. + 스택이 비었는지 체크하는 부분을 쉽게 처리 하는 방법을 알았다. https://ryute.tist..

문제 https://www.acmicpc.net/problem/2304 Olympiad > 한국정보올림피아드 > KOI 2005 > 초등부 2번 초등부문제라는 게 날 자극한다.. 풀이 웅덩이가 없으려면 5 2 6 처럼 높은 곳에서 아래로 내려갔다가 다시 올라가면 안된다는 조건이 있어야 한다. 높이의 max를 구해 반으로 가르고 -> , > N; for(int i =0; i> L >> H; pillars[L] = H; if(pillars[L] > pillars[max]) max = L; if(left > L) left = L; if(right max int height = pillars[left], pos = left; for(int i = left+1; i = ..

문제 https://www.acmicpc.net/problem/3986 풀이 가장 어려운 것이 문제 이해였다. 소스 #include #include #include int main() { int N = 0, result = 0; std::string word; std::cin >> N; for(int i=0; i> word; for(auto& c : word) { if(!stk.empty() && stk.top() == c) stk.pop(); else stk.push(c); } if(stk.empty()) ++result; } std::cout