728x90 전체 글140 백준 No.1005 [ACM craft] Baekjoon Online Judge No.1005 [ACM craft] 문제 1005번: ACM Craft (acmicpc.net) 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 설명 위상정렬(2021.08.05 - [Algorithm (C++ based)/Algorithm 이론] - 위상 정렬 (Topological Sort))의 기본 개념을 이용하여 풀 수 있는 문제이다. 위상정렬을 통해 각 건물(노드)에 방문을 할 때 마다 그 건물을 짓는데 걸리는 시간을 계속해서 최대값으로 업데이트를 한다. .. 2021. 8. 5. 위상 정렬 (Topological Sort) 위상 정렬 (Topological Sort) 위상정렬 위상정렬은 무향 비순환 그래프 (DAG : Directed Acylic Graph) 에서 정해진 순서에 맞게 나열을 하는 것 이다. 일상에서의 예시로 대학교 과목 이수도 에서 선수과목이 있는 것을 생각해 볼 수 있다. 과목 F 를 듣기 위해선, 과목 D, E 를 들어야 한다. 또 과목 D를 듣기 위해선 과목 A를, 과목 E 를 듣기 위해선 과목 B, C 를 들어야 하고 과목 B를 듣기 위해선 과목 A를 들어야 한다. 이 경우 가장 처음에 들을 수 있는 과목은 선수과목이 없는 과목 A와 과목 C 이다. 위상 정렬은 이러한 선수과목이 없는 경우 즉, 진입 간선이 없는 경우를 따져가면서 정렬을 해 나가는 알고리즘 이다. 설명 1. 주어진 노드와 간선에 대한.. 2021. 8. 5. 유클리드 호제법 / 확장 유클리드 호제법 유클리드 호제법 / 확장 유클리드 호제법 유클리드 호제법 유클리드 호제법 이란 두 자연수 사이의 최대공약수(GCD) 를 구하는 알고리즘 이다. gcd(a, b) == a 와 b 의 최대공약수 라고 할 때 알고리즘에 사용되는 식은 다음과 같다. gcd(a, b) == gcd(b, a % b) ... (b 2021. 8. 4. 세그먼트 트리 (Segment tree) 세그먼트 트리 (Segment tree) 정의 세그먼트 트리 (Segment tree) 란, 1차원 배열의 값들을 포화 이진 트리를 활용하여 Bottom-up 을 통해 효율적으로 저장 및 탐색하는 자료구조 이다. 이 트리의 리프 노드들은 순서대로 배열의 원소들에 해당이 되며, 내부 노드들은 아래 두 자식 노드에 해당이 되는 배열의 원소들을 합한 범위의 원소들에 대한 연산 값을 나타낸다. 트리 구현 트리의 각 노드들은 배열에서 트리에 해당되는 구간의 원소들의 합의 값을 가지고 있다. 설명 세그먼트 트리는 Bottom-up 방식으로 구현이 된다. 이를 위해선, 리프 노드들을 배열의 원소들로 우선적으로 초기화를 시켜준다. 리프노드의 시작 노드는 배열의 개수보다 큰 2의 제곱수 들 중 최소값이다. 즉 위 트리에.. 2021. 8. 3. 백준 No.7453 [합이 0인 네 정수] Baekjoon Online Judge No.7453 [합이 0인 네 정수] 문제 7453번: 합이 0인 네 정수 (acmicpc.net) 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 설명 투 포인터 알고리즘을 활용하여 풀었다. 투 포인터를 하기 이전 투 포인터를 할 수 있는 상태를 만들어야 한다. 위와 같이 4개의 배열이 주어졌다고 할 때, 결국 네 배열의 원소의 합이 0인 경우가 몇 번 있는지를 찾는 것 이므로, 각각의 배열들은 다른 배열과 무조건 한 번씩은 더해지는 작업을 거치게 된.. 2021. 8. 2. 백준 No.9466 [텀 프로젝트] Baekjoon Online Judge No.9466 [텀 프로젝트] 문제 9466번: 텀 프로젝트 (acmicpc.net) 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 설명 학생들을 노드라고 하고, 학생들이 각각 본인이 팀을 하고 싶은 상대를 간선으로 표현하였다. 결국, 한 팀이 이루어지기 위해선 아래와 같이 싸이클이 이루어져야 한다. 빨간 간선들이 팀을 의미한다. {1, 2, 4} 세 명 이서 한 팀을, {3} 혼자서 한 팀을 이렇게 총 두 팀을 이루었고, {5, 6, 7}은 모두 팀을 이루지 못 했다. 처.. 2021. 8. 2. 삼성SDS 21년 하계 알고리즘 특강 후기 삼성 SDS 21년 하계 알고리즘 특강 후기 ( 2021.07.19 (월) ~ 2021.07.30 (금) ) 2021년 6월 11일 금요일까지 삼성SDS 에서 2021년 하계 알고리즘 특강 지원을 받았다. 7월 중순까지는 계절학기를 들었어야 해서 2차수로 지원을 해 보았다. (지원을 할 땐 병적증명서, 재학증명서, 성적증명서, 전공증명서류를 제출 해야 했었다!)지원을 하면 무조건 들을 수 있는 것이 아니라 지원자가 교육과정에 있는 문제 및 이론들을 이해할 수 있는지 확인을 하기 때문에 지원서 마감 후 코딩테스트를 보았다. 코딩테스트는 6월 16일 수요일 오전 9시부터 6월 20일 일요일 자정까지 5문제를 풀면 됐다. 4.5일 정도 안에 5문제를 풀면 됐기 때문에 주어진 시간상 5문제를 다 푸는것은 무리는.. 2021. 7. 31. Overloading 과 Overriding 의 차이점 Overloading 과 Overriding 의 차이점 오버로딩과 오버라이딩의 차이점 Overloading 오버로딩(Overloading) 이란, 같은 이름을 갖는 함수나 연산자를 정의하는 것을 의미한다. 먼저, 함수의 오버로딩(Functional Overloading)은 두 개 이상의 함수가 같은 이름을 가졌지만, 서로 다른 매개변수(Parameter) 리스트를 가질 때 발생한다. 아래와 같은 예시가 있다. #include using namespace std; int add(int A, int B, int C) { return A + B + C; } int add(int A, int B) { return A + B; } int main() { int num1 = 2; int num2 = 4; int n.. 2021. 7. 28. 백준 No.12015 [가장 긴 증가하는 부분 수열 2] Baekjoon Online Judge No.12015 [가장 긴 증가하는 부분 수열 2] 문제 12015번: 가장 긴 증가하는 부분 수열 2 (acmicpc.net) 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 설명 2021.07.28 - [Algorithm (C++ based)/BOJ] - 백준 No.11053 [가장 긴 증가하는 부분 수열] 백준 No.11053 [가장 긴 증가하는 부분 수열] Baekjoon Online Judge No.11053 [가장 긴 증가하는 부분 수열] 문제 11053번: 가.. 2021. 7. 28. 백준 No.11053 [가장 긴 증가하는 부분 수열] Baekjoon Online Judge No.11053 [가장 긴 증가하는 부분 수열] 문제 11053번: 가장 긴 증가하는 부분 수열 (acmicpc.net) 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 설명 Dynamic programming 을 이용하여 Memoization 을 통해 풀 수 있다. 아래와 같이 가장 긴 증가하는 부분수열을 구해야 하는 arr 배열이 있다. 정답을 구하기 위해서 arr 의 첫 번째 수 부터 li.. 2021. 7. 28. Class, Object, Instance 의 차이 Class, Object, Instance 의 차이 Class 객체 지향 프로그래밍(OOP : Object Oriented Programming) 에서 특정 객체를 생성하기 위해서 변수와 메소드를 정의하는 일종의 틀이다. 'class'는 객체(Object)를 정의하기 위한 멤버변수와 메서드로 구성이 된다. Object 객체(Object)는 'Class'에서 정의한 것을 토대로 실제 저장공간에 할당이 된 것 이다. 변수, 자료구조, 메소드가 될 수 있다. 이는 객체 지향 프로그래밍의 핵심이라고 할 수 있다. 객체 지향 프로그래밍은 컴퓨터 프로그램을 여러 개의 독립된 단위인 객체들의 모임으로 파악을 하고자 한다. 각각의 객체들은 서로 데이터를 주고 받으며 그 데이터를 원하는 방식으로 처리를 할 수도 있다. .. 2021. 7. 27. JAVA API "String" class JAVA API "String" class String class char 배열에 기능을 추가 한 클래스 이다. 문자를 연달아 놓은 것인 문자열이 저장이 된다. 하지만, char 배열과 다르게 수정이 불가능한 Immutable class 이다. 따라서 문자열을 다루는 작업이 많이 필요한 경우엔 String class 대신 StringBuffer Class를 사용하는 것이 좋다. method int length() 문자열의 길이를 int type 으로 반환하는 method 이다. System.out.print(" str의 길이 : "); System.out.println(str.length()); char charAt(int idx) 문자열에서 지정된 인덱스(idx)에 있는 문자(char type)를 알려.. 2021. 7. 26. 힙[Heap], 삽입 및 삭제 힙 (Heap), 삽입 및 삭제 정의 최대힙/최소힙 ( Link : 2021.07.21 - [C++ Algorithm/ETC] - 힙 [Heap], 최대힙/최소힙 ) 에서 임의의 값을 삽입, 삭제할 때 O(logN) 의 시간복잡도로 해결을 할 수 있다. 이러한 1차원 array 에서는 임의의 값을 삽입하거나 삭제를 할 때 마다 O(N)의 시간이 소요가 되어 굉장히 비효율적이다. 최대힙/최소힙을 사용한다면 이는 이진트리로 이루어졌기 때문에 이 작업들이 O(logN)의 소요시간을 가진다. 삽입 최대힙/최소힙 에서 Data 의 삽입은 현재 Node중 가장 마지막 Node에 우선 연결이 된다. 힙(Heap)은 완전이진트리를 활용한 자료구조 이기에 삽입을 할 때 기존 Node 와 Swap을 하여 두지 않는 이상 .. 2021. 7. 22. 힙 [Heap], 최대힙/최소힙 힙 (Heap), 최대힙/최소힙 정의 힙(Heap) 이란 완전이진트리(Perfect Binary Tree) 를 응용한 자료구조이다. 완전이진트리는 아래와 같은 Binary Tree를 의미한다. 완전이진트리는, 위처럼 마지막 레벨을 제외하면 모두 포화상태이며 마지막 레벨에 해당되는 노드들은 모두 좌측으로 쏠려있는 Binary Tree 이다. 이를 이용해서 힙(Heap)이라는 자료구조에 접근을 할 수 있다. 예를 들어 만약 최소힙을 생성하게 되면, Parent node 는 항상 Child node 보다 작거나 같은 값을 가지게 된다. 설명 힙(Heap)은 일반적으로 어떠한 수의 배열에 있어서 최소값과 최대값을 구할 때 쓰인다. 최소값을 구할 때 쓰이는 힙(Heap)은 최소힙(Min Heap) 이라고 불리고 .. 2021. 7. 21. 투 포인터 알고리즘 (Two pointer Algorithm) 투 포인터 알고리즘 (Two pointer Algorithm) 개요 위와 같은 Array 에 대해서 array[0] + array[1] + ... + array[k] 의 값이 20이 넘을 때 k의 최소값을 구하라고 한다면, 위 주황색 포인터를 계속해서 1씩 증가시켜 가면서 20이 처음으로 넘는 index를 찾게 될 것 이다. 위의 경우 이 때의 정답은 5이다. 이 경우는 사실 많이 기초적이며 array에 대해서 이해를 하려고 공부를 할 때나 다루는 부분일 것이며 대부분의 사람들이 생각할 수 있을 것 이다. 그렇다면, 위와 같은 Array 에 대해서 부분합인 array[k] + array[k + 1] + ... + array[n] 의 값이 6에 해당이 되는 index가 연속되는 부분집합의 개수를 구하라면 .. 2021. 7. 20. 이전 1 ··· 3 4 5 6 7 8 9 10 다음 728x90
