DOTY

어떤 알고리즘인지 모르고 있었지만 이번 기회에 문제를 풀면서 알게 된 알고리즘. 아직은 어떤 타이밍에 이 알고리즘을 써야 하는지 모르지만, 연습하다보면 알게 될것이라 믿는다.....ㅠㅠ 방법은 다음과 같다. 1. 두개의 포인터가 있다. 본인은 front, end로 정한다. 2. 두 포인터중 하나라도 배열의 크기를 넘어가게 되면 그대로 끝! 3-1. 두 포인터의 범위에서 모자라면 end로 범위를 늘려준다. 3-2. 두 포인터의 범위에서 넘치게 되면 front로 범위를 줄여준다. 생각보다 간단한 알고리즘. 그런데 시간복잡도는 O(N)밖에 안된다. 원래대로 하려면 for문을 두개 쓰는 등 해야하는데!!! 빠르자너.....!!! 예시를 들어보자. (초기 : front = 0, end = 0, answer = 9..

programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr BFS, DFS 모두 가능한 문제. 하지만 나는 BFS가 더 좋아서 BFS했음 ㅎㅎㅎㅎㅎㅎ #include #include #include using namespace std; int solution(string begin, string target, vector words) { int answer = 0; int flag = 0; ..

programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있�� programmers.co.kr 까다로워 보이지만 자료 정리만 잘 해놓으면 기본적인 DFS와 다를게 없다. #include #include using namespace std; bool check[200] = {0, }; vector link[200]; void dfs(int x) { check[x] = 1; for(int i = 0; i < link[x].size(); i++) { int y = ..

programmers.co.kr/learn/courses/30/lessons/43165?language=cpp 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 한두 달 전에 시도했다가 포기했던 문제... 설욕전 대성공 ㅎㅎㅎㅎㅎㅎㅎㅎ #include #include using namespace std; int s = 0; int answer = 0; void dfs(int cnt, vector numbers, int target) { if(cnt == nu..

www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 다 풀었다.... 는 통수 딱!!!!! (85% 에서 헤맸다....ㅠㅠㅠ) #include #include using namespace std; vector road; int R, C; int answer = 1; char map[21][21]; bool check[21][21] = {0, }; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; void dfs(..

www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 솔직히 감이 처음에는 안 잡혔지만 결론은 노가다 였다. #include #include #include #include #include using namespace std; queue q; vector v; int map[8][8] = {0, }; int cpy_map[8][8]; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; bool check[8][8] = {0, }; i..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주�� www.acmicpc.net DFS를 연습하고 싶으면 이 문제를 추천한다. 가장 기본적인 DFS 인 듯 싶다. #include #include using namespace std; vector arr[1001]; bool check[1001] = {0, }; int N, M; void dfs(int x) { if(check[x] == 1) { return; }..

https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 흠.... BFS는 좋아.... #include #include using namespace std; queue q; int N, M; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int tomato[1000][1000] = {0, }; bool check [1000][1000] = {0, }; int bfs() { int cnt ..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어�� www.acmicpc.net DFS 사용하는 방법이 아직 너무 미숙한듯 하다.... 어려워....ㅠㅠ #include #include using namespace std; vector com[101]; bool check[100] = {0, }; int cnt = 0; void dfs(int num) { if(check[num]) return; check[num] = true; for(int i = 0; i < com[num]..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net #include #include #include #include using namespace std; int N; int dx[] = {1, 0, -1, 0}; int dy[] = {0, 1, 0, -1}; int map[25][25] = {0, }; bool check[25][25] = {0, }; int vilage(int x, int y) { queue q; int cnt = 0; q.pus..