끵뀐꿩긘의 여러가지

◎문제 링크 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net ◎문제 파악 수빈이의 이동 가능 type 1. -1칸 2. +1칸 3. *2칸 ◎코드 구현 더보기 package project; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import ..

◎문제 링크 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net ◎문제 파악 비연결일 수도 있는 그래프를 BFS로 탐색하는 문제이다. 예를 들어 위와 같은 밭이 있고 1인 칸이 배추가 있는 칸이라면, 위의 문제는 5개의 비연결 그래프를 BFS로 탐색하는 문제이다. 비연결 그래프를 BFS탐색하기 위해서는 1. BFS 탐색 조건 2. 탐색이 끝날 조건 두가지가 필요하다. 1. BFS 탐색 조건에서는 배추 흰 지렁이가 상하좌우에 있는 인접한 배추로는 이동할 수 있으..

◎문제 링크 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net ◎문제 파악 이분 그래프(BipartiteGraph): 인접한 정점끼리 서로 다른 색으로 칠해서 모든 정점을 두 가지 색으로만 칠할 수 있는 그래프. 즉, 그래프의 모든 정점이 두 그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는( 같은 그룹에 속한 정점끼리는 서로 인접하지 않도록 하는) 그래프를 이분 그래프라고 한다. 출처: https://gmlwjd9..

◎문제 링크 https://www.acmicpc.net/problem/7562 7562번: 나이트의 이동 체스판 위에 한 나이트가 놓여져 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 www.acmicpc.net ◎문제 파악 기본적인 bfs문제이다. 움직이는 주체가 나이트라서 상하좌우로만 움직였던 다른 bfs문제와는 다르게 역동적으로 움직인다. 나이트의 움직임 체스의 나이트는 위의 그림과 같이 움직인다. 현재 나이트의 위치에서 index x y 1 -1 -2 2 -2 -1 3 -2 +1 4 -1 +2 5 +1 +2 6 +2 +1 7 +2 -1 8 +1 -2 이렇게 8개의 방향으로 움직인다. 또한..

◎문제 링크 https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net ◎문제 파악 BFS로 최단 경로를 찾는 일반적인 문제와 결은 비슷하지만, 1번까지 벽을 부수고 이동할 수 있다는 점이 이 문제의 특징이자, 어려운 포인트이다. p가 A에서 B, B에서 C로 이동할 때, (A는 언제나 0 통로이다) 1. B가 통로이고, C가 통로인 경우 p는 B,C로 이동하며, p는 벽을 부순적이 없다. 2. B가 벽이고, C가 통로인 경우 P..

◎문제 링크 https://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 ◎문제 파악 1. 모든 티켓을 다 사용할 수 있는 경로를 찾을 것. -> DFS(깊이 우선 탐색)를 사용하여 그래프를 돌아보며 경로를 찾는다 2. 방문한 경로를 저장할 것 -> stack을 recursion DFS의 매개변수로 두어 DFS함수의 depth가 늘어날 때마다 경로를 stack에 저장한다 3. 경로가 여러..

◎문제 링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net ◎문제 파악 가장 중요한 조건이자 유일한 조건이 "연속으로 놓여 있는 3잔을 모두 마실 수는 없다."는 것이다. 조건을 만족하는 포도주 배열에 새로운 잔 한잔(i번째 포도주)이 추가되었을 때, 연속으로 3잔을 먹지 않기 위해서는 마지막 3잔만 고려하여 3가지 행동을 할 수 있다. 1. 추가된 (i번째) 포도주 선택하지 않기 --> 최댓값 = i-1번째 포도주까지 있을 때와 최댓값이 같음..

◎문제 링크 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ◎문제 파악: 계단수: 모든 자리수의 차이가 1이 나는 수 목표: N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하기 1. 1 자리 수일 때: 1~9의 수는 모두 계단수이다. 2. 2 자리 수일 때, 0으로 시작하는 수는 1의 자리에 1을 붙일 수 있다. --> 01 (1 자리 수의 배열 index 1참조) 1로 시작하는 수는 1의 자리에 0이나 2를 붙일 수 있다. --> 10,12 (1 자리 수의 배열 index 0,2 참조) 2로 시작하는 수는 1의 자리에 1이나 3을 붙일 수 ..