'백준' 태그의 글 목록

[백준] 9251번 LSC (C)

문제 주소 백준 9251번 LSC 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 알고리즘 DP 힌트 첫번째 문자열의 i번 문자까지의 문자열과 두번째 문자열의 j번 문자까지의 문자열의 LCS의 길이를 구한다. 문제풀이 dp[i][j]에 문자열 a의 i번 문자까지의 문자열과 문자열 b의 j번 문자까지의 문자열의 LCS의 길이를 저장한다. 가장 끝의 문자만 비교하는 식으로 길이를 구해나갈 수 있다. 끝 문자가 같을 경우 dp[i][j] = dp[i-1][j-1]+1 끝..

Problem Solve/Dynamic Programming 2020. 4. 21. 09:49

[백준] 2565번 전깃줄 (C)

문제 출처 한국정보올림피아드 지역본선 2007 초등부 4번 문제 주소 백준 2565번 전깃줄 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 위치의 번호가 차례로 주어진다. 위치의 번호는 500 이하의 자연수이고, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다. www.acmicpc.net 알고리즘 DP 힌트 서로 교차하지 않는 전깃줄의 최대 개수를 구한다. 문제풀이 서로 교차하지 않는 전깃줄의 최대 개수를 구하기 위해선 한 쪽 전봇대 기준으로 정렬을 한 뒤 나머지 전봇대의 번호에서 가장 긴 증가하는 수열을 구하면 된다. #include ..

Problem Solve/Dynamic Programming 2020. 4. 12. 00:31

[백준] 1436번 영화감독 숌 (C)

문제 주소 백준 1436번 영화감독 숌 알고리즘 브루트 포스 힌트 7번째 짜리에서 6이 연속으로 3번 이상 나오는 경우가 10000번이 넘는다. (9*9*9*9*5) 문제 풀이 n의 범위가 10000 이하이기 때문에 1부터 1씩 증가 시키면서 n번째의 수를 찾아도 제한 시간안에 풀 수 있다. count6 함수는 6이 연속된 개수를 확인하는 함수이다. #include using namespace std; int count6(int i){ int cnt=0,flag=0; while(i>1){ if(i%10==6){ if(!flag) flag=1; cnt++; } else if(flag){ if(cnt>=3) return cnt; flag=0; cnt=0; } i/=10; } return cnt; } int ..

Problem Solve/Brute Force 2020. 3. 27. 14:13

[백준] 1018번 체스판 다시 칠하기 (C)

문제 주소 백준 1018번 체스판 다시 칠하기 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다. www.acmicpc.net 알고리즘 브루트 포스 힌트 정답 배열을 만들어 놓고 비교한다. 풀이 B와 W가 반복해서 나와야 하는데 B가 먼저 올 수 도 있고 W가 먼저올 수도 있다. 이것을 따로 계산해주면 복잡해서 W가 먼저 나온다고 가정을 하고 문제를 푼다. 이 때 색을 칠하는 개수와 64 - 색을 칠하는 개수중 더 작은 수가 색을 칠하는 최소 개수가 된다. 64 - 색을 칠하는 개수가 B가 먼저 나올 경우를 생각해 주는 것이다. #i..

Problem Solve/Brute Force 2020. 3. 27. 01:21

[백준] 7568번 덩치 (C)

출처 한국정보올림피아드 지역본선 2013 초등부 2번 문제 주소 백준 7568번 덩치 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x,y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x,y), (p,q)라고 할 때 x>p 그리고 y>q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56,177), (45,165) 라고 한다면 A의 덩치가 B보다 큰 www.acmicpc.net 풀이 0 ~ n-1을 확인하면서 덩치가 큰 사람의 수를 세어준다. #include using namespace std; i..

Problem Solve/Brute Force 2020. 3. 22. 22:33

[백준] 2231번 분해합 (C)

출처 ICPC Asia Regional Seoul 2005 B번 문제 주소 백준 2231번 분해합 힌트 모든 경우를 다 확인해도 제한 시간 안에 가능하다. 풀이 제한시간이 2초이고 입력받는 n의 범위가 1,000,000이하이다. 이는 O(n)풀이가 가능하다는 말이다. 따라서 1부터 n까지 확인하여 분해합이 n과 같다면 그 수를 출력하면 된다. #include using namespace std; int main(){ int n; cin>>n; for(int i=1;i=1;j/=10){ sum+=tmp/j; tmp%=j; } if(sum==n){ cout

Problem Solve/Brute Force 2020. 3. 22. 22:10

[백준] 1260번 DFS와 BFS (C++)

문제 주소 백준 1260번 DFS와 BFS 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 알고리즘 DFS, BFS 풀이 간단한 DFS와 BFS 구현 문제이다. DFS는 재귀함수와 스택으로 구현할 수 있고, BFS는 q로 구현해야 한다. DFS를 하고 check배열을 초기화 해주어 BFS를 한다. #include #include using namespace std; int graph[1001][1001]; int check[1001]; int n, m; void dfs(i..

Problem Solve/DFS & BFS 2020. 3. 21. 15:37

[백준] 2206번 벽 부수고 이동하기 (C++)

문제 주소 백준 2206번 벽 부수고 이동하기 알고리즘 BFS 힌트 어떤 위치에 온 상태가 벽을 부수고 온 것인지, 벽을 부수지 않고 온 것인지 구분 해야 한다. 풀이 위치(a, b)와 상태(w : 벽을 부쉈다면 1 부수지 않았다면 0)를 원소로 가지는 dot구조체를 만들어 준다. check배열도 위치와 상태를 담을 수 있도록 3차원으로 선언 해 준다. 현재의 위치가 목표 위치라면 ans를 출력하고 main 함수를 종료 해 준다.q를 다 확인 할 때까지 목표점에 도착하지 못하였다면 목표점에 도달할 수 없는 것이므로 -1을 출력해준다. 벽이 있고 벽을 뚫지 않았다면 q에 넣어주고 벽이 없다면 check배열을 하여 중복되지 않도록 q에 넣어준다. #include #include using namespace ..

Problem Solve/DFS & BFS 2020. 3. 21. 15:09

[백준] 1697번 숨바꼭질 (C++)

출처 USACO US Open 2007 Contest Silver 2번 문제 주소 백준 1697번 숨바꼭질 1697번: 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 www.acmicpc.net 알고리즘 BFS 힌트 check 배열(방문 배열)에 그곳에 가게 되는 시간 + 1을 저장한다. 풀이 수빈이가 이동할 수 있는 위치는 3군데가 있다. 각 각의 위치가 주어진 범위를 벗어나지 않는 지 확인을 한 후 왔던 곳인지 확인을 한다. 처음 위치를 1로 하고 (이는 check배열의 본질을 잃지 않기 위함이다.) check[다음위..

Problem Solve/DFS & BFS 2020. 3. 21. 01:01

[백준] 1023번 유기농 배추 (C)

문제 주소 백준 1012번: 유기농 배추 알고리즘 DFS, Flood Fill 힌트 Flood Fill 알고리즘을 사용하여 구역의 개수를 구한다. 풀이 배추들의 위치를 입력받기 전에 in배열과 check배열을 초기화 해주어야 한다. check가 되어 있지 않으면서 배추가 있는 곳을 탐색하여 주변 배추들이 있는 곳을 check한다. #include using namespace std; int n,m; int in[50][50]; int check[50][50]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; void fill(int a, int b){ check[a][b]=1; for(int i=0;i=n || nb>=m||nax; for(int q=0;q>m>>n>>c; f..

Problem Solve/DFS & BFS 2020. 3. 20. 23:50

낭만 IT

백준 → (19)건