백준6

• 

  [C++] 백준 - 11779 최소비용구하기2 (다익스트라) 1. 문제 2. 입출력 및 예제 3. 문제 해설 백준 - 1916 최소비용 구하기 문제와 비슷한 문제이다. 하지만 추가된 것은 몇 개의 노드를 거치면서 왔는 지에 대한 정보와 지나온 path에 대한 정보도 출력을 해야한다는 것이다. 처음에 예제 답안을 살펴보면 경로가 1 3 5로 나와있는 것을 확인할 수 있다. 하지만 위의 그래프를 그려보면 1 3 5 뿐만 아니라 1 4 5도 된다는 것을 알 수 있다. 그리고 경로에 대한 제약사항은 존재하지 않는다. 따라서 이 문제는 도달할 수 있는 경로가 여러가지일 경우에는 그냥 아무거나 출력하면 되는 문제였다. 여태까지 많은 경로를 기억했다가 출력하는 문제들을 풀어본 결과 경로를 기억하는 문제들은 대게 그 경로에 추가되는 로직이 있기 마련이다. 또한 위의 문제는 다익.. c++/알고리즘 2023. 2. 15.

• 

  [c++] 백준 - 단절점(11266) [단절점 이론] 1. 문제 2. 입출력 3. 예제 입출력 4. 문제 해설 혼자 푼 문제는 아니다. 애초에 특수한 단절점과 단절선에 대한 이론을 알고 있어야해서 인터넷에서 단절점과 단절선에 대한 이론을 찾아본 후 풀었다. https://jason9319.tistory.com/119 단절점(Articulation Point)와 단절선(Bridge) 하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상의 컴포넌트로 나누어지는 정점을 단절점이라고 합니다.다음과 같은 무방향 그래프가 있다고 해봅시 jason9319.tistory.com 위의 블로그에서 많은 도움을 얻었다. 내가 이해한 바를 다시 정리해 말하면 다음과 같다. 무엇이 단절점인가? 어떤 조건을 만족해야 단절점이 될 수 있을까?를 먼저.. c++/알고리즘 2023. 2. 13.

• 

  백준-4659 비밀번호 발음하기 문제는 다음과 같다. 이 때 문제에서 고려할 것은 3가지이다. 모음이나 자음이 3번 연속으로 오면 안된다. e나 o를 제외한 같은 글자가 2번 연속으로 오면 안된다. 모음(a, e, i, o, u)을 하나 이상 포함해야 한다 나의 코드는 아래와 같다. #include #include #include #include using namespace std; string password = ""; bool vowel = 0; bool seq = 0; int vow = 0; int con = 0; stack charStack; bool isVowel(char a) { if (a == 97 || a == 101 || a == 105 || a == 111 || a == 117) return true; else ret.. c++/알고리즘 2022. 4. 6.

• 

  백준-2468 안전영역 1. 안전영역(DFS) 이 문제 또한 DFS를 활용하여 깊이 탐색을 하는 문제였다. 앞서 문제와 한 가지 다른점은 앞서 유기농 배추 문제는 모든 배열의 값이 0아니면 1이 들어가서 바로 dfs를 탐색할 수 있었던 반면에 이 문제에서는 각 배열마다 다른 높이가 존재해서 높이를 비교하면서 가야한다는 점이 있었다. 하지만 메모리 적으로 여유가 있어 나는 먼저 침수 높이d와 비교해 더 낮은 지대를 1의 값으로 갖는 비교 배열을 만들어준 후 앞선 유기농 배추 문제와 같이 dfs를 실행해주었다. dfs함수에서는 우선적으로 방문 배열을 1로 표시해주어야 하는 것이 중요하다는 것을 명심하자. 다음은 내가 문제를 푼 코드이다. #include #include #include using namespace std; int .. c++/알고리즘 2022. 3. 29.

• 

  백준-1012번 - 유기농 배추 내가 백준 문제를 풀면서 느낀 점은 채점을 할 때 맞게 하고 싶다면 문제에서 변수들을 잘 파악해야한다는 것이다. 우선 문제를 살펴보면 테스트 케이스를 의미하는 변수 T가 존재한다. 또한 배추를 심은 배추밭의 가로길이 M, 세로 길이 N, 배추를 심은 개수 K가 존재한다. 또한 그 후 배추의 위치를 나타내는 변수론느 x, y가 존재한다. 그럼 일단 6개의 변수가 존재하는 것이다. 그 후 반복문 안에서 다음 배열 인덱스를 담아 줄 ny, nx변수와 최종 개수를 ret할 ret 변수까지 9개가 존재한다. 또한 이 문제는 깊이 탐색 문제이므로 배추의 위치를 표현할 map과 그 배열과 같은 크기의 방문 여부 배열이 필요하다. #include #include #include using namespace std; i.. c++/알고리즘 2022. 3. 29.

• 

  백준2178번-미로BFS 이 문제는 가중치가 같은 맵 안에서의 최단 경로를 찾는 문제이다. 이는 자료구조 queue를 사용하며 풀면 되는데 나의 코드는 다음과 같다. #include #include #include #include using namespace std; int n, m, y,x; int max = 104; int a[104][104]; int visited[104][104]; // 입력 배열과 방문 배열 int dy[4] = {-1,0,1,0}; int dx[4] = {0,1,0,-1}; int main() { cin >> n; cin >> m; for(int i = 0; i >a[i][j]; } }//입력 만들기 queue q; // q.. c++/알고리즘 2022. 3. 28.