목록전체 글 (124)
풀이 보관함
문제 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 풀이 과정 싸이클이 형성되면 팀이 생성된다. 싸이클이 형성되는 경우 1) 첫번째 노드와 마지막 노드가 같을 경우 4 - 7 - 6 - 4 2) n번째 노드와 미지막 노드가 같을 경우 2 - 1 - 3 - 3 🚩 반드시 알아야 할 것 재방문으로 사이클 형성을 알 수 있다. 재방문 노드 이전의 노드들 (경로)은 사이클 형성 불가한 노드라는게 판정된다. 첫번째 노드를 1, 2, 3 .. 로 진행하다가 ..
문제 https://www.acmicpc.net/problem/7562 풀이 방문한 순서대로 좌표를 저장하기 위한 데이터 타입으로 pair를 가지는 queue를 선언했다. std::queue q; 🔍 knight() 처음 함수를 실행하면 (0, 0)에서 방문할 수 있는 위치들를 탐색하여 목표 지점에 왔는지 확인한다. 첫번째 이동으로 갈 수 있는 모든 위치를 queue에 저장한다. 이 때, 재방문 방지를 위해 min[x][y] == 0 이라는 조건을 달아주었다. (한번도 방문 안한 곳이라면 queue에 넣는다.) queue에는 다음 이동으로 갈 수 있는 모든 위치를 갖게 된다. 이 과정을 (N, M)까지 반복한다. (N, M)에 도달하면 바로 return 하기 때문에 최소 이동 횟수을 바로 알 수 있다. ..
문제 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..