url : https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상 정렬 문제에서 좀 더 정렬 조건을 추가한 문제이다. 위상 정렬 + 가능한 쉬운(작은 숫자의) 문제부터 정렬 => 오름차순 우선순위 큐를 사용한다. 코드 #include using namespace std; int n, m, a, b; vector graph[100004]; int indegree[32004]; vector result; void top..
url : https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 위상정렬 문제이다. 위상정렬 사이클이 없는 방향 그래프 (= DAG)의 모든 노드를 순서대로 나열할 때 사용 => 방향성 O, 순서 O, 사이클 X 이 문제는 사람들의 키를 순서대로 정렬하여 줄을 세우기 때문에(순서O, 방향성 O, 사이클 X) 위상 정렬로 문제를 푼다. 위상 정렬 템플릿을 그대로 사용하면 풀리는 문제이다. 코드 #include..
url : https://www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 오랜만에 다시 푼 dfs 문제! 코드 #include using namespace std; int n, temp, maxH, answer; int mp[104][104], visited[104][104]; int dy[]={-1,0,1,0}; int dx[]={0,1,0,-1}; void dfs(int y, int x, int h){ visited[y][x]=1; for(int i=0;ih){..
url : https://school.programmers.co.kr/learn/courses/30/lessons/160585 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 구현 구현 문제를 거의 처음 풀어보는데, 구현 문제는 1. 경우의 수 구하기 2. 반복되는 부분 함수 작성하기 를 생각하고 풀면 좀 더 편할 것 같다. 틱택토(tic-tac-toe) 문제 특히 위 틱택토 문제를 보면 O와 X가 번갈아서 나오는데, O가 이길 경우는 O의 개수가 X의 개수보다 1 더 많아야하고, X가 이길 경우는 X의 개수가 O의 개수와 같아야한다.
url : https://school.programmers.co.kr/learn/courses/30/lessons/154538 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr
url: https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 재귀 함수 작성시 고려할 점 재귀는 3가지를 고려하면 된다. 다음 경우, 불가능한 경우(종료 조건1), 리턴값 경우(종료 조건2) 이 문제가 완전탐색이고 그 중 DFS인 이유 이 문제는 주어진 숫자를 더하거나 빼서 target(특정 값)에 도달하는 경우의 수를 구하는 문제이다. 모든 경우를 고려해야하므로 완전탐색이고, 완전 탐색을 하기 위해서는 여러 알고리즘 방법(DFS, BFS, 백트래..
url: https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net LCS = 최장 공통 부분 수열 두 문자열에서 연속적이지 않으면서 한방향(동일한 순서)로 가장 긴 공통 문자열을 찾는 문제이다. DP 유형의 고전적인 문제(유형화된 문제)라고 할 수 있다. 점화식 인덱스가 각각 0~i, 0~j라고 할 때, dp 배열을 채워보자. 직전 문자 (각각 i-1 위치 문자와 j-1 위치 문자)가 같다면, i와 j위치 문..
url : https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 골드 5인데, 이진탐색 template을 알고있다면 풀 수 있는 문제이다. 최솟값, 최댓값 구하기 최솟값을 구할 경우 초기값은 최댓값(ex)합의 최댓값 or int 최댓값)으로, 최댓값을 구할 경우 초기값은 최솟값(ex)합의 최소 or int 최소값)으로 설정하기 이진탐색 Tip 이진탐색은 1. 조정해야하는 값(문제에서 구하는 값)의 상한과 하한을 구하..
