백준20 [Java/백준/BFS, DFS] 1707번: 이분 그래프 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 주어진 조건을 보고 이분그래프인지 아닌지 판단하면 되는 문제다. 이분그래프는 아래처럼 하면 된다. https://ko.wikipedia.org/wiki/%EC%9D%B4%EB%B6%84_%EA%B7%B8%EB%9E%98%ED%94%84 이분 그래프 - 위키백과, 우리 모두의 백과사전 2색변 이분 그래프의 예 그래프 이론에서, 이분 그래프(二分graph, 영어: bipartite gra.. 2021. 6. 25. [Java/백준/투포인터] 1806번: 부분 합 문제 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 연속된 수들의 부분합들 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성해야 한다. 참고한 부분은 아래 링크! https://dev2som.tistory.com/135 [Java] 투 포인터(Two Pointers), 구간 합(Prefix Sum) (출처 - 동빈나 유튜브) 배열의 특정된 연속 구간을 처리하는 경우에 사용하는 투 포인터와 구간.. 2021. 6. 25. [Java/백준/백트레킹] 1987번: 알파벳 문제 www.acmicpc.net/problem/1987 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 백트래킹 너무 어렵다ㅠㅠ.... 일단 백트래킹이란 걸 처음에 알아보는 것부터 아직 어설프다... 앞으로 DFS를 사용해야 할 것 같다, 가지치기 할 수 있을 것 같다 하면 걍 백트래킹으로 해야지.. 시행착오가 좀 있었다. 처음엔 alphabet을 사용했는지 여부만 알아보는 코드이다. 기저조건은 그냥 썼던 알파벳일때 return max는 다 dfs를 돌고 나왔다 싶을 해줬다. 근데 이러면 안될 것 같.. 2021. 2. 18. [Java/백준/배열] 16926번: 배열 돌리기 1, 17406번: 배열 돌리기 4 문제 www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 새로운 유형을 만나버렸다. 앞으로 많이 쓰일 것 같아서 고민하다 다른사람들의 풀이를 보고 방법을 아예 외워버렸다. 배열 전체를 반시계 방향으로 입력된 횟수만큼 돌려주면 된다. 여기서 고민할 것은 몇 겹의 layer로 이루어져 있는지, 어떻게 돌려줄 것인지 이다. 1. Layer 수 예를 들어 4 x 5 배열에선,.. 2021. 2. 14. [Java/백준/스택(Stack)] 2493번: 탑 문제 www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 이해에만 엄청 오래 걸렸다.. 힌트를 봐도 당최 어떻게 푸는질 알아야지ㅠ 코드 자체는 단순하다. 탑이 나열되어 있을 때 가장 오른쪽에서 바라보면, 높은 건물들만 보인다. 탑 높이를 입력 받는다. → tall (1-1) stack 확인, 비어있지 않다면 stack의 top의 높이를 확인한다. → tall보다 높다면 높은 탑의 위치를 출력하고 반복문을 빠져나온다. (1-2) stack 확인, 비어있지 .. 2021. 2. 14. [Java/백준/재귀, 분할정복] 2630번: 색종이 만들기 문제 www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. www.acmicpc.net color 변수에 시작점의 색을 저장한다. 지정 범위에서 color와 다른 색이 나오면, 해당 범위는 모두 같은 색으로 칠해져 있다는 것이 아니므로, 범위를 4개로 나누어서 재귀 함수를 호출한다. 기저조건은 start와 end의 범위가 1이 될 때로 했다. package boj; import java.io.*; public class BOJ2630 { static int blue.. 2021. 2. 14. [Java/백준/스택(Stack)] 1918번: 후위 표기식, 1935번: 후위 표기식2 문제 www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 A~Z의 문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 수식 www.acmicpc.net www.acmicpc.net/problem/1935 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 후위 표기식: 골드 4, 후위 표기식2: 실버 3 문제이다. 푸는 방식은 비슷해서, 후위 .. 2021. 2. 14. [Java/백준/Queue(큐)] 1158번: 요세푸스 문제, 11866번: 요세푸스 문제 0 문제 www.acmicpc.net/problem/1158 1158번: 요세푸스 문제 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000) www.acmicpc.net www.acmicpc.net/problem/11866 11866번: 요세푸스 문제 0 첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 1,000) www.acmicpc.net 두 문제는 범위만 다른 동일한 문제이다. 위 문제는 자료구조 중 Queue를 사용하면 쉽게 풀 수 있다. 큐(Queue)는 먼저 들어온 데이터가 먼저 나가는 FIFO(선입선출) 구조를 띄고 있다. 예제의 7 3을 예로 들면 처음엔 에서 1을 빼서 7 뒤로 넣고, 2를 빼서 7 뒤의 1 뒤.. 2021. 2. 14. [Java/백준/DP] 1932번: 정수 삼각형 문제 www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 코드 한 줄과 그 위의 줄만을 생각한 점화식을 세웠다. 0 0 0 0 0 0 ← i=0 0 7 0 0 0 0 ← i=1 0 3 8 0 0 0 ← i=2 0 8 1 0 0 0 ← i=3 0 2 7 4 4 0 ← i=4 0 4 5 2 6 5 ← i=5 == N ↑ ↑ j=0 j=5 입력값을 받는 배열이 triangle, 최대값이 들어가는 배열이 max_triangle이라 할 때, max_triangle[i][j] 에 들어가는 배열을 생각하면 1) 윗 줄의 양 대각선 위치의 max_.. 2020. 10. 4. 이전 1 2 3 다음
