기억보다는 기록을 해볼까

문제 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 생각 처음에는 노드 들을 다 순회해서 끝 노드까지의 거리 중 가장 큰 2가지가 지름이다. 라는 방식으로 접근을 했다. 풀면서 계속 꼬여서 결국에 다른 살마의 코드를 참고했다. 1번 노드부터 시작을 해서 dfs로 탐색을 하여 거리가 1번 노드로부터 가장 먼 노드를 구한다. 이후 가장 먼 노드부터 시작을 해서 같은 dfs로 탐색을 하여 가장 거리가 먼 노드와의 거리가 곧 지름..

문제 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 생각 다익스트라 알고리즘을 활용한다. 2개의 점을 반드시 지나야 하므로 2가지를 어떤 순서로 통과하는지에 따라 2가지의 경우의 수가 나온다. 따라서 1(S) -> v1 -> v2 -> N 1(S) -> v2 -> v1 -> N min(Stov1 + v1tov2 + v2toN, Stov2 + v1tov2 + v1toN) 이 답이 된다. 코드 #inc..

문제 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 생각 문자열에 많이 약하다는 생각으로 넘겼던 문제이다. 그러나 문자열이 아니라고 생각해도 차이가 없다. (선입견) LCS 알고리즘을 참고했다. 이 문제는 최대 수열의 길이만 구하면 되는 문제이지만 언제든지 최대 수열을 구하라는 문제가 있을 수 있다. [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 L..

문제 https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 생각 3가지의 상태에 따라 움직일 수 있는 환경이 다르므로 3가지의 케이스로 분류하였다. 가로 대각 세로 코드 #include using namespace std; int map[17][17]; int n; //방향 가로, 대각, 세로 int dy[3] = {0, 1, 1}; int dx[3] = {1, 1, 0}; int cnt = 0; //현재의 상태(state)..

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 생각 브루트포스 알고리즘으로 전체를 다 순회해야 한다. 모든 집에 대한 모든 치킨집까지의 거리를 계산해 최솟값을 저장한다. 치킨집을 고르는 과정에서는 조합을 이용해 치킨집을 고르면 된다. void dfs(int idx, int chosen) { if(chosen == m) { int tmpSum = 0; for(int i = 0; i < h.size(); i++) { i..

문제 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 생각 아오 bool을 선언만 하면 알아서 다 false로 되는 줄 알았는데 아오 아니네 bool vst[9][9] = {{false}}; //vst선언 이거 뒤에 {{false}} 를 안해줬더니 계속 엉뚱한 값 나와서 헤맸네 아오 이 전에 굉장히 이 문제로 많은 것을 배웠다. 2차원 배열을 돌 때 2차원을 1차원 배열로 생각을 해 다음과 같이 2차원 배열을 탐색 할 수 있다. 그런데 위의 i, j, k 자체로는 2차원 배열의 위치를 표현 할 수 없으므로 i / m, i ..

오늘은 당직을 가야 하니 간단한 1 문제만 풀고 가야겠다. 재귀를 통한 순열 구현문제이다 이제부터는 순열 관련 문제들이 꽤 포스팅될 것 같다. #include using namespace std; int n; int arr[9]; bool visited[9]; int m; void dfs(int num, int cnt) { if(cnt == m) { for(int i = 0; i < m; i++) cout m; dfs(1, 0); }

하.. 한문제 골치 아프게 계속 안풀렸다. 오늘 공부한 백준 : 5430 AC #include #include #include using namespace std; int main() { int T; cin >> T; while(T--) { deque dq; string str; cin >> str; int n; cin >> n; string arr; cin >> arr; bool right = true; bool end = false; for(int i = 0 ; i < arr.size(); i++) { if(arr[i] == '[' || arr[i] == ',' || arr[i] == ']') continue; int num = arr[i] - '0'; while(arr[i + 1] != ',' &&..

정확히 24일차는 아니지만 블로그 쓰는 횟수가 24번쨰이므로 그렇다고 치자 최근 싸지방을 잘 이용하지 못해 자주 못옴 ㅠㅠ 오늘 공부한 백준 (2667, 6064, 7569, 11286, 11403, 16928) 이제 BFS에 꽤나 익숙해졌다. 혼자서 구현할 수 있는 정도 내일부터는 골드 5문제들을 풀게 될 것이다. (아직 실버 몇개 안 푼게 있지만) 큐의 갯수를 세야 할 때 자주 썼다. typedef pair pii; queue q; 문제의 input이 이런 식으로 가로로 빈칸 없이 나올 때 10101101 00110101 00011010 11010110 아래와 같이 string으로 받은 다음에 int형으로 다시받는 방법을 쓴다. 아니면 그냥 string으로 받아서 string으로 계속 풀수도 있다. ..

오늘 공부한 백준 1012, 1541, 5525 (미완성) 1012 DFS!!!! for(int i = 1; i m) continue; if(vst[ny][nx] == 0 && map[ny][nx] == 1){ vst[ny][nx] = 1; q.push({ny, nx}); } } } } } } 1541 문자열 파싱 for(int i = 0; i < str.size(); i++){ if(str[i] == '-' || str[i] == '+'){ if(minus == true){ sum -= tmp; tmp = 0; } else { sum += tmp; tmp = 0; } if(str[i] == '-'){ minus = true; } } else { tmp *= 10; //previous number tmp..