programming35 [c++]문자열 나누기(string tokenizer) C에서 문자열 나누기 C에서의 문자열 표현은 char 형태의 배열 또는 포인터로 구현된다. 즉 문자열을 표현하기 위한 primitive type이 존재하지 않는다. 에서 제공하는 strtok() 함수를 사용하여 문자열을 구분자를 기준으로 나눌 수 있다. 하지만 strtok는 문자 배열에만 사용이 가능하다는 단점이 있다. 즉 입력으로 고정된 길이의 문자 배열을 받아야 한다. C++에서 문자열 나누기 기본적으로 제공하는 STL 라이브러리는 없고, 직접 구현해서 활용해야 하는 듯하다. (정확하지는 않음.) string STL 이용 void Tokenize(const string & str, vector & tokens, const string & delimiters = " ") { // 맨.. 2017. 12. 1. 외판원 순회문제 백준 2098번 문제이다. 비트마스크와 메모이제이션을 활용하여 해결할 수 있다.문제는 임의의 도시 k에서 시작하여 나머지 도시를 모두 순회한 후 다시 k도시로 돌아가는 거리 중 최소거리를 구하는 것이다. 1. 처음에는 시작 도시별로 모두 다르게 해야하니 n번 for문을 반복해야하나 싶었는데1-2-4-3-12-4-3-1-24-3-1-2-43-1-2-4-3 이 4가지 경우의 가중치가 모두 동일함을 알 수 있다(2의 왼쪽은 1, 오른쪽은 4인 것이 다른 경로에도 동일하게 적용됨)즉 시작 도시를 1로 놓고 풀어도 무방하니 O(N)의 시간복잡도를 없앨 수 있다. 2. 그렇다면 이제 이 문제를 어떻게 작은 문제로 나누는 가에 달려있다. 1번에서 시작하여 순회하는 경우를 생각하자.1-(2,3,4)-1여기서 괄호를 아.. 2017. 10. 26. [boj-1504]특정한 최단경로 dijkstra 알고리즘을 사용하여 최단경로의 길이를 찾는 문제지만,특정 정점 두개(e1, e2)는 반드시 경유해야 함지나갔던 정점이나 간선을 다시 지나갈 수 있음이 두가지 조건이 추가된 문제였다. 시작점이 1이고 n이 도착점일 때, 이 두가지 조건을 만족하는 최단거리를 구해야 하는 것이 이 문제이다.처음에는 단순하게 문제를 3가지 작은 문제로 나누었다. 시작점 1부터 e1까지 dijkstra를 수행하여 e1까지의 최단경로를 찾음e1부터 e2까지 최단경로를 찾음. 이 때 전에 수행한 최단경로의 정보는 사용하지 않는다. 지나갔던 간선이나 정점을 다시 방문할 수 있으니까..마찬가지로 e2부터 도착점 n까지 dijkstra 수행..이렇게 했더니 당연 꽝... 빠뜨린 조건이 있나 이짓 저짓하면서 반례를 찾아보았.. 2017. 7. 31. [graph]위상정렬 위상 정렬이란?DAG(Directed Acyclic Graph), 즉 방향 사이클이 없는 방향그래프에서 노드들의 순서화를 진행하는 것을 말한다. 즉 노드들간의 순서를 정렬한다는 의미이다. 위상정렬 알고리즘첫번째TopologicalSort(G) {for 1 to n{indegree가 0인 임의의 정점 u를 선택A[i] 2017. 7. 25. 이전 1 2 3 4 5 ··· 9 다음