홍루피의 블로그

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

인프런 - 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로 아무 처리 없이 지나가게 한다 - 새로운 좌표인 ..

알고리즘 2021. 1. 21. 22:02

인프런 - 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 풀이 - v(정점)==n이 될때 종료지점, 이 때가 1에서 n까지 도착한 것이기 때문에 cnt를 증가 - v==n이 아닐때는 각 정점에서 갈 수 있는 정점을 찾는다 - 아직 가지 않았고, 간선이 연결되있는 정점을 찾는다 => ch[i]==0 && map[v][i] ==1 - ch[i]에 1을 넣고 DFS(i) => 끝난 후에는 ch[i]를 0으로 초기화한다 #include #include using namespace std; in..

알고리즘 2021. 1. 20. 22:01