[프로그래머스/c++] 등굣길
문제 집에서 학교까지 물이 잠긴 지역을 피해 가는 최단경로의 개수를 구한다. 접근 dp 배열을 통해 각 위치까지 가는데 드는 최단 경로의 개수를 저장한다. 모두 0으로 초기화한다. 먼저 집이 있는 행과 열은 해당 위치까지 가는 최단 경로가 직진하는 경우 단 1개 뿐이므로 1로 설정한다. 이때 주의할점은 집이 있는 행과 열에 웅덩이가 있는 경우는 해당 웅덩이 다음부터는 1로 설정을 멈추어야 한다!(웅덩이가 있으면 직진을 할 수 없으므로!!!) -> 이 부분을 고려안해서 맨 처음에 틀렸었다😕 나머지 위치에 대해서는 왼쪽과 위쪽의 최단 경로의 개수 값을 더하여 저장한다. 이 과정을 반복하면 학교가 있는 위치의 dp 값이 집에서 학교까지 물이 잠긴 지역을 피해 가는 최단 경로의 개수가 된다. 성공 코드(내 코드..
[프로그래머스/c++] 정수 삼각형
문제 삼각형의 꼭대기에서 바닥까지 대각선 방향/한 칸 오른쪽/한 칸 왼쪽으로 이동하며 거쳐간 숫자의 합이 가장 큰 경우를 찾아 해당 합을 반환한다. 접근 dp 배열을 통해 삼각형의 위에서 2번째 층부터 탐색하며 바로 위층에서 현재 위치로 올 수 있는 두 경로 중 숫자가 더 큰 것을 선택하여 현재 위치의 숫자와 합하여 저장한다. 이를 맨 아래층까지 반복하면 맨 아래층에서 가장 큰 값이 삼각형의 꼭대기에서 바닥까지 거쳐간 숫자의 합이 가장 큰 경우에 해당된다. 아래 예를 통해 직접 구해보자. 해당 예시의 경우 30을 반환하게 된다. 성공 코드(내 코드) #include #include #include using namespace std; int solution(vector triangle) { int ans..
문제 숫자 N을 사칙연산을 통해 number로 표현할 때 사용되는 N의 최소 사용횟수를 구한다. 접근 규칙을 찾아서 dp 배열을 만들어 적용시키고자 하였으나 무엇을 기준으로 규칙을 찾아야 할 지 감이 잡히지 않아 문제에서 구하고자 하는 것을 다시 살펴보았다. N의 최소 사용횟수를 구한다는 점에서, N을 1개, 2개, 3개 ... 사용해서 만들 수 있는 수들을 직접 적어보았다. 다음 예시를 통해 살펴보자. N number return 2 11 3 dp[cnt]: N을 cnt 개수 만큼 사용하여 만들 수 있는 수 dp[1] - 2 dp[2] - 22 dp[1]과 dp[1]로 사칙연산 - 2+2=4 - 2-2=0 - 2*2=4 - 2/2=1 dp[3] - 222 dp[1]과 dp[2]로 사칙연산 - 2와 22..
접근 각 game_board와 table 위의 퍼즐 조각들을 (0, 0)을 기준으로 좌표를 옮기는 것까지 생각은 했지만, 해당 방법의 구현과 또한 퍼즐 조각이 회전이 가능하다는 점에서 구현이 힘들어 아래 블로그를 보고 코드를 따라치며 이해하였다. ✔️너무너무 정리가 잘되어 있어 참고하면 좋을 듯 하다! https://velog.io/@hhj3258/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4C%EC%9C%84%ED%81%B4%EB%A6%AC-%EC%B1%8C%EB%A6%B0%EC%A7%80-3%EC%A3%BC%EC%B0%A8-%ED%8D%BC%EC%A6%90-%EC%A1%B0%EA%B0%81-%EC%B1%84%EC%9A%B0%EA%B8%B0 [프로그래..
[프로그래머스/c++] 여행경로
실패 코드 방법 티켓의 [a, b] 중 b를 기준으로 알파벳 순서가 앞서도록 정렬 후, 그 중에서 맨 앞의 ICN을 선택한 후 dfs 함수로 재귀를 통해 경로를 구하도록 하였다. 🤨 그 결과 다음과 같이 테스트 1, 2를 통과하지 못했다... 코드 #include #include #include using namespace std; vector answer; vector t; vector ch(10000, 0); bool cmp(vector a, vector b){ return a[1]
크루스칼 알고리즘을 이용하는 문제이다. 처음에 문제를 보고 크루스칼 알고리즘이 떠오르지 않아 헤매다가 구글링을 통해 찾아보며 풀이 방법을 알게 되었다. 크루스칼 알고리즘이란? 간단하게 설명하면 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용된다. 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용하게 된다. 즉 최소 신장 트리를 구하기 위한 알고리즘이다. 참고 https://chanhuiseok.github.io/posts/algo-33/ 알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST) ## chanhuiseok.github.io 다른 풀이 코드 #i..