본문 바로가기

코딩/알고리즘

 (67)
백준 10451 순열사이클 이 문제의 특징은 '어떠한 노드 s를 목적지로 하는 노드는 1개, 이 s 노드에서 시작하는 노드도 1개'라는 것이다. 이걸 전문용어로 뭐라 있을거 같은데 흠.. 여튼, 그렇기 때문에 bfs같은 탐색을 할 필요 없이 선형으로 탐색하면 된다. 첫번째 반복문은 아직 탐색하지 않은 루트 노드를 선택하는데 쓰고 두번째 반복문은 이 노드로부터 시작하는 사이클을 찾는데 쓴다 탐색을 하다가 이미 방문한 노드를 발견하면 주저없이 반복문을 끝내고 사이클의 갯수를 1증가 시키면 된다. 왜냐하면 위에서 말한 특징 때문에 '이미 탐색한 노드 x를 지금 탐색하였다면 그 x노드는 탐색을 시작했던 노드'라는 명제가 성립하기 때문. #include #include #include #include #include #include usi..
백준 1325 효율적인 해킹 여타 다른 BFS 문제처럼 각 노드별로 그 노드에서 도달할 수 있는 노드의 갯수를 계산해서 최대값을 가진 노드(들)을 출력하면 되는 문제이다. 그런데 이 문제는 4가지의 특징을 가지고 있다. 1. 메모리 평소에 하듯이 adj 배열을 2차원 배열로 선언해버리면 10000 * 10000 * 4byte = 381MB의 메모리를 먹고 short를 써도 190MB를 먹는다 따라서 가변 배열을 써야 한다. 링크는 10만개로 한정되어 있으니 가변 배열을 쓸 경우 100,000 * 4byte라서 1메가도 안된다. 2. 방향그래프 이 그래프는 다른 문제와 다르게 방향 그래프이다 "A가 B를 신뢰한다" 라는 문장은 B->A 와 동치이다. 이것을 유념해두고 문제를 풀어야 한다. 3. 입력 만약 cin으로 입력을 받으면 입력..
백준 1890 점프 혹시 백준에서 채점 돌렸는데 잘 맞추다가 후반부에서 오답나오신분이시라면 결과 출력을 long long으로 했는지 체크하세용 저도 첨에 long long 박아놨다가 막판 출력을 int로 하는 바람에 형번환 되서 한번 틀렸네요 ㅎㅎ BFS문제 풀려고 BFS 눌렸는데 왠 DP문제가 떠서 그냥 풀었다 r만큼 떨어져있는 노드에서 r만큼의 점프가 가능한지 검사하여 가능할 경우 해당 노드까지 도달할 수 있는 경로의 수를 더하는 알고리즘이다 점화식은 아래와 같다. D[i][j] = D[i-r][j] + D[i][j-r], r = [1..9] (if arr[i-r][j] == r, arr[i][j-r] == r) DP는 점화식만 세우면 빠르게 모델링하여 풀수 있다. #include #include #include #in..
백준 10216 Count Circle Groups 노드별로 거리를 계산하고 서로가 통신거리 이내에 있는 노드라면 두 노드를 이어준다( = adj 에 추가한다) 그 후 모든 노드가 탐색될 때 까지 BFS탐색을 여러번 진행하면서 그래프가 몇개 있는지 계산한다. #define getDist(x0,y0,x1,y1) ((x0-x1)*(x0-x1)+(y0-y1)*(y0-y1)) #define dbl(r) (r*r) #include #include #include #include #include #include using namespace std; int testcases; int N; int enemy[3001][3]; bool isVisit[3001]; int enemyNum; int adj[3001][3001]; int adjSize[3001]; int mai..
백준 2667 단지번호 붙이기 2차원 배열을 0,0부터 순차적으로 탐색하다가 집을 만나면 그 집을 루트로 하여 BFS를 시작한다 이 문제에서 약간 다른점은 굳이 isVisit를 쓸 필요가 없다는 것이다. arr[i][j]에서 이미 단지 번호를 붙였고 단지 번호가 붙여져있다는 것은 이미 방문했다는 뜻이니까 isVisit로 방문한지 체크하지 않고 단지 번호가 붙여져있는 것으로 방문한지 체크하면 되기 때문 그 외에 단지 번호를 0부터 붙이고 싶어서 빈땅, 집이 있지만 단지 번호가 붙여지지 않은 집, 단지 번호가 붙여진 집 을 서로 구분하기 위해서 입력을 받을때 0과 1로 받지 않고 -2와 -1로 받았다. #include #include #include #include #include #include using namespace std; i..
[python3] 백준 2739 구구단 숏코딩 python3으로 짰다. 별거 아니지만 숏코딩 순위권... 심심해서 했다n=int(input()) for a in range(1,10):print(n,"*",a,"=",n*a)
백준 2606 바이러스 1번 컴퓨터를 루트로 하여 BFS탐색을 하면서 처음 방문하는 노드의 갯수를 새면 끝 adj 배열을 만들때 머가 가장 빠르고 메모리도 적당할까~ 생각해봤는데, 배열은 벡터가 아닌 2차원 배열을 쓰고 각 노드별로 연결된 링크의 갯수를 미리 저장하면 adj의 자료구조로 링크드리스트를 쓸때의 장점과 배열을 쓸때의 장점을 둘 다 가져올거 같아서 이렇게 활용해 보았다. 괜찮은듯. #include #include #include #include #include using namespace std; int adj[101][101]; int adjSize[101]; int computerNum; int linkNum; bool isVisit[101]; int main() { cin >> computerNum; cin >..
백준 2178 미로 이것도 BFS문제다. 루트가 (0,0)인 그래프에서 노드 (N,M)의 깊이를 구하는 문제로 모델링이 가능하다. 한편, 백준 7576 : 토마토(http://deque.tistory.com/38) 문제와 다른점은 시작점이 하나이기 때문에 지금 방문한 노드의 깊이가 최적화 되어 있는 지에 대한 검사를 하지 않아도 된다. #define INT_MAX_ 2147480000 #include #include #include #include #include using namespace std; int N, M; int arr[101][101]; bool isVisit[101][101]; int di[4] = { -1, 0, 1, 0}; int dj[4] = { 0, +1, 0, -1}; int main() { cin..

티스토리툴바