문제풀이

프로그래머스 타겟 넘버 문제풀이

문제를 보고 DFS 를 이용하여 풀려고 했으나 또 순서를 생각해서 풀려고 하여 헷갈렸다. 내가 아니라 컴퓨터가 돌리게 하자 문제는 간단하였다. dfs 함수에서 numbers 에 있는 숫자들을 더하기 , 빼기 연산을 했을때 연산횟수가 cnt 와 같아질때 그 값들이 target 과 같았을 때 answer 을 1을 더해주면 된다. #include #include int answer=0; using namespace std; void dfs(vectornumbers,int tg, int sum, int cnt){ if(cnt==numbers.size()){ if(sum==tg)answer++; return; } dfs(numbers, tg, sum + numbers[cnt], cnt + 1); dfs(numbe..

[C++] 백준 1389번 문제풀이

이 문제를 보고 BFS나 DFS로 풀려고 했으나 더 좋은 방법을 찾아서 풀었다. 그 방법은 플로이드 와샬 알고리즘인데 2차원 배열에서 한 정점에서 다른 모든 정점들을 방문 할 때 최소값으로 방문하도록 하는 알고리즘이다 여기선 한칸을 이동할때 비용이 같으므로 1로 통일 하였다. 다른 문제에서 한칸을 이동할때 비용이 다르면 1이 아니라 다른 값을 넣어 해야 할 것이다. #include #include int INF = 96748532; const int MAX = 101; using namespace std; int n, m; int gp[MAX][MAX]; void func() { for (int k = 1; k > m; while (m--) { int a, b; cin >> a >> b; gp[a][b]..

[C++] 백준 1764번 문제풀이

이 문제를 풀 때 들었던 생각은 듣도 못한 사람을 vector 에 넣고 보도 못한 사람이 듣도 못한 사람의 vector 안에 있다면 듣보잡의 vector안에 넣어야 겠다고 생각했다. 보도 못한 사람이 듣도 못한 사람의 vector 안에 있는가를 알기 위해선 탐색을 해야하는데 시간이 많이 걸리기 때문에 binary search 를 이용하여 풀었다. #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); int N, M; cin >> N >> M; vectordb; vectordbj; while (N--) { string name; cin >> name; db..

[C++] 백준 1697번 문제풀이

문제를 보고 든 생각은 내가 숫자를 X2 또는 +1 또는 -1 을 이용하여 K에 도달하도록 만드는 것이 였다. 그러나 문제를 풀수록 멍청한 생각이였단걸 알았고 BFS를 통해 쉽게 풀 수 있었다. (내가 풀지 말고 컴퓨터를 이용하여 풀도록 하자) BFS를 배워도 그것을 떠올리고 풀기가 쉽지 않았다.... 문제를 보고 어떤식으로 풀어야겠다 이 단계에서 BFS DFS 트리 등등을 떠올릴 수 있어야 하는데 그 단계 까지 가진 못했다. 그 동안 배운 자료구조를 풀어서 정리 해봐야겠다... #include #include #include using namespace std; bool visited[1000001]; int main() { ios_base::sync_with_stdio(0); cin.tie(NULL)..

[C++] 백준 1620번 문제풀이

이 문제를 보고 든 생각은 map 이나 vetor를 이용하여 풀어야 겠다 라고 생각하였다. 구현 자체는 어렵지 않았지만 생각해야 할 것이 시간초과를 하지 않게 해야 하는데 vector나 map 을 이용할때 for 문을 가지고 첫번째 요소부터 마지막 요소까지 확인하는 것은 매우 시간(O(N))을 많이 잡아먹는다. 따라서 다른 방법을 찾아야 했는데 map 을 두개 사용하거나 map 하나 또는 배열을 이용하여 푸는 것 이였다 두가지 다 사용하여 풀었으나 여기엔 map 과 배열을 이용한 풀이를 적어놓았다. ios_base::sync_with_stdio(0); cin.tie(NULL); 이 문장을 왜 쓰는줄 몰랐는데 찾아 보니까 C++ 알고리즘을 사용할 때 시간을 줄일 수 있다고 한다. (계속 똑같은 코드여도 위..

[C++] 백준 1463번 문제풀이

이 문제를 보면서 생각했던 점은 2,3 이 나오므로 6의 배수를 고려하여 풀고 입력 받은 수를 나눠가면서 풀자 였다. 그러나 문제를 풀다보니 입력 받은 수를 나눠서 풀기엔 순서를 고려하기 어려웠다 예시에 나온것 처럼 10 -> 9 -> 3-> 1 10 -> 5 -> 4-> 2->1 위와 같이 10에서 바로 2로 나누는것이 아닌 1을 빼고 3으로 나누는것이 연산 수가 적게 나오고 16 -> 8 -> 4 -> 2 -> 1 16 ->15 ->5 -> 4 -> 2 -> 1 위와 같이 16에서 1을 빼고 나누는것이 아닌 바로 2로 나눠서 푸는것이 연산 수가 적게 나왔다. 나눠서 풀기엔 적합하지 않은 문제였다. 그래서 연산을 하면서 풀기로 하였는데 여기서 DP (동적 프로그래밍)을 사용하여서 풀어야 한다는것을 알게..

[C++]백준 1074 번 문제 풀이

처음 문제를 풀때 2차원 배열로 풀려고 했으나 2차원 배열의 크기를 넘어가는 케이스가 있어서 재귀를 사용하여 풀었다. Z방향으로 움직이며 큰 사각형을 4등분하여 Z방향으로 이동하기 때문에 2사분면 -> 1사분면 -> 3사분면 ->4사분면 이런식으로 재귀하게 만들었고 주어진 r,c 와 같으면 count 를 출력하게 하였다. 문제 풀면서 생각해야 할 것 들이 있었는데 1. 어떤 범위내에 있을 때 재귀를 해야하는가 ? 2. Z 방향을 어떻게 표현할 것인가 ? 이 두가지 였다. 첫 번째는 현재 위치를 좌표로 표현했을 때 사각형 내에 r,c 가 좌표로 찍힐 수 있어야 하고 두 번째는 사분면을 이용하여 해결하였다. 재귀와 더 친해져야겠다...(나중에 DFS 문제 풀 때 헷갈리지 않도록) #include #inclu..

프로그래머스 전화번호 목록 문제 풀이

처음 문제를 보았을 때 제일 먼저 생각한것이 phone_book 안에 있는 요소들을 하나씩 비교해서 첫 번째 요소가 다른 요소들의 접두사가 된다면 비교를 끝내고 false 를 return 하고 끝이라고만 생각했다 문제를 풀면서 몇가지 문제들이 있었는데 내가 생각하지 못한 부분은 첫 번째 요소의 size가 요소들중 제일 짧은 요소가 아니란 점 answer 를 true 로 두었을 때 첫 번째 요소만 돌고 끝날 수 있다. 이를 해결하기 위해 첫 번째 요소가 제일 짧은 요소가 되게 sort 함수를 이용 하였고 check 를 사용하여 첫 번째 요소만 돌고 끝내지 않게 하였다. 다른 사람의 풀이를 보았을때 substr를 이용할 수 있었으면 훨씬 빠르고 간결하게 풀 수 있었을 것 같다. 다음 부턴 string을 비교..