완전탐색 (6) 썸네일형 리스트형 [SW Expert Academy] 길찾기 길찾기 SW Expert Academy는 문제 복제가 금지되어 있기 때문에 링크로 대체하겠습니다. 어떻게 풀까? 대표적인 DFS / BFS 문제입니다.저 같은 경우는 그냥 시작점에서 큐를 돌려서 BFS를 이용해서 풀었습니다! 0번 노드에서 시작해서 0번 노드에서 이어지는 노드들을 모두 큐에 넣은 후에 방문 했다는 것을 체크해 둡니다.만약, 99번 노드가 나온다면 바로 연결되어있다는 것으로 끝내주면 됩니다.하지만 큐가 빌 때까지 99번 노드를 찾을 수 없다면, 시작 노드에서 끝 노드로 갈 수 없다는 것이 될 것입니다! 문제를 하나 풀어보겠습니다. 큐에 시작점인 0을 넣고, 0번을 방문 했다고 체크 합니다. 큐의 가장 위에 있는 0번 노드가 시작 노드가 됩니다.0번 노드가 가리키는 1번과 2번 노드를 큐에 .. [완전탐색/부분집합] 비트를 이용하여 모든 부분집합을 구하자! 부분 집합이란 전체의 집합에서 하나의 원소를 '고른다 / 안 고른다' 두 가지의 경우에 대해 살펴보는 것이므로 2^n 가지의 경우가 나옵니다. 이는 비트를 이용하면 굉장히 쉽게 구할 수 있습니다! 왜냐하면 비트는 이진수이기 때문에, 하나의 자리수마다 고른다 (1) / 안 고른다(0)을 설정할 수 있기 때문입니다! 우선 코드를 보겠습니다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950 #include#include#include int arr[10]; void print(int bit){ int idx = 0; while (bit) { if (bit & 1) { printf("%d ", a.. [완전탐색/순열] 재귀 함수로 순열을 짜보자! (크기 순서로) 재귀함수를 통해 순열을 짜는 방법을 알아보겠습니다.우선 예제로 주어진 수가 1 2 3 4 5일 때 을 구해봅시다. 어떻게하면 순열을 구할 수 있을까요? 바로, 앞의 3 자리를 순열의 결과로 보는 것입니다.보통 결과를 앞에 3자리에 위치시키기 위해 크게 2가지 방법이 있습니다. 1. swap을 이용한 방법2. 오른쪽으로 한칸씩 원형 회전 시키는 방법 1번의 경우에는 순열을 구하는 순서가 상관이 없을 때 사용합니다.2번의 경우는 순열을 구하는 순서가 정해져 있는 경우입니다. (특히 크기 순서로) 1번을 예로 보겠습니다.1 2 3 4 5가 있을 때,맨 앞자리를 처음에는 1로 한다.그리고 다음 2번째 수를 2로 하고,3번째 수를 3으로 하면, 1 2 3 순열이 만들어집니다.이제 3과 4를 swap해서 1 2 4.. [완전탐색] 완전탐색에 대해 알아보자 완.전.탐.색! 말 그대로 무식하게 모든 경우를 다 보는 것입니다!컴퓨터의 가장 강한 이점인 '속도'를 극한으로 이용할 수 있는 방법입니다.보통 완전 탐색은 최적화 문제에서 많이 사용합니다.최적화 문제란, 여러가지 경우를 만들 수 있을 때, 가장 적합한 답의 경우를 구하는 문제를 말합니다.예를 들면, 마을 사이를 잇는 도로가 있고 도로마다 거리가 다를 때, A에서 B로 가는데 가장 짧은 도로의 길이를 구하는 문제가 있습니다.이와 같은 문제를 풀 때 완전탐색을 이용하면 A에서 B로 가는 모든 도로의 경우를 구한 뒤에 그 중 거리가 가장 짧은 값을 답으로 선정합니다.물론, 완전탐색을 이용해서 문제를 풀기 위해서는 문제의 조건에서 주어진 시간 내에 풀 수 있을지 잘 생각해보아야 합니다.완전탐색을 너무 많이하면.. [알고스팟] CLOCKSYNC 링크 : https://algospot.com/judge/problem/read/CLOCKSYNC 문제 ID시간 제한메모리 제한제출 횟수정답 횟수 (비율)CLOCKSYNC10000ms65536kb68852724 (39%) 문제그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시, 혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로, 각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다. 한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다. 스위치들과 그들이 연결된 시계들의 목록은 다음과.. [완전탐색/조합] 비트 연산을 이용하여 조합 만들기 - 비트 조합 예전에 대학생활을 하면서 '로봇 연구회' 동아리 활동을 하면서 아트메가 128을 사용했기 때문에 비트연산을 이용한 경험이 있습니다. 덕분에 프로그래밍을 하면서 비트를 이용해서 문제를 해결한 적이 있는데, 이번에는 그 중에서도 특히 인상 깊었던 '조합 만드는 법'에 대해서 설명하려고 합니다! 우선, 그 전에 비트 연산에 대해서 간단히 알아봅시다. 1. & : 비트 AND 연산. 비트마다 AND 연산을 해서 두 비트가 모두 1일 경우에 1 그 외에는 0이 됩니다. ex) 0b 1111 & 0b 0011 = 0b 0011 2. | : 비트 OR 연산. 비트마다 OR 연산을 해서 두 비트중 하나라도 1일 경우에 1 그 외에는 0이 됩니다.ex) 0b 1100 | 0b 1010 = 0b 1110 3. ~ : 모든.. 이전 1 다음
