분류 전체보기
-
백준 - 2011(암호코드) [C++]문제 풀이/백준 2023. 3. 14. 23:39
이 문제는 다이나믹 프로그래밍을 이용해서 푸는 문제이다. 이 문제는 dp 배열을 map으로 선언할 수 있다면 쉽게 풀 수 있다. #include #include #include using namespace std; #define MOD 1000000 map m; int func(string temp) { if (temp.empty()) { return 1; } if (m[temp] != 0) { return m[temp]; } int result = 0; int n = temp.size(); if (n >= 1) { for (int i = 1; i = 2) { for (int i = 10; i > password; int answer = func(password); cout
-
프로그래머스 - 여행경로문제 풀이/프로그래머스 2023. 3. 14. 22:05
이 문제는 DFS를 이용하는 Level 3 문제이다. 이 문제에서 핵심은 티켓이 중복될 수 있다는 것과, 정점의 방문 여부와 상관없이 간선이 모두 소진되어야 DFS가 종료되어야 한다는 것이다. 또한 DFS 실행 도중 언제 result에 현재 정점을 넣을 건지도 굉장히 중요하다. 경로가 다양할 경우 알파벳 순서로 앞에 오는 경로부터 선택해야 하므로 ticket[1] 에 대해서 sort를 수행한 뒤 DFS를 실행한다. 보통은 인접 리스트로 그래프를 구현하지만, 이 문제의 조건인 간선의 모든 소진을 만족하도록 직관적으로 구현했다. 처음에는 dfs 초기에 result에 현재 노드를 삽입했지만, 이는 테스트 케이스 1번과 2번에서 오답이 나온다. 위상 정렬 알고리즘처럼 맨 마지막에 result를 삽입하고 그 결과..
-
프로그래머스 - 아이템 줍기문제 풀이/프로그래머스 2023. 3. 14. 21:58
이 문제는 BFS를 이용하는 Level 3 문제이다. 테두리를 따라서 가는 길을 구현하는 것이 어려웠는데, 입력받은 직사각형들의 내부를 모두 1로 만들고, 그 다음에 테두리만 남겨놓고 0으로 바꾸는 방식으로 구현했다. 그 다음에는 기본적인 BFS를 수행하는데, 이 때 문제가 발생한다. 1 1 1 1 1 1 이 표현은 사실 | ㄴㄱ 」 「 | 를 표현한 것이다. 그러나 BFS 를 수행하면 저 구석을 건너뛰고 바로 직진한다. 이를 해결하기 위해서는 좌표를 2씩 곱해서 BFS를 수행하고, 그 값을 2로 나누면 된다. #include #include #include #include using namespace std; int matrix[102][102]; int visited[102][102]; int dy[..
-
프로그래머스 - 단어 변환문제 풀이/프로그래머스 2023. 3. 14. 00:06
코딩테스트 고득점 Kit DFS/BFS Level 3 단어 변환 문제이다. 이 문제는 bfs를 이용해서 푸는데, 인접 리스트와 visited 배열을 맵으로 선언하는 것이 핵심인 문제이다. 또한 begin과 words 단어들 중에서 알파벳 하나만 다른 단어들끼리 인접하다는 생각을 해야 풀 수 있는 문제이다. #include #include #include #include using namespace std; map edges; map visited; int bfs(string begin, string target) { queue q; visited[begin] = 1; q.push(begin); while (!q.empty()) { string present = q.front(); q.pop(); if (..
-
백준 - 2150 (Strongly Connected Component) [C++]문제 풀이/백준 2023. 3. 12. 22:41
이 문제는 유향 그래프의 강한 연결 요소들을 찾는 기본 문제이다. 딱히 주의할 점은 없지만 하나 있다면 출력에서 각 강한 연결 요소들 안에서의 정렬도 해야하지만 강한 연결 요소들간의 정렬도 필요하다는 것이다. 강한 연결 요소를 찾는 알고리즘은 O(V + E)인데, 이 문제의 입력은 V 가 최대 10000, E가 최대 100000이므로 2초의 시간이면 충분하다. #include #include #include #include using namespace std; int v, e; vector edges[10001]; vector transpose[10001]; vector visited; stack st; vector tempNodes; vector answer; void dfs(int start) { v..
-
강한 연결 요소 (Strongly Connected Components)CS/알고리즘 2023. 3. 12. 22:38
유향 그래프에서 모든 정점이 도달 가능하면 강하게 연결되었다고 한다. 여기서 강한 연결 요소는 부분 그래프의 모든 정점이 강하게 연결된 것이다. 강한 연결 요소를 찾는 것은 O(V + E) 시간에 가능하다. Transpose graph가 이를 찾는 알고리즘에서 사용되는데, 이는 원래 그래프의 모든 간선의 방향이 반대인 그래프이다. 강한 연결 요소를 찾는 알고리즘은 다음과 같다. 1. DFS를 수행한다. 2. DFS를 수행하고 각각이 끝날 때마다 스택에 집어넣는다. 3. Transpose graph에 대해서 DFS를 수행한다. 이 때 시작점은 스택에서 pop하는 순서대로이다. 4. DFS가 끝날 때마다 저장한다. 이를 C++로 구현하면 다음과 같다. int v, e; vector edges[10001]; ..
-
프로그래머스 - 체육복문제 풀이/프로그래머스 2023. 3. 12. 18:48
코딩테스트 고득점 Kit 탐욕법(Greedy) Level 1 체육복 문제이다. 이 문제는 기초적인 그리디 알고리즘 문제로, 문제에서 제시한 그대로 구현하면 정답이 나온다. #include #include using namespace std; int solution(int n, vector lost, vector reserve) { int answer = 0; vector students(n + 1, 1); for (auto i : lost) { students[i]--; } for (auto i : reserve) { students[i]++; } for (int i = 1; i
-
프로그래머스 - 모음사전문제 풀이/프로그래머스 2023. 3. 12. 18:17
코딩테스트 고득점 Kit 완전탐색 Level 2 모음사전 문제이다. 이 문제는 a,e,i,o,u 다섯 모음으로 이루어진 모음 사전에서 어떤 단어가 몇번째 단어인지 알아내는 문제이다. 완전 탐색, 백트래킹으로 모든 단어의 조합을 구하는 연산의 수는 5^5 = 3125밖에 되지 않고, 모든 단어 조합의 수 또한 5 + 25 + 125 + 625 + 3125 = 3905개밖에 안되기 때문에 전역 배열에 담기에도 충분한 크기이다. #include #include using namespace std; vector words; char alphabet[5] = {'A', 'E', 'I', 'O', 'U'}; void func(int index, string temp) { if (index == 5) { return..