본문 바로가기

algorithm

 (135)
백준 15729_방탈출(JAVA) https://www.acmicpc.net/problem/15729 15729번: 방탈출 첫째 줄에 N(1 ≤ N ≤ 1,000,000)가 주어지고 둘째 줄에는 쪽지에 적혀 있는 N자리의 수가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net [문제 풀이] 그리디 알고리즘을 이용하여 문제를 풀었습니다. 이 문제는 전구가 하나도 켜지지 않은 상태에서 최종 전구의 상태로 변할 수 있는 최소 횟수를 구하는 문제입니다. 단순 그리디를 통해 한 가지 규칙을 이용하여 풀었습니다. 문제를 푸는 순서는 다음과 같습니다. 최초 배열[n + 2]를 순차적으로 돕니다. 현재 인덱스의 배열의 값으 1이면 오른쪽 두개의 값을 반대로 변환 시켜줍니다. 이 것을 한번의 횟수로 칩니다. [코드] package coding..
백준 1342_행운의 문자열(JAVA) https://www.acmicpc.net/problem/1342 1342번: 행운의 문자열 민식이와 준영이는 자기 방에서 문자열을 공부하고 있다. 민식이가 말하길 인접해 있는 모든 문자가 같지 않은 문자열을 행운의 문자열이라고 한다고 한다. 준영이는 문자열 S를 분석하기 시작 www.acmicpc.net [문제 풀이] DFS를 이용하여 문제를 풀었습니다. 이 문제는 문자열이 주어졌을 때 두 가지 비교를 통해 행운의 문자열을 찾아내는 것입니다. 1. 사용할 알파벳이 있느냐 2. 이전 알파벳이 현재 알파벳과 같느냐 이 두 가지를 비교해서 만든 문자열이 주어진 문자열의 크기와 같을 경우 결과값을 올려주는 방식으로 문제를 해결했습니다. 문제를 푸는 순서는 다음과 같습니다. 문자열을 입력 받으면 알파벳의 갯수를..
백준 1197_최소 스패닝 트리(JAVA) www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net [문제 풀이] MST를 이용하여 문제를 풀었습니다. 이 문제는 최소 신장 트리 중 Kruskal를 구현하는 문제였습니다. 최소 신장 트리에 관한 내용은 아래 링크에 가시면 자세히 나와있습니다. //현재 수정 중이라 비공개 되있습니다. 빠른 시일 내에 정리하여서 올리겠습니다. steady-life.tistory.com/124?category=788590 코드 설명 먼..
프로그래머스_여행경로(C++) programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr [문제 풀이] DFS를 이용하여 문제를 풀었습니다. 이 문제는 공항을 잇는 경로들이 주어지고 모든 공항을 잇는 경로 중 알파벳 순이 가장 빠른 경로를 찾는 문제입니다. 문제를 푸는 방법은 주어진 경로들을 알파벳 순으로 정렬하여 알파벳 순으로 경로들을 확인하면서 가장 먼저 나오는 경로를 찾는 방법입니다. 코드 설명 tickets 백터를 알파벳 ..
백준 2156_포도주 시식(JAVA) www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net [문제 풀이] DP를 이용하여 문제를 풀었습니다. 이 문제는 숫자가 주어 졌을 때 아래와 같은 두 가지 규칙을 이용하여 포도주를 고를 때 최대로 마실 수 있는 포도주의 양을 찾는 문제입니다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 문제를 푸는 방법은 1 ~ N까지 포도주 양을 확인하며 누적합..
백준 1463_1로 만들기(JAVA) www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net [문제 풀이] DP를 이용하여 문제를 풀었습니다. 이 문제는 숫자가 주어 졌을 때 아래와 같은 세가지 규칙을 이용하여 x가 1로 가는 최소 연산의 횟수가 몇번인지를 찾는 문제입니다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 문제를 풀기 위하여 DP를 이용하였습니다. 문제에 사용 된 점화 식은 아래와 같습니다. arr[i] = arr[i-1] + 1; if(i % 2 == 0){ arr[i] = Math.min(arr[i], arr[i/2] + 1); } if(i %..
백준 1717_집합의 표현(JAVA) www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net [문제 풀이] 유니온 파인드를 이용하여 문제를 풀었습니다. 이 집합의 원소들이 주어 졌을 때 0,1을 통해 원소의 집합을 합쳐주고 같은지 확인 하는 문제였습니다. 전형적인 유니온 파인드 문제임으로 이론은 아래 링크에 들어가시면 자세히 설명 되있습니다. steady-life.tistory.com/128?category=788590 서로소 집합(Disjoint Set, Un..
서로소 집합(Disjoint Set, Union-Find) 서로소 집합 교집합이 공집합인 집합(서로소 집합)들의 정보를 확인(Find)하고 조작(Union)할 수 있는 자료구조 2가지 연산으로 이루어져 있습니다 Union 연산 - 어떤 두 원소 a, b 에 대해서 union(a, b)는 각 원소가 속한 집합을 하나로 합치는 연산 - a ∈ A, b ∈ B 에 대해서, union(a, b)는 A∪B 이다. Find 연산 - 어떤 원소 a에 대해서 a가 속한 집합(집합의 대표번호)을 반환 - a ∈ A 에 대해서, find(a)는 집합 A(집합 A의 대표번호)를 반환 서로소 집합 표현 배열(Array) 초기화 자기 자신의 부모를 자기 자신으로 초기화 i 1 2 3 4 5 U[i] 1 2 3 4 5 Union 연산 시간복잡도 : O(N) union(1, 3) unio..

티스토리툴바