꺼진불도다시보자

문제 https://www.acmicpc.net/problem/2607 2607번: 비슷한 단어 첫째 줄에는 단어의 개수가 주어지고 둘째 줄부터는 한 줄에 하나씩 단어가 주어진다. 모든 단어는 영문 알파벳 대문자로 이루어져 있다. 단어의 개수는 100개 이하이며, 각 단어의 길이는 10 이 www.acmicpc.net 접근방법 사이즈가 같은 경우와 한 사이즈 작은 경우, 한 사이즈 큰 경우를 나눠서 계산했다. map을 복사해와서, word에 있는 알파벳이 cand에 몇개 존재하냐를 세는 것이 포인트다. 만약 word에 D가 2개 있을 경우, cand에 D가 3개 있다면, 3개를 다 세면 안되고 2개만 세야하기 때문에 세면서 하나씩 빼준다. cand에 D가 1개 있다면, 1개만 셀 것이기 때문에 match..

문제 https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 접근방법 크루스칼 알고리즘을 사용했다. Edge와 DisjointSet의 클래스를 각각 선언해 사용했다. Kruskal 또는 prim 알고리즘을 구현할 때, 포인트는 Edge 클래스 내에 operator를 선언하는 것이다. 부등호의 방향이 >임을 잊지말자. DisjointSet 생성자에서 parent와 rank의 크기를 V+1으로 초기화해야하는데..

문제 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 접근방법 BFS를 활용해 최단거리를 구하는 문제다. queue를 정의하고, pair.first에 위치 저장하고, pair.second에 이동시간 저장했다. 포인트는 방문여부 체크로 중복을 줄여주는 데 있었다. 방문여부 체크를 안하면 메모리 초과로 실패했다. 1 2가 입력되면, 0이 정답이 되어야 하는데, 1이 나왔다. 알고보니 함수 리턴하는 과정에서 순서..

문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 접근방법 트리의 지름 구하는 방법은 임의의 노드 x로부터 가장 먼 노드를 하나 선택하고 그 노드로부터 가장 먼 노드와의 거리를 측정하는 것이다. 문제의 그림을 보면 직관적으로 이해할 수 있다. 가장 먼 노드를 찾는 것과 가장 먼 노드와의 길이를 측정하기 위해서 DFS알고리즘을 이용했다. 코드 #include #include #include #include #include ..

문제 https://www.acmicpc.net/problem/1918 1918번: 후위 표기식 첫째 줄에 중위 표기식이 주어진다. 단 이 수식의 피연산자는 알파벳 대문자로 이루어지며 수식에서 한 번씩만 등장한다. 그리고 -A+B와 같이 -가 가장 앞에 오거나 AB와 같이 *가 생략되는 등의 www.acmicpc.net 접근방법 well known중에 well known infix to postfix 문제다. 연산자들은 따로 모아뒀다가, 낮은 우선순위 연산자가 들어올 때, 한꺼번에 postfix에 넣어준다. 여기서는 +, -, *, /가 전부다. 곱하기 나누기가 들어오면 따로 모아놨다가, 더하기 빼기 들어왔을 때, 다 빼서 postfix에 붙이면 된다. 그리고 중요한건 '('가 들어왔을 때 어떻게 처리하..

문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 접근방법 DP를 이용해 풀었다. 분명히 맞는 거 같은데, 틀렸다고 나와서 한참 헤멨다. 알고보니 cache 배열의 범위가 틀렸었다. 단순히 n의 범위가 16까지라서 cache[16][16]으로 정의했는데, 내가 범위 체크를 함수 들어가기 전이 아니라 함수 들어가고 나서 하기 때문에, 16 크기의 house배열이 입력으로 들어오는 경우, cache 17을 접근하게 되는..

문제 https://www.algospot.com/judge/problem/read/TRIANGLEPATH algospot.com :: TRIANGLEPATH 삼각형 위의 최대 경로 문제 정보 문제 6 1 2 3 7 4 9 4 1 7 2 7 5 9 4 위 형태와 같이 삼각형 모양으로 배치된 자연수들이 있습니다. 맨 위의 숫자에서 시작해, 한 번에 한 칸씩 아래로 내려가 맨 아래 www.algospot.com 접근방법 메모이제이션을 활용한다. 중복 계산을 없앨 수 있다. 완전 탐색이라면 최악의 경우 2^100 을 훨씬 넘어가지만, 메모이제이션을 활용하면, 저장된 값을 재사용가능하기 때문에, 100 * 100 = 10000 의 계산 내에서 해결 가능하다. 코드 #include #include #include..

문제 접근방법 코드 완전탐색 코드 : bool match(const string& w, const string& s) { //w[pos]와 s[pos]를 맞춰나간다. int pos = 0; while(pos < s.size() && pos < w.size() && (w[pos] == '?' || w[pos] == s[pos])) ++pos; //더이상 대응할 수 없으면, 왜 while문이 끝났는지 확인한다. //2.패턴 끝에 도달해서 끝난 경우, 문자열도 끝났어야 대응됨 if (pos == w.size()) return pos == s.size(); //4.*를 만나서 끝난 경우: *에 몇 글자를 대응해야 할지 재귀 호출하면서 확인한다. if (w[pos] == '*') for (int skip = 0;..

문제 접근방법 분할정복. 3개로 분할하는데, 하나는 왼쪽, 하나는 중간, 하나는 오른쪽. 주목해봐야할 부분은 중간에 걸친 사각형의 최댓값을 계산하는 부분이다. for loop이 돌 때마다 더 높은 막대를 선택하고, ret와 비교해서 더 큰 값을 고른다. 코드 #include #include #include #include using namespace std; #define FOR(i, n) for (int i=0;i> C; while(C--) { cin >> n; h = vector(n); FOR(i, n) cin >> h[i]; cout

c++ STL에서 제공해주는 헤더 안에는 next_permutation 함수가 있다. 다른 언어에는 없다고 한다. c++유저들의 특권인 셈이다. 이를 잘 이용하면 조합과 순열을 편하게 만들 수 있다. 아래 코드를 참고하자. 1,2,3,4,5를 이용해 next_permutation으로 순열을 만들 수도 있고, 이 5개의 원소중 3개를 순서상관없이 뽑고싶다면, prev_permutation과 temp = {1, 1, 1, 0, 0} 배열을 적절히 이용하면 된다. #include #include #include using namespace std; int main() { vector arr = {1, 2, 3, 4, 5}; vector temp = {1, 1, 1, 0, 0}; do { for (int i=0;i