algorithm/BOJ (63) 썸네일형 리스트형 백준 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 코드 설명 먼.. 백준 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.. 백준 1926_그림(JAVA) www.acmicpc.net/problem/1926 1926번: 그림 어떤 큰 도화지에 그림이 그려져 있을 때, 그 그림의 개수와, 그 그림 중 넓이가 가장 넓은 것의 넓이를 출력하여라. 단, 그림이라는 것은 1로 연결된 것을 한 그림이라고 정의하자. 가로나 세로 www.acmicpc.net [문제 풀이] 깊이 우선 탐색을 이용하여 문제를 풀었습니다. 이 문제는 2차원 배열에 대한 정보가 주어지고 2차원 배열에서 1로 연결된 그림의 갯수가 최대 그림의 크기를 찾는 문제였습니다. 문제를 푼 방법은 배열을 순회하며 1이 시작되는 좌표를 찾고 깊이 우선으로 탐색하며 확인한 좌표들은 마킹을 해주는 식으로 풀었습니다. 코드 설명 입력으로 주어진 값을 받아 배열에 저장해주고 방문을 확인할 배열을 똑같이 선언해 줍니.. 백준 2583_영역 구하기(JAVA) www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net [문제 풀이] 너비 우선 탐색을 이용하여 문제를 풀었습니다. 이 문제는 사각형의 좌표가 주어 졌을 때 사각형 공간을 제외한 나머지 공간이 몇개로 나누어질 수 있는지에 대해 찾는 문제였습니다. 문제를 풀기 위해 2차원 배열에 사각형이 차지하고 있는 부분을 먼저 적은 후 2차원 배열을 순회하면서 체크 되지 않은 부분이 있다면 BFS를 통해 영역을 구해 주었습니다. 코드 설명 입력으로 주어진 값을.. 이전 1 2 3 4 ··· 8 다음 목록 더보기
