내가 그때 이걸 알았더라면

이 글에서는 fstream 라이브러리를 이용한(C++11 이상 버전 권장, 버퍼 객체 bool 타입으로 변환 가능해서) 파일 입출력 예제를 다뤄보겠다. 수업에서 배운 dfs, bfs, 다익스트라 알고리즘 등을 복습할 겸 C++로 코드를 짜보았다. 1. include 먼저 기본 입출력에 필요한 iostream, 그래프 정보를 저장하는 데 쓸 이차원 배열을 동적으로 생성하기 위한 vector, 파일 입출력을 위한 fstream 라이브러리를 include 해온다. #include #include #include using namespace std; *std 네임스페이스를 미리 선언했다. 이렇게 되면 원래는 std::fstream 형인 fstream을 그냥 fstream으로 사용할 수 있다. 2. 변수들과 파일..

java에서는 String 클래스에 문자열을 특정 문자열을 인수로 받아 쪼개주는 메서드인 .split()이 존재한다. 하지만, "." 이나 "\" 같은 예약어들은 함부로 사용할 수 없다. 그럴 땐 다음과 같은 방법을 이용할 수 있다. 1. "." 으로 split() 하기 .split("//."); .split("[.]"); 2. "\" 으로 split() 하기 .split("////"); 참고 블로그 : https://mousevm.tistory.com/224 String.split( ) 함수에서 구분자로 역슬래시("\") 사용하기. 오늘도 역시 삽질 끝에 알아낸 소중한 하나의 정보를 기록합니다. ㅋㅋ 오늘은 자바의 String.split( ) 함수에서 구분자로 역슬래시("\")를 사용해서 문자열을 분리..

자바에서 스윙 라이브러리를 사용하려고 다음과 같이 import시 오류가 나는 상황이 있었을 것이다. import javax.swing.*; 이때, java 11 이후로는 java.base 모듈만 기본으로 포함하므로, 그 이외의 다른 모듈들을 사용하기 위해서는 따로 불러오기가 필요하다. 따라서 module-info.java 파일에 다음과 같이 작성해준다. module { requires java.desktop; } 예시) 참고 블로그 : https://daily-life-of-bsh.tistory.com/129

1. 서론 다익스트라 알고리즘이란, 그래프 상에서 한 정점에서 다른 (모든) 정점으로의 최단경로를 구하기 위해 사용되는 알고리즘이다. 인접 리스트와 우선순위 큐를 이용해 손쉽게 구현할 수 있다는 장점이 있어 많은 사람들이 사용한다. 2. 설명 먼저, 다음과 같은 그래프가 있다고 가정하자. 다익스트라 알고리즘은 먼저 시작점 자신의 거리를 0으로 두고 다른 갈 수 있는 모든 점들의 최단거리값 (dist[])를 업데이트한다. 업데이트시 만약 [현재 노드의 cost + 현재 가리키는 노드로 가는 edge의 cost] 값이 가리키는 노드의 dist값보다 작다면, dist를 업데이트한다. 그 다음, 방문하지 않은 다른 모든 점들중 가장 dist값이 작은 노드를 시작점으로 잡고, 다시 dist를 업데이트한다. 이를 ..

1. 변수 한 개를 추가로 생성한다. void swap(int *a, int *b){ int tmp = *a; *a = *b; *b = tmp; return; } 2. xor 연산을 사용한다. void swap(int *a, int *b){ *a ^= *b; *b ^= *a; *a ^= *b; return; } 3. 덧셈 연산을 사용한다. void swap(int *a, int *b){ *a = *a + *b; *b = *a - *b; *a = *a - *b; return; } // 또는 더 간단하게 void swap(int *a, int *b){ *a += *b; *b = *a - *b; *a -= *b; return; } 1. 방법은 간편하지만 추가로 변수를 생성해야 한다는 단점이 존재하고 (메모리 ..

참고 링크 : https://gist.github.com/480/4681b67d2a906db8c6c1321cc678f05f github 리모트 리포지토리 변경하기 github 리모트 리포지토리 변경하기. GitHub Gist: instantly share code, notes, and snippets. gist.github.com 1. 기존 repository pull/push 하기 git pull git add . git commit -m "clean push" git push 2. 기존 repository remote 제거 git remote remove origin 3. 새 repository remote 추가 git remote add origin [깃 주소]

1. 문제 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 양의 정수 n(1 ≤ n ≤ 100,000)과 n개의 원소로 이루어진 수열 An이 주어진다. 이때, An에서 가장 큰 구간합을 구하여라. 2. 해결 방법 1. Brute Force 먼저 가장 간단한 방법은, Brute Force 방식으로 크기 n의 int 배열을 만들어 i번째 자리에서 1~i-1번째 자리부터에서의 합을 구해 O(n^2)(1~i에서 O(n), 이를 1번째부터 i-1까지 반복하므로 O..

1. 문제 https://www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소 www.acmicpc.net 집합 A에는 속하지만, B에는 속하지 않는 원소들의 개수와 원소들을 모두 출력하는 문제이다. 집합에서 A - B (차집합)의 개념이 등장한다. 2. 풀이 방법 배열이나 리스트 등을 사용하면 해당 자료형 안에 특정 원소가 있는지 확인하려면 O(1)의 시간이 걸리기에, 접근하는데 시간이 O(1)이 걸리는 맵 자료형을 이용하여 문제를 해결했다. 먼저 A와 ..

1. 문제 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 길이가 n일 수열이 주어질 때, 이 수열에서 가장 긴 증가하는 부분 수열의 길이(연속일 필요는 없지만 증가해야 함)를 구하면 되는 문제이다. 2. 풀이 방법 LIS 문제의 해결법은 이 블로그에 잘 나와 있다. https://seungkwan.tistory.com/8 가장 긴 증가하는 부분 수열 (Longest..

1. 문제 https://www.acmicpc.net/problem/19566 19566번: 수열의 구간 평균 길이가 $N$인 수열 $A_1, A_2, \cdots, A_N$이 주어진다. 구간에 있는 모든 수들의 평균이 정확히 $K$인 구간의 개수를 구해 보자. www.acmicpc.net 길이가 n인 수열이 주어질 때, 이 수열에서 평균이 k인 구간의 개수를 구하면 되는 문제이다. 2. 해결 방법 1. 먼저 평균의 의미를 다시 생각해보자. 평균 = 원소들의 합 / 원소들의 개수이다. 양변에 원소들의 개수를 곱하면, 다음과 같이 쓸 수 있다. 구간합 = 평균 * 구간길이 이다. 즉, 구간합을 원소들의 개수로 나눠 이를 평균과 비교할 것이 아니라, 구간합이 구간길이 * 평균과 같은지만 비교해주면 된다는 것..