코딩스케치

질문만 모음트리와 그래프의 차이에 대해서 설명하시오 그래프 탐색 방법에 대해서 설명하시오 Heap이 무엇인지 설명하시오 Heap 자료구조에서 데이터 추출시에 시간복잡도가 어떻게 되는지 설명하시오 본인이 생각하는 가장 효율적인 정렬과 그것의 시간복잡도가 어떻게 되는지 설명하시오 탐욕 알고리즘과 동적 계획법을 각각 설명하시오 Stack과 Queue에 대해서 설명하시오 Stack과 Queue의 실사용 예시 List, Set, Map에 대해서 각각 설명하시오 Array, ArrayList, LinkedList에 대해서 각각 설명하시오 Array를 적용시키면 좋은 데이터는? HashMap과 HashTable에 대해 설명하시오 우선순위 큐에 대해서 설명하시오 BST(Binary Search Tree)와 Binary..

문제를 단순히 풀어가기만 하다가 계속 까먹고 해서 풀려고 하는 문제들이나 풀어온 문제들을 정리하려고 합니다. 좋은 문제들의 선정 기준은 여러 글과 유튜브들, 백준내에서 제출 답변 수 등을 참고했습니다. 문제 난이도는 브론즈~골드5입니다. 브론즈 문제와 실버 난이도 문제 위주이며 본격적인 골드 난이도 문제는 별도 포스팅으로 업데이트할 예정입니다. 혹시 풀이를 원하는 문제가 있다면 댓글로 남겨주시면 감사하겠습니다. 풀 수 있는 선에서 최대한 풀어서 풀이 올려보겠습니다. 풀이는 문제 설명과 그림이 필요한 경우 그림을 포함하여 Python으로 풀이를 제시하고 있습니다. 그리디(6문제)난이도문제풀이비고 Silver 5▶거스름돈◀python Silver 4▶2+1 세일◀python Silver 3▶서강근육맨◀pyt..

백준 2668번 숫자고르기 문제 설명2개의 행으로 이루어진 숫자들이 주어집니다. 1행은 각각 노드이고 이 노드들이 가지고 있는 숫자는 2행에 적혀있습니다. 즉, 각 노드들이 연결된 형태를 이룹니다. 이 중에서 서로 Cycle을 이루는 노드들을 찾는 문제입니다. DFS를 통해 Cycle의 조건을 만족하는 노드들을 찾아나갈 수 있습니다.  백준 2668번 숫자고르기 그림 설명Cycle조건 파악(그림1)Cycle의 조건을 파악하는 것이 가장 먼저입니다. 그림처럼 출발지점으로 다시 돌아오는 경우 Cycle이라고 할 수 있습니다. 2,3,4번은 Cycle을 이루고, 5번은 스스로 Cycle을 이루고 있습니다. 방법1 Cycle에 해당하는 Path를 통으로 등록(그림2)Cycle을 코드에서 어떤식으로 등록할까 고민..

백준 2583번 영역구하기 문제 설명표가 주어지며 직사각형 형태의 좌표가 주어집니다. 해당 좌표를 제외하고 각각의 영역의 넓이를 구하는 문제입니다. 각 영역을 탐색해서 넓이를 구해야 한다는 부분에서 DFS를 떠올릴 수 있지만 가로, 세로의 영역이 좌표처럼 주어진다는 부분과 좌표에서 특정 영역을 제외해야한다는 부분을 어떻게 풀어나갈 지가 중요한 문제라고 볼 수 있습니다. 저의 경우 DFS를 돌 떄 익숙하게 돌기 위해서 표를 뒤집는 방법을 적용했습니다. 백준 2583번 영역구하기 그림 설명그림1 - for문을 더 직관적으로 돌기 위해서 상하반전을 시켜줍니다. 이렇게 하면 평소 자주 도는 for문 형태와 같아집니다.그림2 - for문을 돌 때 좌표 형태가 어떻게 그려지는 확인합니다. 문제에서 주어지는 직사각형..

백준 2667번 단지번호붙이기 문제 설명대표적인 DFS 방식 탐색으로 볼 수 있으며 표 형태에서 DFS로 탐색해나가는 방법으로 풀어나갈 수 있을 것 같습니다.  백준 2667번 단지번호붙이기 그림 설명그림1 - 작은 테스트 케이스로 위와 같다고 구성해봅니다. 행은 i, 열은 j로 돌게됩니다.그림2 - 4방향을 각각 탐색하면서 더 나아갈 곳이 있다면 그만큼 전진시켜줍니다. dx, dy와 같이 배열형태로 나아가는 방향을 표기할 수 있습니다. 기존 i, j에 대해 dx, dy를 각각 더해주면 표에서 다음위치로 전진하는 개념입니다 DFS를 끝마치면 하나의 단지를 찾은 개념이 됩니다. for문을 다 돌고나면 그림 3과 같은 형태로 총 3개의 단지를 찾게됩니다.  백준 2667번 단지번호붙이기 정답 코드(자바)im..

백준 11403번 경로 찾기 자바 문제풀이문제에서 가중치 없는 방향 그래프가 주어집니다. 가중치가 없다. 방향이 있다는 것만 캐치하면 될 것 같습니다.플로이드 와샬로 푸는 방법도 있는 것 같습니다만 아직 해당 알고리즘에 익숙치 않아서 DFS 방식으로 접근했습니다.N 범위는 100까지기 때문에 N2 탐색을 하더라도 시간 문제는 없어보였습니다.   백준 11403번 경로 찾기 그림 풀이위와 같은 형태 즉, arrayList를 선언해서 node를 만들고 각각의 방향 그래프를 탐색해나가는 형태로 풀었습니다. 문제에서 특정 노드가 다른 노드로 향하는 방향이 주어지기 때문에 그걸 참고해서 graph를 만들었고, 각 node들을 돌면서 방문이 가능한 node들을 표시해나갔습니다.진행 순서를 보면 이처럼 볼 수 있습니..

kubectl top nodes 명령어로 node의 자원을 확인하려고 했는데 Metrics Server가 설치가 안되어있어 설치 및 설정을 해주었습니다. kubernetes top metrics api not available error가 발생하는 경우 다음과 같은 방법으로 해결 할 수 있습니다. # metrics 다운받기kubectl apply -f https://github.com/kubernetes-sigs/metrics-server/releases/latest/download/components.yaml  # 설치 확인kubectl get pods -n kube-system | grep metrics-server  # args에 추가kubectl -n kube-system edit deployme..