문제 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[i][..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 5 3 출력예제 1 10 풀이 - 조합을 구하는 문제 , 팩토리얼을 약간 변형하면 된다 - 공식이용 : nCr = n-1Cr-1 + n-1Cr - 메모이제이션을 이용하는데 DFS로 구해놓은 값을 dy[n][r]에 저장한다 => 미리 저장해 놓으면 해당 배열 값이 필요할 때 따로 구하지 않고 바로 return하면 된다(더 효율적임) #include #include #include #include using namespace std; int dy[21][21]; //76. 이항계수(조합)(메모이제이션) //nCr=n-1..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 6 50 2 20 1 40 2 60 3 30 3 30 1 출력예제 1 150 풀이 - 남아있는 날짜가 많은 것 부터 스케쥴링 하는 것이 이 문제의 핵심 - money, when을 구조체로 만들어서 벡터에 넣어준 후 operator정렬기준에 따라 남아있는 날짜가 많은 순으로 정렬한다 (money는 정렬과 상관X) 정렬 전 정렬 후 50 2 60 3 20 1 30 3 40 2 50 2 60 3 40 2 30 3 20 1 30 1 30 1 - 3일 => 60과 30중 큰 수인 60을 res에 더함 - 2일 => 위에서 남..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 5 3 6 0 5 0 2 4 0 -1 출력예제 1 3 5 2 풀이 - PriorityQueue는 기본적으로 최대힙 구조를 지원 => 최소힙으로 만들려면 어떤 방식을 사용해야하는지가 중요함 - 6>5이지만 -를 붙이면 -6 이를 이용해 큐에 넣을때 -로 푸쉬하고 출력할때 -를 붙여서 출력하면 원래값을 얻을 수 있다. #include #include #include using namespace std; //74. 최소힙 (우선순위 큐) //부모노드의 값이 왼쪽 자식과 오른쪽 자식보다 작아야함 => 가장작은 값이 루트에 ..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 5 3 6 0 5 0 2 4 0 -1 출력예제 1 6 5 5 풀이 - 우선순위 큐를 이용한 최대힙 구조 만드는 문제 - 무조건 부모가 자식보다 큰 값을 가져야 한다 => 우선순위 큐가 자식노드에 부모노드보다 큰 값이 들어오면 위치를 바꿔준다 - top을 출력하면 현재의 루트노드가 출력된다 #include #include #include using namespace std; //73. 최대힙 (우선순위 큐) int main(){ int a; priority_queue pQ; while(true){ scanf("%d",..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 8 3 출력예제 1 7 풀이 - k라는 수를 외친 왕자가 나간다 - 가장 문제가 되는 건 큐는 선입선출인데 3번째 왕자를 뺄 때 1,2번 왕자를 다시 넣어줘야 하는 점이다. - for문이 돌면서 1,2번을 큐의 뒤쪽에 넣어준 후 pop으로 빼준다 - 3번이 되면 뒤에 넣지 않고 그냥 pop으로 빼준다 - Q의 사이즈가 1이 되면 정답이므로 출력한다 => 출력후 pop하면 Q.empty()가 되어 끝나게 된다. #include #include #include using namespace std; //72. 공주구하기 ..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 5 14 출력예제 1 3 풀이 - 1, -1, 5만큼 좌표 이동이 가능하다 =>봉우리 문제 처럼 특정 방향이나 좌표로 이동할 땐 pos변수를 잡고 배열에 이동방향을 명시해서 가면 된다 =>이때 -1이나 10001 같은 유효하지 않은 좌표로 갈 경우에 continue를 사용해서 막아주는 것이 필요하다 - s위치에서 한번에 갈 수 있는 정점을 찾는다 => 5면 6, 4, 10을 탐색 - 해당 위치가 endpoint랑 같으면 ch[x]를 출력한다 => 여기서 ch배열은 단순히 체크의 역할이 아니라 점프 횟수를 누적한다 -..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 6 9 1 3 1 4 2 1 2 5 3 4 4 5 4 6 6 2 6 5 출력예제 1 2 : 3 3 : 1 4 : 1 5 : 2 6 : 2 풀이 - 1번 정점부터 n번 정점까지 최소로 갈 수 있는 횟수를 찾는다(2~n번까지 출력) - distance 배열을 사용하는것이 핵심 - 1번에서 출발하기 때문에 2번부터 구하면 된다. 1번은 미리 큐에 넣어놓고 ch[1]=1로 만든다 - x변수는 항상 큐의 front값을 가지고, x에 값을 담은 후에 큐에서 빠진다. - x에서 한번에 갈 수 있는 연결 정점을 탐색한다 (연결리스..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 1 2 1 3 2 4 2 5 3 6 3 7 출력예제 1 1 2 3 4 5 6 7 풀이 - 큐를 배열로 구현(선입선출 구조, 먼저 들어온것이 먼저 나감 스택: 후입선출) - front와 back을 이용한다 (둘 다 -1로 초기화) * front: back을 따라가며 하나씩 출력함 * back: 해당 정점에 연결된 정점을 배열에 넣어줌 Q[0]=1; ch[1]=1; 을 해준 후 시작 (back = 0, front = -1인 상태) while(front front가 back을 따라가면서 출력하기 때문에 front는 bac..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 5 8 1 2 12 1 3 6 1 4 10 2 3 2 2 5 2 3 4 3 4 2 2 4 5 5 출력예제 1 13 풀이 - 기존 인접리스트 형태와 비슷하나 pair를 사용해 2개의 값을 함께 연결한다 * pair pair 선언: pair 변수명 pair 만들기: make_pair(a, b) pair를 가지는 vector 만들기: vector 벡터 이름 (>>는 쉬프트 연산자와 겹치므로 한칸 띄워줘야 함) pair 값에 접근하기 : 첫번째 값 first, 두번째 값 second - 연결된 정점과 비용은 다음과 같이 표..