인프런 - 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 - 연결된 정점과 비용은 다음과 같이 표..

인프런 - 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 풀이 - 일단 DFS로 탐색을 하려면 경로가 들어있는 map배열과 방문했는지 확인할 수 있는 ch 배열이 필요함 - 여기서는 정점(a)-정점(b) 관계와 비용 c를 map[a][b]=c로 표시한다 - 최소비용을 알기 위해서는 전역변수인 cost를 탐색하면서 작은 값이 나올때마다 바꾸어주어야 한다 - DFS(1, 0)부터 시작하는데 시작정점 1에서 sum=0인 상태로 탐색한다 - 정점이 1~n까지 있기 때..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 5 9 1 2 1 3 1 4 2 1 2 3 2 5 3 4 4 2 4 5 출력예제 1 6 풀이 - 기존 문제에서 행렬이 아닌 벡터를 사용 - map[1].push_back(2) => 1번 인덱스에 2라는 노드가 생겨서 서로 연결 됨 - map[1].size()는 map[1]에 연결되어있는 노드의 수를 나타냄 - map[v][i] ex) map[1][2]이면 map[1]에 연결되어 있는 2라는 정점의 값이 됨 - ch[map[v][i]]가 0이면 해당 ch값을 1로 바꾼 후 DFS호출 => 호출 후 ch를 다시 1로 변..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 0000000 0111110 0001000 1101011 1100001 1101100 1000000 출력예제 1 8 풀이 - 앞서 푼 64번 문제의 격자 형태 변형 문제 - 격자 탐색(상, 하, 좌, 우 탐색) 시 dx, dy 배열을 이용함 - 새로 탐색할 좌표 xx = n+dx[i] , yy= m+dy[i] 이때 상하좌우 4번 탐색하기 때문에 for문은 0~4까지 돌면 된다 - 상하좌우 탐색 시 좌표가 1보다 작아지거나 7보다 커지면 안되기 때문에 continue로 아무 처리 없이 지나가게 한다 - 새로운 좌표인 ..