g1embed

네트워크에 연결된 컴퓨터 중, 1번 컴퓨터로 인해 바이러스가 전파된 컴퓨터의 수를 구하는 문제입니다. 유의할 점은 데이터를 받으며 그래프 정보를 입력 시 양방향으로 입력해주는 것과, Queue에 Push할 때 방문처리를 해주는 것입니다. 1. 그래프 입력 2. 시작 노드 Push 후 방문처리 3. BFS : 2차원 배열 BFS와는 다르게 갈 수 있는 방향이 그래프에 연결되 노드의 개수만큼 있습니다. 방문 후 Push 될 경우 감염된 컴퓨터의 수를 증가시키며, 1번 컴퓨터는 세지 않기 때문에 0부터 시작합니다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; queue q; vector com[1..

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, - 버튼을 이용해 특정 채널로 이동하려고 할 때 망가지지 않은 버튼을 이용해 이동하려면 최소 몇 번 버튼을 눌러야 하는지 계산하는 문제입니다. 유의해야 할 점은, 목표 채널로 이동하기 위해 숫자를 누르지 않는 것이 빠를 수 있다는 점입니다. 또한, 목표채널 N이 어디에 존재할 지 모르므로 뺄셈 연산 후 절대값을 취해줘야 함을 잊지 말아야 합니다. 1. 모든 번호를 Brute Force 로 탐색(0 에서 500000까지의 N 이 존재하지만, 이동할 수 있는 채널의 제한은 없으므로 1000000 까지의 채널을 탐색하도록 합니다. 망가진 버튼이 무엇인가에 따라 N 범위를 벗어난 채널에서 이동하는 것이 더 빠를 수 있습니다. 2. 고른 채널을 숫자를 눌..

부등호를 입력받으면 그 사이에 들어갈 수들을 붙여놓은 것 중 가장 큰 수와 작은 수를 찾아내는 문제입니다. 처음에 접근한 방식은 모든 경우의 수를 찾고 부등호에 대한 조건은 모든 수를 선택한 후에 알아보도록 하는 것이었습니다. 보통 재귀를 설계하는 방식처럼 final condition을 먼저 명시하였고, 이후에는 0에서 9까지의 반복문 안에서 check 배열을 넣었다가 풀며 재귀를 돌렸습니다. #define _CRT_SECURE_NO_WARNINGS #include #include #include /* 부등호 */ using namespace std; char a[15], check[15]; int k; vector ans; string to_string(int i) { char j = i + '0'; ..

완전탐색 대신 투포인터 (two pointers) 알고리즘 활용 입력: N: 데이터 수 M: 구간의 합과 비교해볼 값 ㅁㅁㅁㅁㅁ: N개의 데이터 각 'ㅁ' 마다 데이터가 들어오는 칸이라고 생각하면, 들어온 값들의 합이 M과 일치할 수 있는 '경우의 수'를 구해야 합니다. ㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁㅁ 위 예시와 같이 밑줄친 곳과 중앙선이 그어진 곳 모두 합이 M과 일치할 수 있습니다. 시간복잡도를 낮추기 위해 두 개의 포인터를 활용해 front 와 back의 위치에 대해 알고 있도록 합니다. 주의할 점은, 합이 M 보다 클 때 front에 해당하는 값을 한 번 지워서는 M과 일치할 수도 있는 합을 놓칠수도 있다는 것입니다. 이 부분은 테스트케이스에 나와있지 않아 틀리기 쉽습니다. #include /* 수들의 합..