전체 글
BaekJoon 1012번: 유기농 배추(C++ DFS/BFS)
https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 풀이법 1) DFS와 BFS를 이용해서 풀 수 있는 문제이다. 2) 최소의 벌레의 개수를 찾아야 하니, visited 배열을 이용한다면 쉽게 문제를 해결할 수 있다. 3) 한번 방문한 노드를 다시 방문하지 않으므로 시간 복잡도는 O(nm)이 될 것이다 재귀를 이용한 DFS를 이용한 풀이 #include #include #include #include using namespace std; int t; int a..
BaekJoon 2667번: 단지번호붙이기(C++)
https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 풀이법 1) DFS와 BFS 어떤 걸로 풀어도 성공할 수 있는 문제이다. 연결되어 있는 것이 있는지가 핵심이고, 공부를 위해 둘다 구현해 보는 것을 추천한다 2) 구현에 어려움이 있는 문제기 보다는, 빠르게 이게 무슨 문제구나를 파악하는 것이 중요한 문제이다. 3) BFS와 DFS의 개념에 대해 알고 있다면, 구현 시에 BFS..
LeetCode 1368번: Minimum Cost to Make at Least One Vaild Path in a Grid(C++)
leetcode.com/problems/minimum-cost-to-make-at-least-one-valid-path-in-a-grid/ Minimum Cost to Make at Least One Valid Path in a Grid - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 해당 문제는 위 링크를 클릭하면 볼 수 있다. 문제 설명 1) m x n의 grid 배열이 주어진다. 해당 grid는 다음 내가 방문해야 할 cell을 가르키고 있다. 2) 각 ..
BaekJoon 1260: DFS와 BFS (C++)
www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 풀이법 및 장단점 1) DFS -장점: 현 경로 상의 노드를 기억하기 때문에, 적은 메모리를 사용한다. -장점: 찾으려는 노드가 리프에 가까울 수록 BFS보다 빠르게 찾을 수 있다. -단점: 해가 없는 경로를 탐색할 경우 단계가 끝날 때 까지 탐색하기에 최단 경로라는 보장이 없다. 2) BFS -장점:..
Programmers: 더 맵게(C++)
programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 풀이법 1) priority_queue를 이용하여 문제를 해결하고자 한다면 쉽게 풀 수 있는 문제이다. 2) 조건을 상세하게 살피는 것이 매우 중요하다 (정확성 테스트 16 만 막히는 분들은 맨 밑에 도움이 될 말을 적어두었다.) #include #include #include #includ..
BaekJoon 5568번: 카드 놓기(C++)
www.acmicpc.net/problem/5568 5568번: 카드 놓기 상근이는 11, 12, 21, 112, 121, 122, 212를 만들 수 있다. www.acmicpc.net 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 풀이법 1) next_permutation과 map 자료형을 이용하여 푼다면 쉽게 풀 수 있는 문제이다. 2) next_permutation은 현재보다 큰 순열을 만들어 주기 때문에 초기 입력 값에 sort는 필수적이다. 3) map 자료형의 key는 중복이 될 수 없다. 이를 이용하여 문제를 해결했다. #include #include #include #include #include using namespace std; int n, k; int an..
BaekJoon 1717번: 집합의 표현(C++)
www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 풀이법 1) Union Find 와 Disjoint set에 대한 이해가 필요한 문제이다. Union Find - 여러 서로소 집합의 정보를 저장하고 있는 자료구조를 의미 - Tree 구조를 활용하여 parent를 찾아내는 find 함수와, 두 node의 parent가 같지 않을 때 트리를 합치는 ..
BaekJoon 3584번: 가장 가까운 공통 조상(C++)
www.acmicpc.net/problem/3584 3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 풀이법 1) 가장 가까운 조상을 찾기 위해 LCA 알고리즘을 활용하였다. www.crocus.co.kr/660 LCA(Lowest Common Ancestor) 알고리즘 LCA(Lowest Common Ancestor) 알고리즘이란? LCA 알고리즘이란 영어 해석 그대로 최소 공통 조상을..
BaekJoon 1593번: 문자 해독(C++)
www.acmicpc.net/problem/1593 1593번: 문자 해독 첫째 줄에 고고학자들이 찾고자 하는 단어 W의 길이 g와 발굴된 벽화에서 추출한 문자열 S의 길이 |S|가 빈 칸을 사이에 두고 주어진다. (1≤g≤3000, g≤|S|≤3,000,000) 둘째 줄에 W, 셋째 줄에 S의 실 www.acmicpc.net 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. ascii 코드를 이용하여 배열을 만든다면 풀 수 있는 문제이나, 시간초과 같은 문제로 인해 난이도가 높다. Google 등에 풀이 자료가 많지 않은 문제이기에, 문제를 풀다가 막혔던 분들은 맨 밑으로 내려서 주의사항을 읽는 것을 추천한다. (필자는 총 8번의 시간초과를 통해 문제를 풀었기에, 아주 조금이나마..
찾아라 프로그래밍 마에스터: 게임 맵 최단거리(C++)
programmers.co.kr/learn/courses/30/lessons/1844 코딩테스트 연습 - 게임 맵 최단거리 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,1],[0,0,0,0,1]] 11 [[1,0,1,1,1],[1,0,1,0,1],[1,0,1,1,1],[1,1,1,0,0],[0,0,0,0,1]] -1 programmers.co.kr 해당 문제에 관한 내용은 위의 사이트에 들어가면 자세히 확인할 수 있다. 2차원 배열이 주어지고 최단거리를 묻는 문제이다. 풀이법 1) BFS에 count 변수를 넣어서 풀면 최단거리를 구할 수 있다. 2) 배열의 크기를 확인 한 후, 방문하지 않은 노드와 들어갈 수 없는 값들을 제외하고 BFS를 순회시킨다. 3) vx와 ..