본문 바로가기

알고리즘23

[BOJ 9252] LCS2 문제 정리LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제두 수열이 주어진다.부분 수열을 찾는다.그 중 가장 긴 것을 찾는다.예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.LCS의 길이와 LCS를 출력한다.제한 사항0.1s, java11: 0.4s각 수열 = 최대 1000글자LCS가 0인 경우, 길이만 출력핵심 포인트LCS를 naive하게 찾아보자.A 수열과 B 수열이 있을 때, B 수열로 A 수열의 LCS를 찾는다면 O(N^3)이 발생한다.B 수열의 각 글자를 첫 부분 수열의 글자로 생각하고 찾는다면 1000 글자에 대해 각 각 1000 - i 글자 수를 연산해야 된다. (N^2)각 N^2의 부분 수열의 글자가 A 수열에 있는지 확인해야한다. (N.. 2025. 4. 8.

[BOJ 17406] 배열 돌리기 4 문제 정리배열의 최솟값을 구한다.배열의 최솟값은 각 행의 모든 원소의 합 중 가장 작은 값이다.배열이 주어지면 k번의 회전을 한다.각 회전은 r, c, s 값으로 회전한다.(r-s, c-s) 부터 (r+s, c+s) 까지 시계 방향으로 회전한다.회전 연산이 두 개 이상이면, 연산을 수행한 횟수에 따라 최종 배열이 달라진다.제한 사항3 ≤ N, M ≤ 501 ≤ K ≤ 61 ≤ A[i][j] ≤ 1001 ≤ s1 ≤ r-s 1 ≤ c-s 핵심 포인트다른 연산이 존재하므로 백트래킹백트래킹으로 구할 수 있는 모든 연산 과정이 적으므로 완전 탐색 가능배열 회전의 최종 결과로 최종 배열을 획득 할 수 있으므로 가지치기 필요 없음.배열 회전에 대한 구현력 필요핵심 로직백트래킹을 통해 다른 경우에 대한 회전 상태 저.. 2025. 4. 3.

[BOJ 1826] 연료 채우기 문제 정리트럭으로 마을까지 이동 중 1KM를 이동 할 때마다 1L의 연료가 빠져 나가는 상황이동하는 곳곳에 N개의 주유소가 존재트럭은 충전 할 때 마다 연료를 충분히 충전할 수 있음.각 각의 주유소 위치와 연료의 양이 주어 질 때, 최소한으로 충전하는 횟수 구하기마을에 도착할 수 없는 경우 -1제한 사항 제한사항 1: 주유소 개수 1 제한사항 2: 주유소 위치 1 제한사항 3: 주유소 연료 1 제한사항 4: 현재 위치에서 마을까지 거리 1 제한사항 5: 현재 트럭의 연료량 1 핵심 키포인트충분히 많이 충전 -> 한 번에 최대한 많은 이익, 그리디의 핵심핵심 포인트거리와 연료 중 어느 것을 포커스로 두어야하는가?의심해야 할 포인트 1: 가장 많은 연료를 얻는 것이 좋은가?의심해야 할 포인트 2: 가장 멀리.. 2025. 3. 31.

[BOJ 20207] 달력 문제 정리날짜가 1일 ~ 365일로 표시되어 있는 달력을 가지고 있음.올해 일정을 모두 계획해서 달력에 표시함.날씨로 인해 달력에 표시한 일정 중 일부가 지워지려고 함.방지하기 위해 일정이 있는 곳에만 코팅지를 달력에 붙이려고 함.너무 귀찮은 탓에 아래와 같은 규칙을 따라 코팅지를 붙이려고 한다.연속된 일정을 모두 감쌀 수 있는 가장 작은 직사각형의 코팅지를 만들어 붙인다.연속된 두 일자에 각 각 일정이 1개 이상있다면, 연속된 일정이다.연속된 모든 일정은 하나의 직사각형에 포함되어야 한다.달력은 아래와 같은 규칙을 따른다.일정은 시작 날짜와 종료 날짜를 포함한다.시작일이 가장 앞선 일정부터 차례대로 채워진다.시작일이 같은 경우 일정의 기간이 긴 것부터 채워진다.일정은 가능한 한 최 상단에 배치된다.일정.. 2025. 3. 31.

[MST] 최소 스패닝 트리 - 크루스칼(Kruskal), 프림(Prim) MST란? 최소 신장 트리(Minimum Spanning Tree)로 가중 그래프(Weight Graph)에서 가장 적은 비용(Weight)으로 모든 정점(Vertex)으로 이동할 수 있는 부분 그래프(Sub Graph)이다. MST는 각 정점에서 정점 사이에 하나의 간선(Edge)만 필요하므로 총 N-1 개의 간선을 가지게 되므로 마치 트리의 형태를 하고 있어서 트리라는 이름이 붙는다.크루스칼 알고리즘 1. 모든 간선을 비용이 적은 순서를 기준으로 정렬한다. - Sort2. 간선에 붙은 정점 u와 v를 기준으로 부모를 찾는다. - Find3. 정점 u의 부모와 정점 v의 부모가 다르다면 서로 다른 집합에 속해있지만, 1번 과정으로 인해 해당 간선이 두 정점의 최소 비용의 간선임을 알 수 있으므로 하나의.. 2024. 7. 11.

[Java] Graph (Adjacency Matrix, Adjacency List) 정점(Vertex)과 간선(Edge)로 구성된 것, Graph(G) = (Vertex(V), Edge(E)) Graph 용어 정점(Vertex) - 노드, 특정할 수 있는 실체간선(Edge) - 정점 간 이어져 있는 선가중치(Weight) - 정점 간에 거리, 비용 (간선의 길이라고 생각해도 좋음)경로(Path) - 출발 정점에서 도착 정점까지의 거쳐 간 순서순환(Cycle) - 경로의 출발 정점과 도착 정점이 같은 경우차수(Degree) - 정점에 붙은 간선 수진입 차수(In-Degree) - 정점으로 들어오는 간선 수진출 차수(Out-Degree) - 정점에서 나가는 간선 수Graph 종류 유향 그래프(Directed Graph) - 특정 정점에서 특정 정점으로 이동하는 그래프무향 그래프(UnDire.. 2024. 7. 9.

백준 - [BOJ 22856] 트리 순회 문제노드가 N개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자.순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. 이때 루트 노드는 항상 1번 노드이다.유사 중위 순회는 루트 노드에서 시작하며, 다음과 같이 진행된다.현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다.그렇지 않고 현재 위치한 노드의 오른쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 오른쪽 자식 노드로 이동한다.그렇지 않고 현재 노드가 유사 중위 순회의 끝이라면, 유사 중위 순회를 종료한다.그렇지 않고 부모 노드가 존재한다면, 부모 노드로 이동한다.유사 중위 순회를 종료할 때까지 1 ~ 4를 반복한다.위 그림에 있.. 2024. 7. 8.

[Java] Binary Tree Binary Tree는 트리를 통해 데이터를 비선형적으로 관리하는 자료구조이다.앞서 포스팅에서 BST(Binary Search Tree)에 대해서 설명했는데 BST도 이진 트리를 기반한 자료구조이다. 왜 Binary Tree를 사용할까?Tree Post에서도 설명했는데 일반 DAG와 같은 Tree는 효율성 측면에서 너무 부족하다. 그저 Graph와 다름이 없다.그래서 실제 데이터 처리를 하기 위해 Binary Tree로 효율성을 극대화하는 방법을 채택한 것이다. 크게 Binary Tree의 두 종류를 알아보자. 1. 완전 이진 트리2. 편향 트리 이 외에도 많지만 Binary Tree의 핵심을 설명하기에 두 가지가 최고인 것 같다. 위 두가지 개념을 언급한 이유는 BST의 문제점 때문이다.앞서 작성한 B.. 2024. 7. 8.

[Java] Binary Search Tree 앞 포스팅에서 작성한 Tree의 비효율적인 문제를 개선하기 위해 생긴 이진 탐색 트리다.트리는 여러 자식을 가질 수 있지만 이진 검색 트리에서는 Binary Tree의 개념을 사용하기 때문에자식이 Left, Right만 존재한다. 이를 통해 Log_2 (N) 번만에 모든 수행을 끝낼 수 있다. 또, inorder를 수행 시 오름차순 정렬된 결과를 얻을 수 있다. package com.study.datastructrue.nonlinear.binarysearchtree;public class Node { int value; Node left; Node right; public Node(int value) { this.value = value; left = null;.. 2024. 7. 8.

이전 1 2 3 다음

티스토리툴바