문제 숫자 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 [프로그래..
문제 접근 캐릭터가 적 팀의 진영까지 가는 가장 빠른 길을 찾는 것으로, 최단 경로를 찾는 문제이다. 최단 경로를 찾는 문제의 경우 제일 먼저 BFS가 떠오른다! DFS의 경우 재귀함수를 호출하여 스택을 사용하므로 구조상 모든 경로를 다 탐색해보아야 하므로 BFS에 비해 시간이 오래 걸린다. BFS를 이용하여 최단거리를 구한다! 성공 코드 각각의 위치를 구조체 Loc를 통해 구현한다. 큐에 시작 위치인 (0, 0)을 넣는다. 큐가 비어있지 않은 동안 다음을 반복한다. 큐에 들어있는 원소를 하나 pop하여 pop한 원소의 위치에서 상, 하, 좌, 우를 탐색하며 게임 맵 크기의 범위에 들어가고 방문하지 않은 위치라면 큐에 해당 위치를 넣는다. 해당 위치의 distance를 pop한 원소의 위치까지의 dist..
[프로그래머스/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]
[프로그래머스/c++] 타겟 넘버
문제 파악 음이 아닌 n개의 정수들을 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버를 만든다. 유형 파악 우선 문제에서 주어진 입출력 예를 보고 직접 하나하나 구해보자. numbers를 통해 주어진 수들이 순서대로 더해지거나 빼지는 것이므로 아래 그림과 같이 모든 경우를 직접 구해본다. 첫 번째 입출력 예 numbers에 주어진 수 5가지를 순서대로 더하거나 빼준다. 마지막에 target 값인 3이 나오는 경우가 총 5가지인 것을 확인할 수 있다. 두번째 입출력 예 numbers에 주어진 수 4가지를 순서대로 더하거나 빼준다. 마지막에 target 값인 4가 나오는 경우가 2가지인 것을 확인할 수 있다. 🤨 두 가지의 입출력 예에 대해 직접 그려본 결과 연산한 결과에 대해 계속해서 + 또는 - 연산을 반복..
크루스칼 알고리즘을 이용하는 문제이다. 처음에 문제를 보고 크루스칼 알고리즘이 떠오르지 않아 헤매다가 구글링을 통해 찾아보며 풀이 방법을 알게 되었다. 크루스칼 알고리즘이란? 간단하게 설명하면 그래프 내의 모든 정점들을 가장 적은 비용으로 연결하기 위해 사용된다. 그래프 내의 모든 정점을 포함하고 사이클이 없는 연결 선을 그렸을 때, 가중치의 합이 최소가 되는 상황을 구하고 싶을 때 크루스칼 알고리즘을 사용하게 된다. 즉 최소 신장 트리를 구하기 위한 알고리즘이다. 참고 https://chanhuiseok.github.io/posts/algo-33/ 알고리즘 - 크루스칼 알고리즘(Kruskal Algorithm), 최소 신장 트리(MST) ## chanhuiseok.github.io 다른 풀이 코드 #i..