컴퓨터비전, 알고리즘 공부 끄적

문제 : https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 오늘 푼 문제는 입력받은 사람 두명의 촌수를 계산하는 문제. 난 항상 로보트처럼 visit를 bool로 놓고 푸는 경향이 있었는데 이번 문제는 따로 count 변수를 만들지 않고 visit로 바로 계산을 하니 더 더 더 편했다. #include #include using namespace std; int n, m; int p1, p2; const int MAX = 10..

문제 : https://www.acmicpc.net/status?user_id=tngus2373a&problem_id=7569&from_mine=1 채점 현황 www.acmicpc.net 오늘 푼 문제는 3차원 토마토..! 원래도 BFS의 대표문제가 토마토인건 알고 있었지만 3차원이라 살짝 당황했다. 3차원 문제도 분명히 예전엔 몇번 풀었는데, 오늘 처음 풀려니까 땀이 삐질,, 여러군데에서 동시에 BFS를 돌리는 방법을 살짝 헤매다가 for문 돌 때마다 BFS를 돌리는게 아니라 그때마다 큐에 좌표를 추가해주고 한 방에 BFS 돌리면 된다는 것을 깨달은 오늘 :) #include #include #include #include using namespace std; int M, N, H; const int ..

문제 : https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 오늘은~~ 오랜만에 다시 프로그래머스 말고 백준을 풀었당 단지번호 붙이기를 풀었는데 오늘은 다시 감도 익혔겠다 아무것도 참고하지 않고 풀었다. BFS 들어갈때 첫 인덱스를 visit에 true 안해준 실수 고쳤더니 바로 성공 ヾ(•ω•`)oヾ(•ω•`)o 다 풀고 보니까 예전에 이 문제를 풀었을 땐 DFS로 풀었더라 크크 #include #include #include #include #i..

문제 : https://programmers.co.kr/learn/courses/30/lessons/43162# 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 이 문제는 그냥 일반적인 DFS로 풀었더니 금방 풀렸당 BFS로도 풀 수 있을 것 같지만 나는 DFS로 풀었당 히히 #include #include using namespace std; bool visit[201]; void DFS(int idx, vector computers, int n) { for(int i=0; i

문제 : https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 오랜만에 카페와서 백준 풀려고했더니 노트북에서 비주얼스튜디오가 자꾸 튕긴다 ,, ㅠ ㅠ 그래서 오늘은 웹에서 바로 푸는 프로그래머스를 풀었다 := numbers.size()) { if(sum == target) { cnt++; } return; } DFS(idx+1, numbers, sum+numbe..

문제 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 어제 풀었던 바이러스 문제를 오늘은 DFS로 풀어보았다. 두 가지 다 가능한 문제는 DFS로 푸는게 더 간단한 것 같다(수피셜 ㅎㅎ;) #include using namespace std; int N, M; const int MAX = 101; int graph[MAX][MAX]; bool visit[MAX]; int cnt = 0; void DFS(int idx) { //신종 바이러스인 웜 ..

문제 : https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 이 문제는 DFS와 BFS 두 방법 모두로 풀 수 있는 문제다. 나는 이전에 내가 풀었던 코드를 참고하지 않고 BFS로 문제를 풀었고 한 방에 성공! 다 풀고나서 예전에 풀었던 코드를 봐보니 graph 대신 2차원 벡터사용해서 map을 사용한 DFS로 문제를 풀었었다. 내일은 같은문제를 DFS로 풀어봐야지. #include #include using namespace std; int N, M;..

문제 : https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 처음엔 DFS와 BFS 두 가지 방법으로 풀어보려고 했으나, 이 미로탐색 문제처럼 최단거리를 탐색하는 문제는 DFS로 풀면 모든 경로를 확인하기 때문에 시간초과가 난다. 그래서 최단거리 탐색은 BFS 방법으로 풀기로 한다!! 요새는 딥러닝 코딩만 해서 python이 익숙하지만 예전에 알고리즘은 항상 C++로 했었어서 C++로 다시 시작했다. 오랜만에 알고리즘 문제를 다시 풀어보니, 기억이 새록새록 나긴 하지만 예전에 쓰..

문제 : https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 보통 DFS는 스택, 재귀 BFS는 큐 를 통해 문제를 풀 수 있다. #include #include using namespace std; int N, M, V; const int MAX = 1001; int graph[MAX][MAX]; bool visit[MAX]; queue q; //문제 //그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를..