멀티탭의 잡다한 이야기

문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자..

문제 숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오. 예시 입력 더보기 5 6 3 2 10 -10 8 10 9 -5 2 3 4 5 -10 예시 출력 더보기 1 0 0 1 1 0 0 1 아이디어 이진탐색 알고리즘 이진 탐색 STL를 사용해 구현시간을 줄이자 소스코드 //소스코드 #include using namespace std; int N, M; vector Narr, Marr; int main() { int temp; cin >> N; for (int i = 0; i > temp; Narr.push_back(tem..

문제 친구로부터 노트북을 중고로 산 스브러스는 노트북을 켜자마자 경악할 수밖에 없었다. 바탕화면에 온갖 파일들이 정리도 안 된 채 가득했기 때문이다. 그리고 화면의 구석에서 친구의 메시지를 확인할 수 있었다. 바탕화면의 파일들에는 값진 보물에 대한 정보가 들어 있어. 하나라도 지우게 된다면 보물은 물론이고 다시는 노트북을 쓸 수 없게 될 거야. 파일들을 잘 분석해서 보물의 주인공이 될 수 있길 바랄게. 힌트는 “확장자”야. 화가 났던 스브러스는 보물 이야기에 금세 화가 풀렸고 보물의 정보를 알아내려고 애썼다. 하지만 파일이 너무 많은 탓에 이내 포기했고 보물의 절반을 보상으로 파일의 정리를 요청해왔다. 스브러스의 요청은 다음과 같다. 파일을 확장자 별로 정리해서 몇 개씩 있는지 알려줘 보기 편하게 확장자..

문제 2개의 문자열 s와 t가 주어졌을 때 s가 t의 부분 문자열인지 판단하는 프로그램을 작성하라. 부분 문자열을 가지고 있는지 판단하는 방법은 t에서 몇 개의 문자를 제거하고 이를 순서를 바꾸지 않고 합쳤을 경우 s가 되는 경우를 이야기 한다. 예시 입력 sequence subsequence person compression VERDI vivaVittorioEmanueleReDiItalia caseDoesMatter CaseDoesMatter 예시 출력 Yes No Yes No 아이디어 주어진 전체 입력에서 검색어의 문자열 순서대로 검색이 된다면 Yes 아니면 No 알고리즘 검색할 문자의 문자 순서대로 전체 문자열에서 매칭이 되는대로 idx를 1씩올린다. 모든 검색이 끝난후 idx의 수가 검색할 문자열..

문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 예시 입력 5 5 3 5 4 5 2 1 2 3 4 3 1 예시 출력 3 1 2 5 4 3 1 4 2 5 아이디어 대놓고 DFS / BFS 알고리즘 DFS / BFS 소스코드 #include #define ALL 1010 using namespace std; bool visitedDFS[ALL]; vector DFSNode[ALL]; bool visitedBFS[ALL]; vector BFSNode[ALL]; int N, M, V; void ..

문제 초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작성하시오. 예시 입력 7 8 0 1 3 1 1 7 0 7 6 1 7 1 0 3 7 0 4 2 0 1 1 1 1 1 예시 출력 NO NO YES 아이디어 대놓고 유니온 파인드 알고리즘 유니온 파인드 소스코드 #include using namespace std; int N, M; int parent[1000010]; int order[100010][3]; int find(int x) { if (parent[x] == x) return x; return parent[x] = find(pare..

문제 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 있다. 문자열의 시작과 끝은 공백이 아니다. ''가 문자열에 있는 경우 번갈아가면서 등장하며, '

유니온 파인드 뼈대 코드 int parent[9]; int find(int x) { //부모노드 찾기 if (parent[x] == x)//인덱스 값이 같다면 리턴 return x; //인덱스 값 리턴 return parent[x] = find(parent[x]); } ///유니온 파인드 뼈대 코드 void merge(int x, int y) { //두 집합을 합치는 기능 x = find(x); y = find(y); if (x == y) return; parent[y] = x; } //두 집합이 서로 같은 집합인지 확인 bool isUnion(int x, int y) { x = find(x); y = find(y); if (x == y) return true; return false; } 집합성 문제 ..

DFS,BFS 뼈대 코드 //DFS 뼈대코드 //스택을 이용 bool visited[N]; vector graph[N]; void dfs(int x) { visited[x] = true; for (int i = 0; i < graph.size(), i++) { int y = graph[x][i]; if (!visited[y]) dfs(y); } }//BFS의 뼈대 코드 //Queue를 이용 #include bool visited[N]; vector graph[N]; void bfs(int start) { queue q; q.push(start); visited[start] = true; while (!q.empty()) { int x = q.front(); q.pop(); for (int i = 0; i..

특정 문자열 검색하기 https://www.acmicpc.net/problem/6550 문자열 정렬 https://www.acmicpc.net/problem/20291 https://www.acmicpc.net/problem/17413 https://www.acmicpc.net/problem/20210 문자열 조건 따지기 https://www.acmicpc.net/problem/17609 https://www.acmicpc.net/problem/20437