홍루피의 블로그

인프런 - 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",..

알고리즘 2021. 2. 2. 20:46

인프런 - 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. 공주구하기 ..

알고리즘 2021. 2. 1. 17:46

인프런 - 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배열은 단순히 체크의 역할이 아니라 점프 횟수를 누적한다 -..

알고리즘 2021. 1. 29. 22:34

인프런 - 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에서 한번에 갈 수 있는 연결 정점을 탐색한다 (연결리스..

알고리즘 2021. 1. 28. 22:18

인프런 - 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..

알고리즘 2021. 1. 27. 16:46

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

알고리즘 2021. 1. 26. 19:56

인프런 - 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까지 있기 때..

알고리즘 2021. 1. 25. 21:10

인프런 - 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로 변..

알고리즘 2021. 1. 22. 23:25