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

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

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 풀이 - 순열 경우의 수를 DFS로 구현 - A배열에 들어있는 원소들을 n개의 가지로 뻗어나가면서 방문한다. => 이때 ch가 1이면 방문한 것이므로 제외하고 방문하지 않았을 시 res[L](경로 출력위함)에 a[i]값을 넣고 ch[i]=1로 바꾼다. => DFS(L+1)로 다음레벨로 내려간다. => 한 경로가 끝난후에 (L==r) 레벨별로 방문한 정점을 담아놓은 res배열을 출력하고, 경로의 개수를 +1한다. => 그 이후 puts("")로 행을 바꿔준다. => DFS 함수가 끝난 후 경로 개수 cnt를 출력한다. #inclu..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개 풀이 - 최소비용스패닝 트리 구성 - 노드를 한개씩 추가해가면서 그 노드들에 인접한 간선들에 대한 비용을 우선순위큐에 넣는다. - 우선순위큐는 최소힙 구조로 원소를 하나씩 팝하면서 들어온 비용 중 가장 작은 비용을 res에 더한다. - 간선의 연결정보는 무방향그래프이기 때문에 vector를 이용해서 연결정보를 저장한다. - 한번 방문한 정점은 간선의 값이 최소여도 방문하면 안되기 때문에 ch배열로 체크한다. #include #include #include #include using namespace std; int ch[30]; //79. 원더랜드(Prim MST 알..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개 풀이 - 크루스칼 알고리즘: 최소신장트리를 구성하는 알고리즘으로 k개의 노드에 K-1개의 간선을 선택한다. - 가장 적은 비용으로 트리를 구성하는데 가중치를 오름차순 정렬한 후 가중치가 낮은 간선을 먼저 선택한다. - for문을 돌면서 v1, v2의 집합이 같은지 find로 확인 후 같지 않으면 res에 가중치를 더하고 두 집합을 하나로 union한다. - union : find로 a,b의 집합을 찾고 이 집합이 서로 다를시에 unf[a]=b함으로써 하나로 합쳐준다. - 앞서 푼 문제와 union&find로 같은 알고리즘을 사용한다 #include #include #..

인프런 - it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비 강의를 바탕으로 공부한 내용입니다. 문제는 비공개로 입력예제와 출력예제만을 가지고 포스팅 입력예제 1 9 7 1 2 2 3 3 4 4 5 6 7 7 8 8 9 3 8 출력예제 1 NO 풀이 - Find & Union 알고리즘 - 1차원 배열인 unf를 사용해 트리형태를 구현한다 - Find와 Union 함수가 필요 (1) Find 함수 : 집합번호를 리턴하고 서로의 집합이 다를 시에 서로 합친다. ex ) {1}, {2} => {1, 2} (2) Union함수 - 인덱스 번호와 집합번호가 같으면 해당 v값을 return - 아닐시 unf[v]에 들어있는 값으로 루트 노드를 찾아 넣어준다 => unf[v]=Find(u..

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

Django를 처음 써보는 초보자 기억 복기용이므로 틀린 부분이 있을 수 있습니다. 다른 블로그에서 S3환경 설정하는 부분은 많이 나와있기 때문에 다루지 않습니다. S3에서 이미지 다운로드, 업로드를 API로 만드는 것을 목적으로 한 포스팅입니다. IDE : Pycharm 프레임 워크 설정 1. Preferences => Project => Python Interpreter에서 djangorestframework 추가 2. settings.py => REST_FRAMEWORK 부분 추가, INSTALLED_APPS에 'rest_framework' 추가 S3 연동해 API 만들기 [1] 터미널에서 pip명령어를 통해 아래 두 가지를 설치한다. S3 연동 패키지 설치 : pip install boto3 다양..

인프런 - 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일 => 위에서 남..