내가보려고만든 메자노트

문제 보러 가기 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 이 문제는 이진트리 자료구조를 이용하여 너비를 구하는 응용문제이다. 너비를 구하는 부분에서 좀 다른 점이 있다면, 각 level마다 최대 너비를 구해야 한다는 점. 가장 왼쪽 자식이 1번 , 가장 오른쪽 자식이 n번으로 너비를 구한다는 점이다. 아래 트리와 같이 구성된다. 문제풀이 - 자신의 번호와(num) 부모 번호(parent) 왼쪽 자식(left) 오른쪽 자식(right)을 갖는 Node 클래스를 만든다. - Node []..

최소 스패닝 트리(Minimum Spannig Tree) = 최소 신장 트리 : 스패닝 트리 중 가장 작은 가중치의 간선으로 구성된 트리를 의미한다. 조건 본래의 그래프의 모든 노드를 포함 간선의 가중치의 합이 최소여야 한다 모든 노드가 서로 연결되어있다 트리의 속성을 만족 (사이클이 존재하지 않는다) ↓스패닝 트리란? 더보기 스패닝 트리란? : 그래프의 최소 개수의 간선으로 이뤄진 트리 (n개의 노드가 존재한다면 간선은 항상 n-1개이다) 모든 노드가 연결되어야 함 사이클이 존재하지 않음 즉, 최소 스패닝 트리에서 최소 가중치의 합 조건만 빠진 트리를 의미. 이 최소 스패닝 트리 문제를 다루는 알고리즘에는 2가지가 있다. 1. 크루스 칼(Kruskal) 알고리즘 : 두 노드 간 제일 작은 가중치의 간선..

최소 스패닝 트리 2가지 알고리즘 내용 문제 보러 가기 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 이 문제는 최소 스패닝 트리의 가장 기본적인 구현을 다루는 문제이다. 최소 스패닝 트리는 스패닝 트리 중(그래프 내의 모든 정점을 포함하는 트리) 연결된 간선 가중치가 가장 작은 것들로 구성된 트리를 의미한다. 모든 정점을 포함하기 위해서는 하나의 트리로 연결돼야 하는데 이때 사용하는 알고리즘이 크루스칼, 프림 2가지의 방법이 있다. 이 중 크루스칼을 이용하여 풀이하였다. 문제풀이 크루스칼 알고리즘은 Union-Find를 사용하여 구현할 수 있다. -> Union-Find 설명 - 간선의 정보를 ..

문제 보러 가기 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 이 문제는 유니온 파인드라는 알고리즘을 이용하여 합집합을 만들고, 판단하는 문제이다. 자료구조를 코드로 만들어 표현하는 부분을 더 연습해야겠다고 생각했다! 유니온 파인드(Union-Find) 알고리즘이란? 그래프 알고리즘 중 하나이다. 분리 집합, 합집합 찾기의 의미를 갖는다. parent [] 배열로 각 노드가 어떤 부모 노드 아래에 있는지 그래프로 만든다. x 1 2 3 parent[x] 1 2 3 -..

문제 보러 가기 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 영문자 www.acmicpc.net 이 문제는 기본 트리구조를 생성하고 트리의 순회 방법인 전위, 중위, 후위 순회를 해보는 트리 자료구조의 기본 문제라고 볼 수 있다. 재귀를 사용하여 구현하였다. 트리는 다양한 방법으로 구현할 수 있다. 나의 경우 트리 클래스를 따로 만들어서 사용하였다. Node [] 배열로 만들어서 구현하는 방법도 존재한다. 문제풀이 -tree 자료구조에 입력받은 각 노드를 위치에 맞게 insert()한다. -전위 순회(preOrder) : 루트 -> 왼..

문제 보러 가기 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 이 문제는 백트래킹에 속해있는 문제로 완전 탐색을 통해 풀이할 수 있다. [ 적절한 탐색 조건 + 탐색을 하는 순서 ]를 찾아 접근하여야 통과할 수 있었던 거 같다. 물론 나는 헤매다가 다른 분들의 접근법을 참고하였다 ^_ㅠ 문제풀이 -가장 적게 색종이를 사용하므로 5X5의 색종이부터 탐색 -해당 색종이 영역이 다 1인지 확인 -> 다 1이면 사용할 수 있다는 의미 -해당 색종이를 사용할 수 있다면 사용하고 다른 색종이에 걸리지 않도록 0..

문제 보러 가기 코딩테스트 연습 - 단체사진 찍기 단체사진 찍기 가을을 맞아 카카오프렌즈는 단체로 소풍을 떠났다. 즐거운 시간을 보내고 마지막에 단체사진을 찍기 위해 카메라 앞에 일렬로 나란히 섰다. 그런데 각자가 원하는 배치가 모두 programmers.co.kr 이 문제는 카카오프렌즈들을 세우는 순서의 경우의 수 -> 순열을 구하는 문제였다! 순열을 다 구하면 시간 초과가 날까 고민했지만 그냥 모든 순열을 구해서 풀었다. 하지만 제출 시 틀리다고 나와서 뭐가 문제인지 계속 고민했는데,,, 전역 변수의 경우 main안에서 초기화를 꼭 해줘야 한다... 왜지.. 궁금하다.. 이걸로 삽질하지 말자고 올리는 풀이! -프로그래머스는 다 그런 듯..? 문제풀이 -8명을 세우는 총경우의 수는 8! = 40320 ..

문제보러가기 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 이 문제는 누적 합을 응용해 나머지가 0 인 구간의 개수를 구하는 문제이다. 어떻게 풀어야 하나 해서 검색도 하고 고민.. 항상 느끼지만 기본적인 수학 지식이 있으면 좋을 거 같다 ㅎ.. 누적 합 이란 A [0] + A [1] +... A [i]+..+A [j]+...+A [n]의 숫자에서 A [i]부터 A [j]까지의 합을 구하는걸 미리 합 해놓은 S [] 배열로 구하는 문제이다. -> i~j까지의 합..