알고리즘/BOJ 썸네일형 리스트형 1162번 1162번 - 도로 포장 다익스트라를 이용해서 문제를 풀었다. 그런데 어떤 점을 큐에 넣을 때 판단해야 할 점이 하나 더 있었다. 포장한 도로이지 아닌지 여부를 파악해줘야 했다. 다행히 저번에 BFS를 3차원배열을 이용해서 풀었던 문제와 비슷했다. 차원을 하나 더 추가하면서 풀 수 있게 됐다. 기본적인 로직은 다익스트라로, 그 다음 dist 배열에 오면서 몇번이나 포장했는지 여부를 저장하면서 문제를 풀었다. #### 점을 방문했을 때의 상태를 한 차원 더 표현하면 문제가 쉬워질 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656.. 더보기 6118번 6118번 - 숨바꼭질 가중치가 없어서 BFS로 풀 수 있는 문제였다. BFS를 돌린 후, 가장 큰값을 찾고, 갯수를 찾으면 되는 문제. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include#include#includeusing namespace std;int main(){ //freopen("input.txt", "r", stdin); int n, m; cin >> n >> m; vector v(n + 1); vector dist(n + 1,-1); while (m--) { int from, to; cin >> from >> to; v[.. 더보기 1719번 1719번 - 택배 오랜만에 다익스트라를 쓰려고 하니 많이 헷갈렸다. 이 문제는 다익스트라 + 경로 추적이라고 생각. 각 정점마다 다익스트라를 실행하고, p 배열을 이용해서 부모 노드를 저장한다. 최소값을 모두 구하고, 부모노드를 이용해서 처음 방문하는 값들을 구했다. (처음 방문하는 값들의 부모가 시작 노드라는 점을 이용) #### 이 문제를 거의 이틀이나 잡고 있었다. 계속 puts 를 쓰고 있었기 때문이었다... 하 별거 아닌 거로 너무 시간을 쏟았다.. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737.. 더보기 4811번 4811번 - 알약 처음에 쉽게 봤는데 정답률보다 어려웠던 것 같다 체감상.. W와 H의 관계에 대해서 처음에 잘 생각해보고 짜야 했다. 예시에 나와있듯이 엄청 큰 값이 나오므로 long long 형으로 값을 출력해야 한다. 처음에 재귀만 이용해서 완전탐색으로 풀었는데 시간초과가 나와서, DP로 고쳐서 문제를 풀었다. D[w][h] = 알약이 W,H개 남았을 때, 만들 수 있는 글자의 수 로직은 W가 하나 없어지면 H가 하나 증가한다. 그리고 기저 조건으로 W와 H가 결국 0 이 되면 하나의 경우가 생긴다. 이런식으로 다이나믹 프로그래밍을 이용해서 문제를 해결했다. 123456789101112131415161718192021222324252627282930313233343536373839404142434.. 더보기 9997번 9997번 - 폰트 로직. 비트마스크를 이용해서 단어에 어떤 알파벳이 쓰였는지 p 배열에 저장한다. 모든 p배열 전체집합의 부분집합을 구하고, 그 부분집합의 p 배열들의 알파벳 값을 모두 구한다. 그 값이 모든 알파벳이 쓰여진 이진수 (1 더보기 2098번(다시 풀어보기) 2098번 - 외판원 순회 음..TSP 문제를 완전탐색 말고 비트마스크로 연습하려고 풀어봤는데 생각보다 헷갈린다. DP 점화식을 보고 문제를 풀었는데, 코드 짜는 과정에서 실수가 발생했다. 아직 비트마스크 연습이 더 필요하다. ( http://www.qukihub.com/post/traveling-salesperson-problem-tsp 이 블로그를 참고했다. ) D[current][visited] = 현재 위치가 current이고 방문했던 도시들이 visited일 때, 부분 경로(집합)최솟값 으로 놓고 점화식 문제를 풀었다. 기본 로직은 결국 완전탐색은 중복되는게 발생하기 때문에 DP로 풀 수 있다는 점이고, 그 과정에서 방문했던 도시들을 비트마스크로 나타낼 수 있다는 점이었다. TSP 라는 개념 자.. 더보기 1194번 1194번 - 달이 차오른다, 가자 생각해보다가 모르겠어서 결국 다른 분들의 아이디어를 따왔다.. 나는 BFS 라고 하면 자꾸 이차원배열로만 해결하려는 습관이 있었는데, 이 문제를 보면서 깨달음을 얻었다. 차원을 하나 늘려주므로서, 모든 고민거리가 한순가에 해결됐다. 이 문제는 일단, 같은 정점을 여러번 방문할 수 있어야 하는데, 그 조건을 어떻게 할 것인가가 문제였다. 나는 처음에는 BFS를 여러번 돌릴까 생각을 했다. 이차원으로만 하려고 하니, 도저히 풀리지가 않았다. 정점에 방문할 때 어떤 키를 가지고 있는가? 를 기준으로 차원을 늘려서 문제를 풀다보니, 같은 정점을 여러번 방문하는 것에도 문제가 없었다. 또한 열쇠가 6개이므로 열쇠를 가지고 있는지 없는지는 비트마스크를 통해서 해결할 수 있었다. .. 더보기 1157번 1157번 - 단어 공부 로직은 1.단어 갯수 세기2.max 값 찾기3.max 값 여러개인지 찾기4.max 값 출력 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include#includeusing namespace std; int alpha[26];int main(){ string s; cin >> s; for (int i = 0; i = 'a' && s[i] = 'A' && s[i] 더보기 이전 1 ··· 10 11 12 13 14 15 16 ··· 40 다음
