url : https://school.programmers.co.kr/learn/courses/30/lessons/181188 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제가 그리디인 이유 요격하는데 필요한 최소한의 미사일 갯수 => 매 순간 최소의 미사일 개수를 선택하고, 그것을 계속하면 전체적인 최소 미사일 개수가 나온다 (=최적 부분 구조) ✅ 구간이 나오고, 정렬 가능하다면 그리디를 생각하기! 그리디 중 구간 스케줄링 1. sort(끝점 기준 정렬) 2. 기준값이 시작값보다 작으면 cnt++ 코드 #include using namespace ..
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위치 문..
