개인사

개요그래프정점과 정점사이의 상관관계를 나타내는 자료구조 노드와 간선으로 이루어져 있다.1. 그래프의 방향그래프는 방향이 있는 그래프와 방향이 없는 그래프로 나뉘어 진다. (양방향과 단방향)2. 가중치각 노드간 간선에 가중치가 있을 수 있다. (거리 등) 3. 트리그래프의 한 종류로 LEVEL이 설정되어 있는 그래프이다. LEVEL 0에 ROOT 노드가 있으며, 하위 노드는 자식이 된다. 반대로 자식 입장에서 ROOT 노드는 부모 노드이며, 자식간의 관계는 형제 노드가 된다.트리의 특징방향 그래프만 존재루트 노드가 한개만 존재계층 형식으로 비순환 그래프4. 인접 행렬위 트리 노드를 인접 행렬로 표현하면 아래와 같이 표현할 수 있다.노드12345101001200110300000400000500000 출발지 ..

개요1. 중복 순열중복이 가능한 N개 중에서 R개를 선택하는 경우의 수(순서를 고려한다, 중복 조합)별다른 판별조건 없이 모든 수를 도출해 주면 된다.1 1 21 2 12 1 1 2. 순열서로 다른 N개 중에서 R개를  선택하는 경우의 수(순서를 고려한다, 중복인 경우는 선택하지 않는다.)DAT를 활용하여 이미 선택한 경우에는 선택하지 않도록(방문 여부 체크) 판별조건을 추가해 준다.1 2 31 3 22 3 1 3. 중복 조합중복이 가능한 N개 중에서 R개를 선택하는 경우의 수(순서를 고려하지 않는다.)중복이 가능하다 = 방문 처리를 하지 않는다.조합을 위해 현재 뽑는 순서가 2번째 이상일 경우 이전에 뽑았던 수보다 작을경우 선택하지 않는다. 라는 판별 조건을 추가해 준다.1 1 11 1 21 1 31 ..

리뷰최소 힙과 최대 힙을 사용하여 문제를 풀이하였다.처음엔 스택을 사용하려 했으나 인입되는 순서 관리 골치아파서 힙으로 풀릴 것 같아 힙을 사용하였다. 문제 풀이n, k, t 값을 받아와 주고 최소힙과 최대힙을 초기화 해준다.t보다 크거나 같은 값은 bigger로, 작은 값은 lower 힙으로 보내준다.cnt가 k보다 작을 경우 while루프를 돌려 lower에서 가장 큰 값을 t에 더해주고 해당 요소를 빼준다.요소를 빼주고 나서는 변경된 t값에 맞추어 최소힙과 최대힙을 최신화 해줘야 한다. 참고 사항lower에서 가장 큰 값을 빼주기 전에 while문을 통해 bigger에 존재하는 t보다 작은 값들을 lower로 옮겨 주었다.  정답 코드#include #include #include using nam..

개요백트래킹 : 재귀 호출 중 가망성이 있는지 여부를 판별하면서 진행하는 방식재귀를 통해 경우의 수를 모두 탐색하여 구하고자 하는 조건에 일치하는 경우를 모두 구할 수 있다.실행하고자 하는 하는 반복 횟수, 재귀를 빠져나올 기저 조건, 각 반복 횟수에 적용할 식을 잘 세우면 효율적으로 사용할 수 있다.  예제1. 조합을 선택하여 출력하기서로 다른 n개의 수에서 k개의 수로 이루어진 조합을 출력하기코드#include using namespace std;int n, k;int arr[100];int DAT[110];void bt(int index) { // 2. 기저 조건 if (index >= k) { for (int i = 0; i > n >> k; for (int i = 0; i > arr[i]; }..

리뷰3차 배열의 BFS문제 문제 풀이3차 배열을 사용해야 하므로 방향을 총 6개를 설정해 줘야 한다. 상, 하, 좌, 우, 위, 아래n, m, h값을 입력받고 3차 배열에 값을 넣어준다. 이때 값이 1일경우 미리 큐에 넣어주면 편하다.bfs를 실행하고 3차 배열의 범위 내를 탐색한다. 나는 다음 좌표가 만약 값이 0인 경우 time + 2를 해주었다.bfs가 종료된 후 토마토가 잘 익었는지 확인해 주어야 한다. flag와 max_val 변수를 각각 0으로 초기화 해줬다.3차 배열을 돌며 만약 0이 발견되면 flag = 1, break 해준다. 그게 아니라면 max_val에 최대값을 저장해 준다.flag가 1일경우 -1을 출력, 0일 경우 max_val을 2로 나눈 값을 출력해 주면 된다. 참고 사항tim..

리뷰케이스를 2개로 나누어 BFS를 활용하여 푸는 문제 문제 풀이n값과 2차 배열을 입력받은 후 2차 배열을 한개 더 생성 후 초기화 해준다. (깊은 복사 필요)0, 0부터 n-1, n-1 좌표까지 순회를 하며 만약 각 배열의 현재 좌표 값이 '_'가 아니라면 각각의 bfs를 실행해 준다.bfs1은 각 색상이 주어졌을때 해당 색상이 있는 부분은 모두 '_'로 바꿔주고 case1 즉, bfs1 실행 횟수를 증가 시킨다.bfs2는 위와 동일하나 만약 색상이 R 혹은 G일경우 R, G모두 '_'로 바꿔주고 case2를 증가 시킨다.2차 배열의 모든 순회와 bfs처리가 종료된 후 case1과 case2를 출력해 주면 된다. 참고 사항없음  정답 코드#include #include #include using na..

리뷰C++, 파이썬 모두 힙을 사용한 BFS로 문제를 풀었다. 문제 풀이m과 n을 입력받고 2차 배열을 입력 받는다, 방향 배열을 4방향으로 초기화 한 후 방문 배열도 n * m크기로 초기화 한다.힙에 (벽을 부순 횟수, x좌표, y좌표)를 초기화 해준다. 초기값은 (0, 0, 0)이다. 최소 벽을 출력할 min_wall 변수도 0으로 초기화 해주고 while 루프를 실행한다.현재 힙에 존재하는 벽이 가장 낮은 정보를 뽑아온다.만약 끝부분에 도달했다면 현재 까지 부순 벽의 수를 min_wall에 저장해 준다.그게 아니라면 4방향을 체크하며 범위 내에 존재하는지, 방문을 한적이 있는지를 체크해 준다.만약 방문을 하지 않은 좌표라면 방문 처리를 해주고, 해당 좌표의 값이 1이라면 부순 벽을 1만큼 올려준 뒤..

개요함수란 무엇인가? 코드를 기능 단위로 묶어둔 것이다.return type funcname() { body}와 같은 형식을 가진다. 지역/전역/함수를 사용할때 어떤 메모리 영역에서 쓰이는지 잘 구분해야 한다. 재귀는 다시 돌아오다 라는 뜻으로 재귀 함수는 다시 돌아오는 함수이다. 즉 다시 실행되는 함수 (run / recall)재귀 함수는 자기 자신을 리턴 혹은 호출 하므로 종료 조건을 설정하지 않으면 원하는 의도가 나오지 않을 가능성이 매우 높다. (함수를 호출하는 것 자체가 메모리를 사용하는 것이므로 while처럼 무한루프에 빠지진 않을 것이다.)따라서 재귀 함수를 사용할 당시엔 종료 조건을 설정해 주어야 한다. 예제1. 무한 루프코드#include using namespace std;void he..

리뷰전위, 중위, 후위 순회 겁먹지 말고 그냥 출력 시점만 조정해 주면 된다.우선 문제는 굉장히 친절하다, A, B, C 오름차순으로 주어지고 루트는 항상 A고 좌우 노드 모두 친절히 설명해 준다. 문제 풀이맵을 통해 앞의 노드를 키로 갖고 뒤의 값 두개를 pair로 받아준다.A를 시작으로 dfs를 돌려주고 '.'가 아닌 노드를 왼쪽부터 방문해 주면 된다.전위 순회 : dfs 재귀를 실행하기 전에 루트 노드부터 출력 해준다.중위 순회 : 왼쪽 노드 재귀를 실행한 후 루트 노드를 출력해 주면 된다.후위 순회 : 왼쪽 및 오른쪽 노드 모두 재귀를 실행해 주고 나서 루트 노드를 출력해 주면 된다.각 dfs 실행 사이에 줄바꿈을 한번씩 해주면 된다. 참고 사항 정답 코드#include #include #incl..

리뷰BFS도 가능하지만 그리디 알고리즘으로 풀이가 가능하다. 문제 풀이b에서 a로 가는 방법으로 풀이한다.while루프의 조건은 a가 b보다 작거나 같을때 실행, cnt를 1 상승시키고 만약 a와 b가 같다면 루프를 종료한다.현재 b의 뒷자리가 1이라면 b를 10으로 나눈 몫을 b로 갱신해 준다.만약 b가 짝수라면 b를 2로 나눈 몫을 b로 갱신해 준다.둘다 해당되지 않다면 -1을 출력하고 리턴한다.중간에 리턴되지 않고 루프가 종료되었을때 a가 b보다 크다면 -1을, 아니라면 cnt를 출력한다. 참고 사항while루프가 종료되는 경우는 다음과 같다.1의 자리 뒤에 1을 붙이거나 2를 곱해도 a가 결코 b가 될 수 없을 때a가 b보다 커져서 루프가 종료 되었을 때 정답 코드#include using nam..