BangBang's Devlogs

www.acmicpc.net/problem/1012 문제 해결 방안 배추가 있는 공간들을 DFS 탐색을 통해 분리된 갯수를 찾는 문제이다. maps에 배추가 있는 값들을 추가해주고 maps를 탐색하면서 1(배추가 있는 곳)일 때 result(지렁이)++해주고 DFS를 해서 visited를 true로 만들어줘서 다음에 1일때 이미 방문했으면 넘어갈 수 있게 해주었다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; //유기농 배추 public class Main { static int m; // 가로길이(1~50) static int n; // 세로길이(1~50) static int ..

www.acmicpc.net/problem/2178 문제 미로의 (1,1) 에서 (n,m)위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 문제이다. BFS + DP를 이용하여 해결하였다. 해결 방안 1. 미로의 이동 가능 여부 관련 값은 maps[][]에 저장하였다.(1이면 이동 가능) 미로의 해당 칸으로 이동할 때 지나야하는 최소의 칸 수는 cnts[][]에 저장하였다.(0이면 한번도 이동 안한 곳) 2. 주어진 maps의 (1,1) 위치에서 (m,n)으로 BFS 방법으로 4방향을 탐색하고 DP를 이용하여 cnts에 지나야하는 최소 칸 수를 메모제이션하였다. 3. cnts[n][m]을 출력하면 도착 위치에 가기위해 지나야하는 최소의 칸을 출력한다. 코드 import java.io.BufferedR..

www.acmicpc.net/problem/2606 문제 입력의 첫째 줄이 그래프의 노드 갯수가 되고 둘째 줄이 간선의 갯수가 될 것이다. 또한 무방향 그래프가 될것이다. 해결 방안 무방향 그래프를 ArrayList를 이용하여 구현하였다. 1번부터 시작하는 DFS 탐색을 하였으며 DFS의 depth를 바이러스 감염 시킨 컴퓨터 갯수로 하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; // 바이러스 public class Main { static int n; // v static int e; // edge static Array..

www.acmicpc.net/problem/10974 문제 해결 방안 모든 순열을 출력하는 기본적인 DFS 문제이다. DFS + 백트래킹을 이용하여 구현하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; // 모든 순열 public class Main { static int n; static boolean[] visited; public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader..

www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 문제 해결 방안 time 배열의 index는 해당 위치이고 값은 해당 위치를 수빈이가 최소 몇 초를 나타낸다. 또한 수빈이는 3가지 방법으로 이동할 수 있으므로 3가지 방법으로 이동한 위치의 값이 k 일때까지 너비우선 탐색을 해주면 된다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.In..

www.acmicpc.net/problem/1766 문제 * 위상 정렬의 대표적인 문제이다. (줄 세우기 문제에 약간 심화문제 우선순위 큐 사용) yubh1017.tistory.com/manage/newpost/83?type=post&returnURL=https%3A%2F%2Fyubh1017.tistory.com%2F83 Queue를 이용한 위상정렬로 구현하였다. 문제를 풀기전 간단하게 위상정렬에 대한 설명을 하자면 1. 위상 정렬은 그래프 정렬을 말한다. 2. 위상 정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 한다. 두 노드 A,B 사이에 A->B 같은 관계가 성립되어야 하며 A->B 관계가 성립하면 B->A나 B->C->A와 같이 사..

www.acmicpc.net/problem/2252 문제 * 위상 정렬의 대표적인 문제이다. Queue를 이용한 위상정렬로 구현하였다. 문제를 풀기전 간단하게 위상정렬에 대한 설명을 하자면 1. 위상 정렬은 그래프 정렬을 말한다. 2. 위상 정렬이 가능하려면 DAG(Directed Acyclic Graph, 방향성이 있으며 사이클이 없는 그래프) 여야 한다. 두 노드 A,B 사이에 A->B 같은 관계가 성립되어야 하며 A->B 관계가 성립하면 B->A나 B->C->A와 같이 사이클이 생겨서는 안된다. 3. 자기 자신을 가리키는 간선의 갯수인 indegree 배열을 이용하여 구현할 수 있다. 4. 위상 정렬 과정 4.1) 위상 정렬을 위해 두개의 Queue를 만들어준다. q : indegree 값이 0인 ..

www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토� www.acmicpc.net 문제 해결 방안 BFS를 기본으로하여 구현하였다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; // 토마토 // ..

TCP란? TCP는 네트워크 계층 중 전송 계층에서 사용하는 프로토콜 로서, 장치들 사이에 논리적인 접속을 성립(Establish) 하기 위하여 연결을 설정하여 신뢰성을 보장하는 연결형 서비스이다. TCP 3-way HandkShake란? TCP 통신을 이용하여 데이터를 전송하기 위해 네트워크 연결을 설정(Connection Establish)하는 과정이다. TCP 3-way HandkShake 역할 및 과정 [STEP 1] Client는 Server에 접속을 요청하는 SYN 패킷을 보낸다. 이때 Client는 SYN을 보내고 SYN/ACK 응답을 기다리는 SYN_SENT 상태가 된다. [STEP 2] Server는 Client의 SYN 요청을 받고 Client에게 요청을 수락한다는 ACK와 SYN 가 ..

programmers.co.kr/learn/courses/30/lessons/12973?language=java 코딩테스트 연습 - 짝지어 제거하기 짝지어 제거하기는, 알파벳 소문자로 이루어진 문자열을 가지고 시작합니다. 먼저 문자열에서 같은 알파벳이 2개 붙어 있는 짝을 찾습니다. 그다음, 그 둘을 제거한 뒤, 앞뒤로 문자열을 이어 붙 programmers.co.kr Stack 자료구조를 활용하여 구현하였습니다. 해결 방안 문자열의 문자들을 Stack에 넣어주면서 stack.peek()이 넣으려는 문자와 같으면 pop()해주고 아니면 push()해준다. 다 끝난 후 stack이 비어있으면 성공적으로 수행하였으므로 1, 비어있지 않으면 0을 반환해준다. 코드 import java.util.*; class..