Posts
begin_fill
Cancel

크루스칼 알고리즘(Kruskal Algorithm)

크루스칼 알고리즘이란? MST(최소 신장 트리)를 찾는 알고리즘. Greedy method(탐욕적 방법)을 이용한다. Union-Find를 이용하여 사이클 탐색한다. 유니온 파인드를 모른다면 유니온 파인드를 먼저 읽어야 한다. 크루스칼의 핵심 개념은 간선을 거리가 짧은 순서대로 그래프에 포함시키는 것이다. 모든 노드를 최소 비용으로 ...

백준 16637 괄호 추가하기 c++

문제 https://www.acmicpc.net/problem/16637 문제해설 수식이 주어지고 그 수식에서 괄호를 만들어 연산했을 때 최대값을 구하는 것이다. 괄호에는 연산자가 하나만 들어갈 수 있다. 숫자 2개만 묶을 수 있다는 소리이다. 그리고 괄호를 제외한 연산에는 우선순위가 없다. 곱하기 연산이 더하기나 빼기보다 우선되지 않고 앞에서부터...

백준 14464 소가 길을 건너간 이유 4 c++

문제 https://www.acmicpc.net/problem/14464 문제해설 소가 길을 건너는데 닭의 도움이 무조건 필요하다. 닭은 x시간에만 다리를 건너게 해줄 수 있고, 소는 a~b시간 사이에 다리를 건널 수 있다. a와 b시간 사이에 x가 있어야 소가 다리를 건널 수 있는 것이다. 그렇게해서 최대 몇마리의 소가 다리를 건널 수 있는지 ...

백준 17218 비밀번호 만들기 c++

문제 https://www.acmicpc.net/problem/17218 문제해설 문자열 2개가 주어지고 두 문자열에서 가장 긴 부분 문자열을 구하면 된다. 문제풀이 그냥 LCA 알고리즘을 써서 해결할 수 있다. 다만 기본 LCA에서는 문자열의 길이만 구하기 때문에 직접 문자열을 찾는 추가적인 구현만 하면 된다. 문자열을 구하는 방법은 LCA...

유니온 파인드(Union-Find)

유니온 파인드란? 유니온 파인드는 그래프 알고리즘으로 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 서로소 집합, 상호 베타적 집합(Disjoint-Set)으로도 불린다. 노드를 합치는 Union연산과 노드의 루트 노드를 찾는 Find연산으로 이루어진다. 트리 구조로 이루어진 자료구조 중 한가지로 생각되기도 한다. 이...

AWS ec2 인스턴스 생성과 SSH 연결

AWS ec2 인스턴스 생성 1. aws에 접속하고 지역이 서울로 되어있는지 확인한 후 EC2로 들어간다. 2. 인스턴스 시작을 누른다. 3. 프리티어만을 체크해주고 우분투를 선택한다. 4. 검토 및 시작을 누른다. 5. 보안 그룹 구성으로 가서 내용을 추가해준다. SSH는 22 HTML은 80 추가적으로 내가 참여했던 프로젝트의...

vue 댓글 줄바꿈 기능

문제점 댓글이 입력시에 줄바꿈을 한 것이 제대로 처리가 안되어서 표시가 되었다. 예를들어 이런식으로 개행문자 처리를 못하는 것처럼 보였다. 개선방법 해결 방법은 생각보다 간단한데 style 태그에 white-space:pre; 라는 속성만 추가해주면 되었다. 찾아보니 white-space라는 속성은 요소가 공백을 처리하는 법을 지정하는 옵션이었다...

백준 1528 금민수의 합 c++

문제 https://www.acmicpc.net/problem/1528 문제해설 정말 어려웠던 문제 더 열심히 해야되는것 같다. 결국 내 힘으로 풀지 못하고 풀이를 참고했다. 문제는 1000000이하의 수 n이 주어질 때 4와 7로만 이루어진 수들의 합으로 n을 표현하는 것이다. 처음에는 문제를 잘못 이해해서 4나 7의 합으로만 표현했는데 그게 아...

sync_with_stdio(false) 쓸 때 주의할 사항

주의할 점 백준 문제를 풀다가 아래 코드가 틀렸었다. 왜 틀렸나 봤는데 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);이 부분 때문이었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32...

백준 2725 보이는 점의 개수 c++

문제 https://www.acmicpc.net/problem/2725 문제해설 정사각형의 좌표 n이 주어지면 원점에서 자연수로 된 좌표가 몇개 보이는지 찾는 문제다. 다만 기울기가 같아 겹치는 좌표는 제외한다. 문제풀이 풀이의 아이디어를 생각해내는게 참 어려운 문제같다. 생각만 해낸다면 구현은 어렵지 않다. 일단 기울기로 접근해보자 기울기가 같...