Preparing Coding Test114 [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] 투 포인터(Two Pointers), 구간 합(Prefix Sum) (출처 - 동빈나 유튜브) 배열의 특정된 연속 구간을 처리하는 경우에 사용하는 투 포인터와 구간합 알고리즘에 대해 알아보려 한다. 수열에서 합이 N인 연속부분수열 → Two Pointer N개의 정수로 구성된 수열에서 M개의 쿼리에 해당하는 구간합 → Interval Sum 코테에서도 많이 나오는 것 같다. 특정한 합을 가지는 부분 연속 수열 찾기 [투 포인터를 활용한 알고리즘 설명] 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)을 가리키도록 한다. 현재 부분 합이 M과 같다면, 카운트한다. 현재 부분 합이 M보다 작거나 같다면, end를 1 증가시킨다. 현재 부분 합이 M보다 크다면, start를 1 증가시킨다. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다. 양의 .. 2021. 6. 24. [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/BFS] 1868. 파핑파핑 지뢰찾기 문제 링크 swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LwsHaD1MDFAXc SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 아이디어 1. map 배열의 전체를 돌면서 8방탐색을 한다. → 8방에 지뢰가 몇개 있는지 체크해서 mark 배열에 저장한다. 2. mark가 0이고(주변에 지뢰가 없고) && 클릭한 적 없고 (visited가 false) && 지뢰가 아닌 곳(map이 0)인 곳 CLICK 3. 2에서 아직 클릭 안한 곳 && 지뢰가 아닌 곳 CLICK 왜인지 시행착오가 좀 많았다.. 0인 곳을 누르면 주변의 0인 곳.. 2021. 4. 23. [Java/백준/DFS] 16964번: DFS 스페셜 저지 문제 www.acmicpc.net/problem/16964 16964번: DFS 스페셜 저지 첫째 줄에 정점의 수 N(2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리의 간선 정보가 주어진다. 마지막 줄에는 DFS 방문 순서가 주어진다. DFS 방문 순서는 항상 N개의 정수로 이루 www.acmicpc.net 계속 99%에서 틀렸습니다가 떠서 환장했던 문제ㅠㅠ import java.io.*; import java.util.*; public class Main { static int N; static ArrayList[] adjacent; static boolean[] visited; static int[] compArr2; static StringBuilder sb = new.. 2021. 3. 9. [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/SWEA/백트래킹] 1247. [S/W 문제해결 응용] 3일차 - 최적 경로 문제 swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15OZ4qAPICFAYD&categoryId=AV15OZ4qAPICFAYD&categoryType=CODE&problemTitle=1247&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 문제 조건을 보면 집 → N명의 고객 → 회사 경로로 간다. 처음에 최단경로 라는 키워드를 보고서 BFS를 이용해야 하나 싶긴 했었다. 이렇게 하면 N명.. 2021. 2. 18. 이전 1 2 3 4 ··· 13 다음
