문제 https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 풀이 처음에는 BFS로 풀었는데 틀렸습니다.가 나왔다. 구글링을 통해 왜 BFS가 아닌 DFS로 풀어야하는지에 대해 찾아보았다. BFS를 사용하지 못하는 이유는 처음 지점부터 끝 지점까지 연결한 파이프는 한 줄이다. 따라서 오른쪽 위, 오른쪽, 오른쪽 아래 세 지점을 탐색해야하는데 만약 오른쪽 위 지점을 연결해서 쭉 이어가다 파이프 연결했으면 다시 돌아와서는 오른쪽과 오른쪽 아래 지점을 탐색할 수 없고 모든..

인터넷 네트워크 IP(인터넷 프로토콜) IP의 역할 지정한 IP주소에 데이터 전달. 패킷이라는 통신 단위로 전달. IP 패킷 정보 출발지 IP, 목적지 IP 등 담아서 전달 IP 프로토콜의 한계 비연결성: 패킷을 받을 대상이 없거나 서비스 불능 상태여도 패킷 전송 비신뢰성: 중간에 패킷 사라지거나 순서대로 안오면..? (패킷 소실) 프로그램 구분: 같은 IP 사용하는 서버에서 통신하는 앱 둘 이상이면? TCP/UDP IP 패킷 안에 TCP 정보 있다. 출발지 PORT, 목적지 PORT, 전송 제어, 순서, 검증 정보 -> 이 안에 전송 데이터가 들어 있다. TCP 특징 전송 제어 프로토콜 (Transmission Controal Protocol) 연결 지향 - TCP 3 way handshake (가상 ..

문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이 유니온 파인드의 연습 문제 UNION 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶음 private static void union(int a, int b) { //union 연산: 대표 노드까지 연결하기 a = find(a); b = find(b); if(a!=b) { parent[b] = a; } } FIND 두 노드가 같은..

문제 https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 알고리즘 C++로 이런 기초 BFS 문제를 많이 풀어봤으나 JAVA로는 처음 풀어서 큐에 저장하는 방식이나 스트링을 문자열로 바꾸고 이를 다시 이차원 배열에 저장하는 과정이 조금 까다로웠다. 알게된 점을 정리하자면, 먼저 BFS를 진행할 때 큐에 해당 좌표를 삽입하는데, 이때 Queue q = new LinkedList(); 이처럼 int[]의 형식으로 좌표를 저장하게 된다. 그리고 이 큐에 push를 진행할 때면 q.ad..

문제 https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 알고리즘 BFS, DFS 두 가지 방식으로 해결할 수 있다. BFS, DFS 두 가지의 풀이를 작성해 두었다. arr을 전역변수로 선언하고 초기화하고 할당하는게 아직도 헷갈리지만, new이후 ArrayList()를 하는 것이 객체를 생성하는 것이라고 생각하니 조금 더 이해가 잘 되는 것 같다. 우선 값을 입력받고 arr에 값을 저장한다. 그리고 bfs나 dfs를 모든 정점에서 진행할 필요 없이 1..

문제 https://acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 알고리즘 DFS 코드 package algo0317; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; public class B13023_ABCDE { static int n, m; static StringBuilder sb = new StringBuilder(); static ..

문제 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 알고리즘 이진 탐색을 이용한다. 중간 값을 찾은 뒤, 찾아야하는 수가 중간 값보다 크다면 뒷쪽을 탐색하고, 작다면 앞쪽을 탐색한다. 뒷쪽을 탐색하기 위해서는 시작점을 중간값 + 1로 옮기고 앞쪽을 탐색하기 위해서는 끝점을 중간값 - 1로 옮겨준다. 코드 package algo0317; import java.io.BufferedReader; im..

문제 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 알고리즘 그리디 서로 겹치지 않는 회의에 대해 종료시간이 빠르면 더 많은 활동을 선택할 수 있는 시간이 많아진다 끝나는 시간을 기준으로 오름차순 정렬을 진행한다. 이때 끝나는 시간이 동일하다면 시작 시작이 더 빠른 것이 앞쪽으로 오게된다. 코드1 package algo0317; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; import java.util.Str..

자바 정렬 방법 1. Compatable 클래스 자체의 정렬 기준을 정하는 것 class A implements Comparable{ public int compareTo(Object obj){ return this.변수 - obj.변수; } } 예시 package algo0317; import java.util.Arrays; import java.util.Comparator; public class ExamComparable { private static final String Comparator = null; public static void main(String[] args) { // TODO Auto-generated method stub Meeting[] ma = new Meeting[3]; m..

문제 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 설명 자바로 dfs를 구현하는 것은 처음인데, 이때 ArrayList를 활용했다. ArrayList를 배열형태로 만들어서 인접리스트를 구현하였다. 우선 인접 리스트를 초기화 한 뒤, 인접 리스트에 그래프를 저장한다. 이때 양방향이기 때문에(방향이 없는 그래프) a[s].add(e)와 a[e].add(s)를 둘 다 추가해 주었다. 방문하지 않은 경우 카운팅을 하고 dfs를 재귀 방식으로 호출한다. ..