https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 1. Logic 처음에 문제를 봤을 때 유니온 파인드로 푸는 줄 알았다. 정 안풀려서 블로그를 참고해서 풀이했다,, r1-r2, rn-r1 끼리 팀을 맺는다는 말은 순환이 있는 그래프끼리 팀을 맺는다는 말이다. 재귀를 활용해서 vis배열에 방문을 처리하면서 방문처리된 배열에 group배열(그룹이 만들어졌다는, 순환하는 그래프의 노드를 표시)이 false라면 그룹을 만들 수 있는 상황이기 때문에 연결된 ..
Algorithm
https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 1. Logic 중위 표기식은 연산자가 연산이 필요한 곳에 위치하는 우리가 흔히 쓰는 연산식이다. 반면 후위 표기식은 컴퓨터가 사용하는 연산자가 뒤에 있는 표기식이다. 컴퓨터는 우리가 아는 중위 표기식을 후위 표기식으로 변환해서 연산을 진행한다. 이 과정에서 스택이라는 자료구조가 필요하다. 중위 표기식 > 후위 표기식 변환 로직 1. 피연산자(연산하고싶은 숫자) 무조건 출력 2. 연산자인 경우..
https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 1. Logic 최소 스패닝 트리 기본 문제 2. Code Kruskal #include using namespace std; int v, e; int parent[1001]; vector graph; int find(int x) { if(parent[x] == x) return x; return parent[x] = find(parent[x]); } int solve() { int weight = 0; for(int i = 0; i < e; i++) { int cost = graph[..
https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 1. Logic 최소 스패닝 트리 기본 문제. 문제를 읽어보면 분리된 두 마을의 길들은 없앤다고 했기 때문에 1. 모든 마을을 연결하는 최소 스패닝 트리를 구하고 2. 스패닝 트리를 구성하는 원소값 중 최댓값을 원소의 합에서 빼서 정답을 도출한다. 2. Code Kruskal #include using namespace std; int v, e; vector ..
https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 1. Logic 최소 스패닝 트리 기본문제 오늘 MST(Minimum Spanning Tree) 최소스패닝 트리를 공부해서 풀이 방법인 크루스칼, 프림 두방식 모두 풀이해봤다. 2. Code Kruskal #include using namespace std; int v, e; vector graph; int parent[10001]; int find(..
https://www.acmicpc.net/problem/2210 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net 1. Logic 5X5배열에 cnt도 6이기 때문에 브루트포싱 돌려도 시간 복잡도를 넘지 않는다! DFS로 해결했다 2. Code #include using namespace std; char graph[5][5]; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; unordered_sets; void sol..
https://www.acmicpc.net/problem/1189 1189번: 컴백홈 첫 줄에 정수 R(1 ≤ R ≤ 5), C(1 ≤ C ≤ 5), K(1 ≤ K ≤ R×C)가 공백으로 구분되어 주어진다. 두 번째부터 R+1번째 줄까지는 R×C 맵의 정보를 나타내는 '.'과 'T'로 구성된 길이가 C인 문자열이 주어진다 www.acmicpc.net 1. Logic 기본 DFS문제. 간단하게 T를 피해서 DFS 돌려주고 이동 거리가 맞는것만 count해주면 된다. 2. Code #include using namespace std; int r, c, k; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; char graph[6][6]; bool vis[6][6..
https://school.programmers.co.kr/learn/courses/30/lessons/250137?language=cpp 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. Logic 그냥 구현문제 부분문제를 나누자면 1. 몬스터에게 공격받을 때 2. 몬스터에게 공격 안받을 때 (붕대 감아야 함) 부분문제를 나눠서 상황에 따라 구현하면 실수를 줄일 수 있다. 2. Code #include #include #include using namespace std; int solution(vector bandage, int health, vect..
https://www.acmicpc.net/problem/1326 1326번: 폴짝폴짝 첫째 줄에 징검다리의 개수 N(1≤N≤10,000)이 주어지고, 이어서 각 징검다리에 쓰여 있는 N개의 정수가 주어진다. 그 다음 줄에는 N보다 작거나 같은 자연수 a, b가 주어지는 데, 이는 개구리가 a번 www.acmicpc.net 1. Logic 처음에 DP로 될거같아서 시도했는데 DP는 vis배열을 찍고 나오기 때문에 최단거리 계산이 안된다. 그리고 vis배열을 기록을 안하게 되면 루프를 계속 들어가기 때문에 힙이 터진다..ㅋㅋㅋㅋ 결국 BFS 느낌으로 해결 이 문제에서 " 징검다리에 쓰여 있는 수의 배수만큼 떨어져 있는 곳으로만 갈 수 있다."는 배수만큼 앞으로 이동 + 배수만큼 뒤로 이동할 수 있다. 2...
https://www.acmicpc.net/problem/1525 1525번: 퍼즐 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. www.acmicpc.net 1. Logic 입력을 인덱스로도 받지만 string으로 받은 후 0의 위치를 찾고 그 상태에서 옮길 수 있는 좌표를 찾아 BFS 브루트포싱한다. 방문처리를 어떻게 해야 할 지 고민이었는데 map / set을 활용하여 중복이 되지 않도록 처리해줬다. map을 활용한 풀이, set을 활용한 풀이 둘 다 해봤다 2. Code map을 활용한 풀이 #include using namespace std; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -..
