본문 바로가기

Programming Problems

(64)
스트링이 주어진 패턴을 반복하는지 확인하기 주어진 패턴을 주어진 스트링이 따르는지 확인한다.패턴 : abba , 스트링 : redbluebluered >> 1패턴 : aaaa, 스트링 : asdasdasdasd >> 0 나이브 솔루션 :패턴 첫 글자를 매칭해서 맵에 넣는다(임의로 잘른 모든 경우에 대해). 그리고 남은 스트링과 패턴에 대해 같은 작업을 반복한다.남은 스트링이 없는데 패턴이 남으면 0 리턴, 다음 패턴이 이미 있는 패턴이면 그걸 적용해 보고 안되면 0. 스트링과 패턴이 전부 0이면 그때 1최악의 경우 O(N^N) 이런거 막 나올수 있겠다. 가능은 함. bool isMatch(string str, int iStr, string ptn, int iPtn, unordered_map &hmap){ if(iStr == str.size() &..
연속된 숫자 배열이 주어졌을 때, 숫자로 만든 합의 최소는? ex ) 1 2 7 8 9 의 최소합은 129+78 (순서 바꾸기 가능) 나이브 솔루션 : 그냥 두 집합으로 쪼갠 후에 합을 구해 최소를 찾는다 > 각 합을 만드는 시간 O(N), 갯수 : 2^NO(N2^N) 솔루션 성질을 더 이용해 보자. DP 하기에는 성질을 너무 많이 사용하고 앞의 값을 재활용하기 어렵다(?) 아닌데. 앞의 최소합이 있으면 새로운 원소가 들어오는 경우 둘 중 더 작은 값으로 가야하지 않나? 엌 greedy 방법이 여기잉네된다. greedy. 나머지가 이미 최소값인 조합으로 구성되어 있기 때문에, 새로운 숫자를 더 작은쪽에 붙이면 된다. 알고리즘뒤에서부터 숫자를 만들어 나간다. 그때그때 대소비교를 O(1)에 할 수 있도록 알고리즘을 짜면작은 쪽의 맨 앞에 숫자를 append 하면 된다..
String에서 repeating subsequence 존재 여부 찾기 string에서 repeating subsequence를 찾아보자.예)abab : sub "abab"가 반복하는 subs이다.abba : 없음azcaxc : "acac" 가 반복한다. 풀이 ) bool hasrepeat(string s){for(int i = 1 ; i
네트워크 증폭 최소화 문제 ( 다익스트라 최소경로 곱셈 ) 12345678910111213141516171819202122double findmin(vector & graph) { vector dist(graph.size(), 999999999); priority_queue q; dist[0] = 1; q.push(pair(1, 0)); while (q.size() != 0) { int curr = q.top().second; double currd = q.top().first; q.pop(); if (currd > dist[curr]) continue; // check adjacent elements for (int i = 0; i currd*nd) { dist[n] = currd * nd; q.push(pair(dist[n], n)); } } } return..
배열 스왑해서 정렬하기 (BFS 응용) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127#include "stdafx.h"#include #include #include #include #include #include #include #include using namespace std; void makeBFS(..
끝말잇기 문제 (오일러 경로) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122#include "stdafx.h"#include #include #include #include #include #include using namespace std; void DFS(vector & graph, vector &visited, int ..
DFS로 보드 길 찾기(그래프 변환) 123456789101112131415161718192021222324252627282930313233343536bool findpath(vector & board) { // make graph vector graph(board.size()*board[0].size(), vector()); int count = 0; for (int i = 0; i
DAG topological sort 응용문제 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748void IDFS(vector & graph, vector & visited, stack & res, int target) { visited[target] = true; for (int i = 0; i