JUINTINATION

1번 문제: 타겟 넘버https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr풀이n개의 음이 아닌 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절..

문제 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 풀이 폴리오미노란 크기가 1×1인 정사각형을 다음과 같은 조건을 만족하면서 여러 개 이어서 붙인 도형입니다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노를 테트로미노라고 할 때 테트로미노 하나를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는..

문제 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이인 트리의 지름을 구하는 문제입니다. 1967번 문제와 유사합니다. 1967번 문제와 다른 점은 입력에서 -1을 입력할 때 까지 해당 노드에 연결된 노드의 정보를 입력한다는 것입니다. 접근 1967번 문제와 연결됩니다. 트리의 간선들에 가중치가 있기 때문에 단..

문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 풀이 입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때 트리에 존재하는 모든 경로들 중에서 가장 긴 것의 길이인 트리의 지름을 구하는 문제입니다. 접근 트리의 간선들에 가중치가 있기 때문에 단순히 가장 왼쪽에 있는 노드와 가장 오른쪽에 있는 노드 사이의 거리를 구하는 문제가 아닙니다. 처음에 이 문제를 보고 루트 노드에서 가장 먼 노드와 두 번째로 먼 노드 사이의..

문제 https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 풀이 루트 없는 트리가 주어진다. 트리의 루트를 1이라고 정했을 때 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력하는 문제입니다. 접근 이진트리라는 조건도 없고 자식노드가 부모노드보다 숫자가 크거나 작다는 조건이 없기 때문에 일반적인 이진탐색트리 관련 알고리즘으로는 문제를 해결할 수 없었습니다. 그래서 DFS와 BFS를 이용하여 그래프를 순회하며..

그래프(Graph)란? 연결되어 있는 객체 간의 관계를 표현하는 자료구조 그래프 G는 (V, E)로 표시 정점(vertices) 여러 가지 특성을 가질 수 있는 객체 노드(node)라고도 불림 간선(edge) 정점들 간의 관계 링크(link)라고도 불림 DFS란? 깊이 우선 탐색(depth-first search)한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 이 곳으로부터 다른 방향으로 다시 탐색 진행 스택(Stack)을 사용하거나 재귀함수 사용 # 재귀함수를 사용한 DFS depth_first_search(v): v를 방문되었다고 표시; for all u ∈ (v에 인접한 정점) do if (u가 아직 방문되지 않았으면) then depth_first_..