Preparing Coding Test/Baekjoon49 [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/백준/DFS, DP] 1937번: 욕심쟁이 판다 문제 링크 www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n*n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에서 www.acmicpc.net 골드 3 문제다. 읽자마자 실버 수준의 DFS로 풀었다가 슬픈 결과를 여러번 맞이했다. 아래부터 1) DFS만 사용했다가 시간초과 발생 2) DP 사용했는데 max값 잘못 계산 반례 : 2 2 2 2 2 3) 성공 시간초과 코드 DFS만 이용한 경우이다. boolean[][] visited를 매개변수로 가지고 이동하면서 선택한 블록에 대한 경로를 저장한다. dfs에서 cnt는 더 이상 갈 블.. 2021. 4. 23. [Java/백준/구현,배열] 10157번: 자리 배정 문제 www.acmicpc.net/problem/10157 10157번: 자리배정 첫 줄에는 공연장의 격자 크기를 나타내는 정수 C와 R이 하나의 공백을 사이에 두고 차례대로 주어진다. 두 값의 범위는 5 ≤ C, R ≤ 1,000이다. 그 다음 줄에는 어떤 관객의 대기번호 K가 주어진다. www.acmicpc.net 소프트웨어아카데미의 와 거의 같은 문제이다. 범위를 벗어나면 방향을 수정하는 방법으로 풀면 된다. 배열 범위를 생각하는게 넘 번거롭고 귀찮다... import java.io.*; import java.util.*; public class Main { static int[][] map; static int C, R; static int[] dy = { 1, 0, -1, 0 }; static .. 2021. 2. 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/백준/소수] 1978번: 소수 찾기 문제 www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 전에 정리해뒀던 dev2som.tistory.com/27 [Java] 소수 찾기 문제 https://programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자.. dev2som.tistory.com 의 에라토스테네스 체 방법을 참고했다. 설명은 주석으로! package boj; import ja.. 2021. 2. 15. [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. 이전 1 2 3 4 ··· 6 다음
