문제풀이

[프로그래머스 문제풀이] 양과늑대 문제풀이

이 문제가 일반적인 Bfs 와 다른 점은 방문할 수 있는 node 가 하나의 Node와 연결되어있는 인접한 Node 뿐만 아니라 방문했었던 Node들과 인접한 Node들을 방문할 수 있다는 점이다. 또한 Node 수가 17 밖에 안되므로 시간복잡도를 크게 생각하지 않아도 된다는 점이다. 따라서 queue에 방문했었던 Node , sheep , wolf 를 담아 방문했었던 Node들과 인접한 Node들을 방문하면서 양을 최대로 담을 수 있는 경우의 수를 구할 수 있다. 물론 코드를 한 번에 보고 푼건 아니며 처음엔 어떻게 접근해야할지조차 몰라 다른 풀이들을 보며 생각해낸 답안이다. from collections import deque def solution(info, edges): g=[[] for _ i..

[프로그래머스 문제풀이] 배달 문제풀이

문제를 풀 때 Dijkstra 을 풀면 된다. 음수를 표현 #include #include #include using namespace std; int INF = 10000000; vector map[51]; int result[51]; void dijkstra(int start){ result[start] = 0; //짧은거리를 표현하기 위해 priority_queue 사용 priority_queue pq; pq.push(make_pair(start, 0)); while(!pq. empty()){ int n = pq.top().first; int d = -pq.top().second; pq.pop(); //result[n]이 distance면 패스 if(result[n]

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

순열과 조합을 정리 하려 한다. 먼저 , 순열이란 서로 다른 n개중에 r 개를 선택하는 경우의수 ( 순서 상관 있다. ) 조합이란 서로 다른 n개중에서 r개를 선택하는 경우의 수 ( 순서 상관 없다 .) #define n 4 #define r 3 1. 순열 ( 순서 O, 중복 X ) int pArr[r] = { 0, }; bool check[n + 1] = { false, }; //중복 검사 void permutation(int depth){ if(depth == r){ printArray(pArr); return; } for(int i = 1; i

[프로그래머스 문제풀이] 더 맵게 문제풀이

우선순위 큐를 생각하자,, 우선운위큐의 존재만 안다면 쉽게 풀 수 있는 문제였다. vector로 풀었더니 효율성 test를 아예 통과하지 못한다. 우선순위큐 사용 방법 다시 생각하기 #include #include #include using namespace std; int solution(vector scoville, int K) { int answer = 0; priority_queue pq; for(int i=0;i

[프로그래머스] 다음 큰 숫자 문제풀이

bitset 의 존재만 알고 자세히 다루진 못했는데 이 문제를 풀면서 bitset에대해 더 알게 되었다. 다른문제풀이를 보니 계속 2로 나누어서 1의 개수를 세는 문제풀이도 있었고 , biset 의 함수중에 count 라는 함수를 써서 엄청 짧게 푼 문제풀이도 있었다. 많이 알 수록 간단해 지는것 같다. #include #include #include using namespace std; int solution(int n) { int answer = 0; bitset bit(n); string s1 = bit.to_string(); int ones=0; for(int i=0;i

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

동적프로그래밍의 정의를 다시 생각하자 문제를 너무 편협적으로 보지말자, 문제 출제자는 생각보다 너그러울수도있다. #include #include using namespace std; int house[1001][3]; int main() { int N; int cost[3]; house[0][0] = 0; house[0][1] = 0; house[0][2] = 0; cin >> N; cout

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

#include #include #include using namespace std; vectorv[100001]; bool visited[100001]; int max1 = 0; int maxnode = 0; void dfs(int cost, int start) { if (visited[start]) return; visited[start] = true; if (cost > max1) { max1 = cost; maxnode = start; } for (int i = 0; i > N; while (N--) { int..

[C++]2020 KAKAO BLIND RECRUITMENT 2번문제

이 문제는 국어문제가 더 비슷한것 같다 문제만 이해한다면 풀수있을것이다 딱히 중요하게 사용한 것들은 없는거 같다 #include using namespace std; bool check(string str){//올바른 괄호 문자열인가 ? int open=0; int close=0; for(int i=0;i