![]()
목차 개요 대표적인 그래프 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있습니다. 상호 배타적 집합(Disjoint - set)이라고도 합니다. 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 입니다. 2가지 연산으로 이루어져 있습니다. Find : x가 어떤 집합에 포함되어 있는지 찾는 연산 Union : x와 y가 포함되어 있는 집합을 합치는 연산 구현 부모노드를 저장할 배열 생성 int[] parent = new int[10]; for(int i = 0; i < 10; i++) { parent[i] = i; } 구현은 간단한 트리를 통해서 이루어집니다. parent[i] 를 i 노드의 부모 노드 라고 정의하고 초기화합니다. pare..
![]()
문제출저 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 소스코드 package studyGroup.June.june5; import java.util.*; import java.lang.*; import java.io.*; /* 유니온 파인드 유니온 파인드를 통해 진실을 아는 사람의 그룹을 만든다. 파티의 멤버들 중 진실을 아는 사람이 한 명도 없다면 answer++ 반례 8 4 1 1 3 1 2 3 3 4 5 6 3 6 7 8 2 3 8 정답 : 0 ..
![]()
목차 개요 티스토리 글쓰기에 유용한 목차를 만들어보겠습니다. jQuery 플러그인 Table of Contents(TOC)를 이용하고 참조한 블로그에 많은 도움을 받았습니다. 더 자세히 알고 싶으면 참조한 블로그를 방문하세요. 스킨은 북클럽으로 하시는 것을 권장합니다. 참조한 블로그 : https://sangminem.tistory.com/307 티스토리 글에 자동으로 목차 넣기 목차를 넣고 싶긴한데 글 쓸 때마다 매번 수작업으로 만든다면 상당히 번거롭겠죠. 그래서 jQuery 플러그인 Table of Contents(TOC)를 이용하여 자동으로 넣는 방법을 소개합니다. 저는 제목1, 제목2로 sangminem.tistory.com jQuery TOC 플러그인 다운과 업로드 다음 자바스크립트 파일을 다운..
![]()
문제출저 : https://www.acmicpc.net/problem/17265 17265번: 나의 인생에는 수학과 함께 세현이의 인생의 목표는 1분 1초 모든 순간 수학과 함께 살아가는 것이다. 그렇기 때문에 매일 수학을 생각하면서 살아가고 있다. 세현이는 밥을 먹을 때도 쌀알의 수를 계산하여 칼로리를 바로 www.acmicpc.net 소스코드 : package studyGroup.June.june4; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; import java.lang.*; public class 백준17265나의인생에는수학과함께 { sta..
![]()
추상클래스 추상 클래스는 클래스 내 추상메소드가 하나 이상 포함되거나 abstract으로 정의된 경우를 말합니다. 추상클래스를 비유하자면 미완성 설계도라고 표현합니다. 추상 클래스는 일반 클래스와 차이가 거의 없습니다. 단지 추상 메소드를 선언하여 상속을 통해서 자손 클래스에서 완성하도록 유도하는 클래스입니다. 상속을 위한 클래스이기 때문에 따로 객체를 생성할 수 없습니다. 클래스안의 메소드가 단 한개라도 추상메소드가 있다면 그 클래스 앞에는 반드시 abstract 클래스명으로 표기해야 하며 abstract와 final 키워드를 동시에 표기할 수 없습니다. public abstract class Test {} 추상 메소드는 선언부는 있는데 구현부가 없는 메소드를 의미합니다. (안이 아직 구현되어 있지 않..
![]()
DP 개요 DP, 다이나믹 프로그래밍은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 문제해결에 패러다임으로 볼 수 있습니다. 큰 문제를 작은 문제로 나누어서 그 답을 저장해두고 재활용한다. 사용이유 DP는 일반적인 재귀(Navie Recursion) 방법과 유사합니다. 하지만 일반적인 재귀를 사용할 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산이 될 수 있습니다. 피보나치 수열을 예시로 들겠습니다. 피보나치의 재귀 함수는 아래와 같습니다. return f(n) = f(n-1) + f(n-2) f(n)을 구하기 위해서 f(n-1)에서 한 번 구한 값들을 f(n-2)에서 같은 과정을 반..
![]()
문제출저 : https://www.acmicpc.net/problem/14945 14945번: 불장난 랩실의 크기가 3일 경우 (기웅, 민수)가 이동 가능한 방법은 (아래-아래, 대각-아래), (아래-아래, 대각-대각), (아래-대각, 대각-대각), (대각-아래, 아래-아래), (대각-대각, 아래-아래), (대각-대각, www.acmicpc.net 소스코드 : package studyGroup.June.june3; import java.util.*; import java.io.*; /* 중복되는 문제가 있기 때문에 DP로 접근한다. 이동할 수 있는 경우의 수는 4가지이다. 1. 둘 다 아래 (거리 그대로) 2. 1번 아래, 2번 오른쪽 (거리 +1) 3. 1번 오른쪽, 2번 오른쪽 (거리 그대로) 4. ..
![]()
Java와 C++은 문법적으로 상당히 유사합니다. java를 설계할 때 C++ 개발자들이 쉽게 배울 수 있도록 만들었기 때문입니다. 하지만 차이점도 여러 개가 있습니다. 설계 목표 Java는 보안, 이식성, 빠른 개발에 비중을 두었고 C++은 속도와 C언어의 하위 호환성을 중점으로 두었습니다. C++은 절차지향언어인 C의 효율성을 개선하기 위해 OOP(Object Oriented Programing)을 결합한 것이기 때문에 완벽한 OOP가 아닌 절차지향도 섞여 있습니다. 클래스 Java는 기본 단위가 Class로 거의 완전한 OOP라 볼 수 있습니다. C++은 C언어의 상위 호환이기 때문에 절차지향이 섞여있습니다. 컴파일과 런타임의 차이 Java는 가상 머신 바이트 코드로 컴파일하며 실행시키려면 가상머신..
![]()
위상정렬이란? 방향 그래프에서 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점을 나열하는 것 이다. 위상정렬의 특징 하나의 방향 그래프에는 여러 위상 정렬이 가능하다. 위상정렬 과정에서 선택되는 정점의 순서를 위상순서라고 한다. 위상정렬 과정에서 그래프에 남아 있는 정점 중에 진입 차수가 0인 정점이 없다면, 위상정렬 알고리즘은 중단된다. 위상정렬의 흐름 1. 진입차수가 0인 정점을 선택 2. 선택된 정점과 연결된 간선들을 제거 3. 위의 과정을 반복해 모든 정점이 선택, 삭제되면 알고리즘 종료 위상정렬과 관련된 문제 백준 작업 : https://www.acmicpc.net/problem/2056 게임 개발 : https://www.acmicpc.net/problem/1516 줄 세우기 :..
![]()
문제출저 : https://www.acmicpc.net/problem/1516 1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 소스코드 : import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static int n; // 갯수 static int[] timeBoard; static int[] indegree; sta..
![]()
문제출저 : https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 소스코드 : import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.nio.Buffer; import java.util.*; /* 메모리 초과 발생.. 1. Queue의 타입 클래스를 변경. dp로 시간 체크 2. 선수과목들을 일일히 다 정하는게..
![]()
문제출저 : https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 소스코드 : import java.util.*; class Solution { public int solution(int n, int[][] computers) { int answer = 0; for(int i = 0; i < n; i++) { computers[i][i] = 0; } int count = 0; Queue que = new Li..
