BangBang's Devlogs

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..

www.acmicpc.net/problem/15970 15970번: 화살표 그리기 직선 위에 위치를 나타내는 0, 1, 2, ...와 같은 음수가 아닌 정수들이 일정한 간격으로 오른쪽 방향으로 놓여 있다. 이러한 위치들 중 N개의 위치에 하나씩 점들이 주어진다(). 주어진 점들� www.acmicpc.net 문제 각 점에서 색깔이 같은 가장 가까운 점과 연결한 화살표들의 길이 합을 구하는 문제이다. 해결 방안 색깔마다 점의 배열을 만들어서 정렬을 한 뒤 각 점에서 가장 가까운 선(왼쪽 혹은 오른쪽)을 구해서 더해주면 되겠다고 생각하였다. HashMap을 사용하여 점들의 색깔마다 ArrayList(점의 위치 배열)를 만들어주었다. 그 후 색깔마다 점의 위치 배열을 정렬해주고 각 점에서 가장 가까운 점까지의..

www.acmicpc.net/problem/17609 문제 회문인지, 유사 회문(한글자만 삭제하면 회문이 되는 경우)인지, 일반 문자열인지 확인하는 문제이다. 해결 방안 주어진 단어의 첫 부분은 증가시키고 끝 부분은 감소시키면서 비교해온다. 이 때 단어의 변화되는 첫 부분 문자와 끝 부분의 문자가 가운데에 올 때가지 같으면 회문(0)이다. 그렇지 않은 경우 첫 부분을 하나 증가시키거나 끝 부분을 하나 감소시켜서 한 글자를 삭제 시켜서 확인을 해보고 둘 중 하나의 경우라도 회문이면 유사회문(1)이고 둘다 안되면 일반 문자열(2)인 경우이다. 이를 코드로 나타내면 아래와 같다. 코드 import java.io.BufferedReader; import java.io.IOException; import java..

www.acmicpc.net/problem/17608 문제 해결 방안 뒤에서부터 확인을 하므로 Stack을 이용하여 구현하였다. 기준 막대기높이(standard)보다 비교하는 막대기높이(current)가 크면 갯수를 하나씩 늘려주고 standard를 current로 바꿔준다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Stack; // 막대기 public class Main { public static void main(String[] args) throws IOException { Stack stack = new Stack(); BufferedR..

www.acmicpc.net/problem/17616 17616번: 등수 찾기 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에 세 정수 N, M, X가 공백을 사이에 두고 주어진다. (2 ≤ N ≤ 105, 1 ≤ M ≤ min(N(N-1)/2, 5×105), 1 ≤ X ≤ N) . 다음 M 줄에는 각각 두 정수 A, B가 주어�� www.acmicpc.net 문제 그래프를 만들어야 되는 문제라고 생각은 했으나 어떻게 문제를 접근해야할지 몰라서 다른사람 풀이 참고함 참고 블로그: home-body.tistory.com/646 해결 방안 가능한 가장 높은 등수 U와 가능한 가장 낮은 등수 V를 구하는 문제이다. 크게 보자면 단방향 그래프로 lower_graph와 higher_graph 두개를 이용해서 ..