백준

https://www.acmicpc.net/problem/15723문제3a is bb is cc is d3a is da is cd is aa는 b다. b는 c다. c는 d다.그럼 a는 d다. (o)그럼 d는 a다. (x)풀이#include using namespace std;vector alpha(26, -1);int find(int target, int from){}int main(){ ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int n, m; cin >> n; cin.ignore(); while (n--) { string s; getline(cin, s); int p, c; ..

https://www.acmicpc.net/problem/14940문제n * m 보드에서..0 : 갈 수 없는 땅1.: 갈 수 있는 땅2 : 목표 지점보드의 각 자리에서 목표 지점 까지 도달할 거리를 출력하자만약 갈 수 있는 땅인데 도달 할 수 없는 경우 -> -1 을 출력갈 수 없는 땅인 경우 -> 0을 출력풀이처음 풀이에서는만약 갈 수 있는 땅인데 도달 할 수 없는 경우 -> -1 을 출력 조건을 놓쳐서 틀렸었다.정신을 차리고 풀기.#include using namespace std;int board[1001][1001];vector> dist(1001, vector(1001, -1));int dx[4] = {0, 1, 0, -1};int dy[4] = {1, 0, -1, 0};struct coord..

https://www.acmicpc.net/problem/5014 문제 건물은 1층부터 F층까지 존재현재 위치: S층, 목적지: G층버튼 U: 현재 층 + U버튼 D: 현재 층 - D한 번에 한 방향으로만 움직일 수 있음 풀이 두가지 풀이 방법이 있다. 1. bfs : 를 담은 큐, 방문 여부를 체크하는 자료구조가 필요하다. 이 방법은 { 현재 층 + u, 현재 층 - d }를 기준으로 다음 층을 탐색한다. 2. bfs : 방문 여부 자료구조를 넣을 때, 이동 횟수를 해당 자료구조에 쓰면서(int형) 방문여부를 표기한다. 이 방법은 자료구조를 하나만 쓰면 되기 때문에 더 간단하고, 이 문제에만 국한하지 않고 다른 층에 대한 기록도 board에 남기 때문에 활용가능성이 더 높지 않을까? 생각되었다. #i..

https://www.acmicpc.net/problem/11725문제바로 위의 부모를 찾는 트리 문제다.가장 상위 노드를 1로 한다.풀이endl로 출력해서 시간초과가 났었다. \n을 생활화하기..#include using namespace std;vector> graph(100001);int board[100001];int main(){ ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; for (int i = 0; i > n1 >> n2; graph[n1].push_back(n2); graph[n2].push_back(n1); } board[1] = true; queue q; q.pu..

https://www.acmicpc.net/problem/1916문제다익스트라 문제다.다익스트라란?가중치가 양수인 그래프에서 시작점에서 다른 모든 정점으로의 최단거리를 찾는 알고리즘이다.풀이이 문제를 처음 접근할 때는 단순하게 queue 를 이용해 풀수 있다고 생각했다.시간초과가 났다ㅜㅜㅋ 머머..다익스트라 템플릿을 다시 공부하는 좋은 기회가 되었다..우선은 bfs가 효율적이지 못한 이유는 무엇일까?이 문제에서는 내가 푼 방식대로 접근하면,탐색순서를 queue로만 결정하기 때문에3번 도시를 비용 5인 경로로 먼저 방문해버림이후에 3을 다시 queue에 넣고 최소비용으로 갱신즉, 필요 없는 "비용 큰 경로"도 다 탐색해야 함이러한 이유로 시간초과가 난다.다익스트라로 바꾸면?priority_queue를 사용..

https://www.acmicpc.net/problem/18352문제한 방향 그래프가 주어지고,,시작 노드가 주어진다..특정 깊이에 존재하는 노드들을 출력하는 문제다. 풀이문제의 범위 조건을 잘 확인하자..정답 출력시 오름차순으로 출력해야한다. 역시 조건을 잘 확인하자..#include using namespace std;vector> graph(300001);int min_score = INT_MAX;vector ans_list;int n;void print_answer(){ sort(ans_list.begin(), ans_list.end()); if (ans_list.size()) { for (auto e : ans_list) { cou..

https://www.acmicpc.net/problem/2660문제// 다른 모든 회원과 친구 -> 1점// 다른 모든 회원이 친구 | 친구의 친구 -> 2점// 다른 모든 회원이 친구 | 친구의 친구 | 친구의친구의 친구 => 3// ...// 회장 : 회원들 중 점수 가장 적음 그러니까, 한 다리를(depth) 건널 때마다 점수가 추가된다는 것이고,그 depth가 가장 작은 수준에서 친구를 찾을 수 있는 사람이 회장이 된다는 것이다. 풀이#include using namespace std;// 다른 모든 회원과 친구 -> 1점// 다른 모든 회원이 친구 | 친구의 친구 -> 2점// 다른 모든 회원이 친구 | 친구의 친구 | 친구의친구의 친구 => 3// 회장 : 회원들 중 점수 가장 적음vecto..

https://www.acmicpc.net/problem/11403 문제가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 풀이알고리즘 분류를 보니, 플로이드-워셜 문제로 되어있다.이 알고리즘은 가중치가 음수도 처리할 수 있는 알고리즘이라고하는데,가중치가 음수가 없는 이 문제가 왜 플로이드 워셜로 분류되었는지 모르겠다. 아무튼 이 문제는 각 노드를 돌면서, 해당 노드와 연결될 수 있는 다른 노드들이 있는 지 확인하기 위한 큐를 활용해 풀었다.#include using namespace std;int board[101][101];vector> graph(101);int n;void printer..

https://www.acmicpc.net/problem/2193문제[조건]1. 1로 시작2. 11이 부분 문자열로 올 수 없음. 그림으로 그려보니dp[i] = d[i-1] + d[i-2] 라는 점화식이 나오는 걸 발견했다. 왜 이런 결과가 나왔을까 생각해봤다.0은 그 뒤에 0과 1이 올 수 있고, 1은 뒤에 0만 올 수 있다. 4자리 이친수를 찾아보면 다음과 같다.3번째 자리의 0과 1에서 부터 0, 1, 0이 뻗어나와야 하고,이는 2번째 자리에서 3번째 자리를 유도하는 방식과 일치한다. 3번째 자리의 0에서부터 0, 1이 뻗어나와야하고,이는 1번째 자리에 2번째 자리를 유도하는 방식과 일치한다. 따라서, 위와 같은 점화식( dp[i] = d[i-1] + d[i-2] )이 유도된다. 풀이#inclu..

https://www.acmicpc.net/problem/1912문제수열이 있을 때, 부분 수열의 합의 최댓값을 구하기점화식1. a[i] = max(a[i-1] + a[i], a[i])2. max_val = max(a[i], max_val) 첫번째 식은, (1) 이전 값들을 반영한 값과 (2) 반영하지 않은 값을 비교해서 더 큰 값을 저장하도록 하기 위함이다. 두번째 식은, (1) 현재 차례에서 반영된 값과, (2) 전역 최댓값을 비교해서 더 큰 값으로 갱신하기 위함이다. 처음에는 스택으로 푸는 건가,, LIS(최장 증가 수열)의 응용인가..싶었는데,, 그냥 DP다.. 점화식을 잘 찾아보자.. 풀이#include using namespace std;int main(){ ios::sync_wit..