홍루피의 블로그

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 풀이 - queue를 이용한 BFS 문제 - 좌표 => Struct를 사용해 저장한다. - 상하좌우대각선 => dx, dy 활용해 좌표를 먼저 구한후 배열에 대입한다. - 섬을 발견하면 일단 큐에 넣고 그 섬의 위치는 0으로 만든다. - 그 섬과 연결된 섬을 찾기 위해 상하좌우대각선의 좌표들을 탐색해 큐에 넣는다. 큐에 넣은 후에는 그 위치에 0을 항상 표시해준다. - 큐가 비면 연결된 하나의 섬을 찾았다는 것이고 카운트가 하나 증가한다. #include #include #include using namespace std; int n, map[30][30], cnt=0; int d..

알고리즘 2021. 3. 12. 13:01

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 풀이 - 앞서 풀었던 조합을 이용해서 피자 가게를 선별한다. - 모든 가게를 선별하면 ch배열에 선별한 피자가게 번호가 들어간다. - 이때 레벨은 m과 같아지고 집 선택한 피자가게(m개) 거리를 구하는데 이 중 가장 작은 값을 dis에 저장 한 후 sum에 더한다. - 모든 집의 최소 피자배달거리들이 sum에 저장되고 이 때 sum은 도시의 피자배달거리가 된다. - 한 개 경우(L==m)의 도시의 피자배달거리를 구하면 res와 비교해서 작으면 res를 업데이트 한다. #include #include #include using namespace std; vector hs; vecto..

알고리즘 2021. 3. 10. 19:57

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 풀이 - nCr 조합 구하기 - for문이 s부터 n까지 돈다. => s~n-1까지 가지가 뻗는다. [예시] 6C4의 첫번째 사이클 s=0 => 가지는 0부터 5까지 / L=0 => ch[0]=0; s=1 => 가지는 1부터 5까지 / L=1 => ch[1]=1; s=2 => 가지는 2부터 5까지 / L=2 => ch[2]=2; s=3 => 가지는 3부터 5까지 / L=3 => ch[3]=3; s=4 => L이 r과 같다(nCr에서 r만큼 뽑는다.) => 0, 1, 2, 3 출력 #include #include #include using namespace std; int n, r;..

알고리즘 2021. 3. 8. 21:46

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 풀이 - DFS 문제 + - * / 개수가 주어지는데 이를 사용해서 DFS함수를 작성하는게 제대로 떠오르지 않았다 op[0]>0이면 더하기를 사용해야 한다는 것이고 op[0]--해서 DFS(L+1, res+a[L])로 뻗어 나간다. 배열엔 n-1번까지 수가 들어가기 때문에 종료조건은 L==n일 때이다. (n+1과 혼동 주의) (중요!!) 종료 후엔 op[0]++해서 개수를 복구시켜야 한다. #include #include #include using namespace std; int n, maxi=2147000000, mini=-2147000000; int a[20],op[5]; /..

알고리즘 2021. 3. 5. 17:16

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 풀이 - DFS 문제 - 최대비용을 얻도록 여행날짜까지 상담을 진행해야 한다. - 가지를 뻗을 때 상담 한다 vs 안한다 두가지로 나눈다. - 만약 현재 L+T[L] 즉 현재 날짜의 상담을 완료 한 후의 날짜가 n+1을 넘지 않고 마무리 가능하면 => DFS(L+T[L], sum+P[L]) - L+T[L]이 여행날짜를 넘기면 상담을 하지 않고 다음날짜로 이동하면서 sum을 그대로 넘긴다 => DFS(L+1, sum) - L==n+1일때 sum과 res를 비교해서 resres) res=sum; }else{ if(L+T[L] 상담 한다 DFS(L+1, sum); //안하고 다음날로 넘..

알고리즘 2021. 3. 3. 21:58

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 풀이 - SEND에 있는 4자리 숫자 - MORE에 있는 4자리 숫자 - 두 수를 더해서 5자리 숫자인 MONEY를 만족하는 순열을 찾는다. - 주의해야할 점은 a[2]와 a[6]이 0이면 4자리 수를 만족하지 않기 때문에 이를 체크해서 return 시켜야 한다. - 순열 구할때와 같이 for문을 사용해서 0-9까지 탐색한다. => 체크되지 않았을 시 a[L]에 i값을 넣고 ch[i]=1로 만든 후 DFS(L+1)로 진행 => 계속해서 사용하지 않은 수들로만 순열을 이루게 한다. #include #include #include using namespace std; int a[10]..

알고리즘 2021. 3. 2. 19:36

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 풀이 - 벨만 포드 알고리즘은 해당 정점에 1번만에 갈 수 있는 비용, 2번만에 갈 수 있는 비용 ~ n-1번만에 갈 수 있는 비용을 비교한다. - dist배열을 만들어 놓고 무한대 값(2147000000)으로 초기화 한다. - 시작정점인 dist[s]=0으로 초기화 한 후 for문에 진입 - 총 1~n-1개의 정점을 거치는 경우의 수가 있기 때문에 바깥 for문은 1~n-1까지 돈다. - 각 경우마다 모든 정점을 살펴야 함으로 안쪽 for문은 0~Ed.size()만큼 돈다. - 시작정점, 도착정점, 비용을 다른 변수에 받아 둔 후 이를 가지고 dist배열을 변경한다. => dis..

알고리즘 2021. 2. 25. 20:15

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 풀이 - 다익스트라 알고리즘 - 거리 배열을 사용 - 현재지점까지의 거리 + 새로운 지점까지의 거리 vs 새로운 지점의 거리배열에 있는 거리 => 거리배열에 더 작은 값이 있다면 continue => 아니라면 새로운거리로 배열의 값을 업데이트 하고 큐에 푸시한다. #include #include #include #include using namespace std; //80. 다익스트라 알고리즘 struct Edge{ int vex; //정점 int dis; //거리 Edge(int a, int b){ vex=a; dis=b; }..

알고리즘 2021. 2. 22. 21:32