백준알고리즘

[백준 9251] LCS C++

www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최대공통부분 수열의 문제입니다. 처음에 용어가 헷갈렸는데, LCS는 2가지의 용어가 있습니다. 1. LCS (Longest Common Substring) 최대공통부분문자열 2. LCS (Longest Common Subseqeunce) 최대공통부분수열 입니다. 둘의 큰 차이는 연속하냐 안하냐의 차이인데, 문자열의 경우 연속하는 문자열중 최대의 공통 부분 문자열이고,..

[백준 11724] 연결 요소의 개수 C++

https://www.acmicpc.net/problem/11724 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 이번 시간은 그래프의 기본인 연결 요소의 개수를 구하는 문제의 풀이법을 설명하겠습니다. 문제에서 조건은 방향이 없는 그래프라고 말하고 있습니다. 입력으로 정점의 개수 N과 간선의 개수 M을 입력받고요, 연결된 요소가 총 몇개 있는지 구하는 문제입니다. 이 문제는 DFS, BFS로 어느것으로 풀어도 되지만, 저는 DFS를 이용해서 깊..

[백준 16929] Two Dots C++

https://www.acmicpc.net/problem/16929 16929번: Two Dots 첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문�� www.acmicpc.net 이번 시간은 Tow Dots 문제 풀이법에 대해 설명드리겠습니다. 같은 색깔에 한해서 Circle이 존재하느냐를 찾는 문제입니다. 그래프 탐색 알고리즘인 BFS와 DFS 중 어떤 것을 사용하면 좀 더 효율적으로 사용할지 고민하다가 DFS 깊이 탐색으로 일정하게 쭉 들어가면서 탐색하면 될 것이라고 생각했습니다. DFS를 구현하는 방법은 대표적으로 2가지가 있습니다. 1. Stack을 이..

[백준 2667] 단지번호붙이기 C++

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. � www.acmicpc.net 안녕하세요. 현's story 입니다. 이번 시간에는 단지번호붙이기 풀이법에 대해 설명해드리겠습니다. 이 문제의 경우 여러가지 변형된 문제를 다수 풀어본 경험이 있습니다. 자신감(?)에 넘쳐서 바로 풀었더니!!!땅 하고 프로그램이 안돌아가더라고요.. 다시 주의깊게 보니까 입력이 변수 간에 서로 띄워져있지 않고 모두 붙여져 있는 형태로 입력이 들어오기 때문에 한자리만 입력받을 필요가 생겼습니다. i..

[백준 12931] 두 배 더하기 C++

https://www.acmicpc.net/problem/12931 12931번: 두 배 더하기 모든 값이 0으로 채워져 있는 길이가 N인 배열 A가 있다. 영선이는 다음과 같은 두 연산을 수행할 수 있다. 배열에 있는 값 하나를 1 증가시킨다. 배열에 있는 모든 값을 두 배 시킨다. 배열 B가 주� www.acmicpc.net 문제풀이 0으로 채워진 배열에서 1. 배열 중 하나의 값을 1 증가 2. 배열의 모든 값을 두배 시킴 의 방법을 사용해서 입력으로 주어진 배열을 찾는데 최소 횟수를 구하는 문제인데, 역으로 입력으로 주어진 배열에서 0으로 채워지게 하려면 최소 몇번을 구해야하는지로 바꿔서 풀었습니다. 다행이도, 2배와 1추가는 홀짝으로 구분할 수 있기 때문에, 모든 배열이 0을 만나지 않는 한 무..

[백준 10819] 차이를 최대로 C++

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 이번 포스트는 백준 문제의 브루트포스 문제 중 하나인 '차이를 최대로'의 문제와 풀이법을 포스팅하려고 합니다. 먼저 문제는 N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |[A[0] - A[1]| + |[A[1] - A[2]| + .... + |[A[N-1] - A[N-1]| 입력 : 첫 째줄 N (3 n; fo..