loltochess

알고리즘 문제를 풀기 시작한 지도 벌써 1년 반이 지났다.처음에는 이런 문제들을 왜 풀어야 하는지에 대한 의문이 많았다.주변 지인들이 알고리즘 문제를 푸는 모습을 몇 번 본 적은 있었지만 나와는 거리가 먼 이야기처럼 느껴졌다.코딩을 열심히 하는 친구들은 보통 알고리즘 공부도 병행하는 경우가 많았던 것 같다.사실 나는 어떤 것을 공부해야 할지 방향을 잡지 못한 상태였고, 그러던 중 일단 알고리즘이라도 풀어보자는 마음으로 시작하게 되었다.막상 시작해보니 말도 안 되는 문제들도 많았고 아무리 고민해도 풀리지 않는 문제들이 정말 많았다.처음에는 '틀렸습니다'라는 문구가 나올 때마다 기분이 몹시 나빴는데, 지금은 조금 익숙해졌다. (물론 여전히 썩 유쾌하진 않다.)오랜 고민 끝에 문제를 해결했을 때 느끼는 그 감..

이 문제는 특이하게 최단경로를 구하는 문제가 아니라 K번째 최단경로를 구하는 문제이다.2번째 최단경로라는 말은 2번째로 빠른 경로를 의미한다. 최단거리를 구하는 알고리즘은 다익스트라 알고리즘으로 구현할 수 있는데 K번째 최단경로는 어떻게 구할까??우선 나는 이 문제를 다익스트라 알고리즘을 살짝 변형해서 해결하였다.다익스트라 알고리즘은 원래 선택된 노드와 이웃한 노드의 거리의 합이 저장되어 있는 값보다 작으면 값을 갱신하고 큐에 노드를 넣어줬었는데 나는 이 부분을 제거했다.그냥 갱신은 모르겠고 전부다 큐에 집어넣었다. 그러고 노드마다 방문된 횟수를 저장하고 만약 K번째로 노드가 방문되었다면 그 값을 배열에 저장하였다.어차피 우선순위 큐를 사용하기 때문에 작은게 우선으로 뽑히고 만약 노드가 K번 방문되었다면..

이 문제는 시작점에서 다른 정점까지의 최단 경로값을 구하는 문제이다. 다익스트라 알고리즘을 사용한다.이 문제에서 주의 깊게 보아야 하는 점은 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수 있다는 것이다.이미 최적의 값으로 갱신된 노드는 다시 방문하지 않게 만들어줘야 한다.(시간초과 방지) if (dist[cur] 이렇게 해도 되고 아니면 visited배열을 이용해서 방문된 노드를 저장해 주면 된다. 이미 방문한 노드는 다시 방문하지 않는다!#include #include #include #define INF 987654321;using namespace std;vector>v[1001];priority_queue>pq;int arr[1001];int main(void){ int N, M = 0;..

만약 누군가 진실을 알고 있다면 거짓말을 하면 안 된다. 근데 이 문제에서 조금 헷갈렸던 점은 파티를 여는 순서가 있는지 아니면 동시에 파티를 여는지가 좀 헷갈렸다.문제를 해결해 보니 동시에 파티를 여는 문제였는데 만약 동시에 파티를 열게 되면 사람이 몸을 쪼개서 가야 하나?? 1/2등분에서 파티에 참석? 약간 이런 부분 때문에 문제를 이해하기 쉽지 않았다. 문제를 해결하는 방법은각 파티에 참여하는 사람들이 주어지는데 각 파티의 첫 번째 사람을 파티장으로 임명해서 문제를 해결한다. 위 예제로 보면첫 번째 파티에서 파티장은 1번이고 1번과 2번을 Union한다.두 번째 파티에서 파티장은 3번이고 3번과 3번을 Union한다세 번째 파티에서 파티장은 2번이고 2번과 3번을 Union하고 2번과 4번을 Uni..

이 문제는 MST를 구하는 문제이다.문제를 해결할 수 있는 방법은 2가지가 있다.프림의 알고리즘을 사용하던지 크루스칼의 알고리즘을 사용하면 된다.일반적으로 프림의 알고리즘이 크루스칼의 알고리즘보다 구현하기 쉬워서 프림의 알고리즘을 많이 사용한다. *프림의 알고리즘*은 한 노드를 딱 정해서 그 노드에서부터 이웃한 노드를 우선순위 큐에 넣고 가장 가까운 노드로 나아가는 방법이다.(나아간 후에는 그 나아간 노드에 있는 이웃한 노드 또한 우선순위 큐에 넣어주는 작업을 수행해야 함. visited배열을 사용해서 이미 방문된 노드는 다시 방문하지 않음.) *크루스칼의 알고리즘*은 간선을 우선순위 큐에 모두 넣어놓고 짧은 간선부터 하나씩 빼서 MST를 구성하는데 만약 사이클이 발생하면 그 간선은 사용하지 않고 넘어간..

대표적인 Union&&Find 문제이다. 0이 들어오면 a의 집합과 b의 집합을 Union 해준다.1이 들어오면 a와 b가 같은 집합에 속해있는지 확인한다.if (num == 0){ Union(a, b);}else if (num == 1){ if (Find(a) == Find(b)) { cout  Union은 어떻게 하느냐?일단 Find(a), Find(b)를 해서 a와 b의 대표노드들을 찾는다.그리고 대표노드 하나를 선택해서 다른 대표노드의 자식으로 넣는다.a가 b의 자식이 되거나 b가 a의 자식이 되거나.나는 index가 큰 놈을 자식으로 만들고 index가 작은놈을 부모로 만들었다. Find는 어떻게 하느냐?우선 자신의 부모노드를 저장하기 위해 1차원 배열을 선언한다.이 배열을 부모노드의 값을 저..

이 문제의 목적은 목적지까지 주유소를 최대한 적게 방문하는 것이다. 어떻게 하면 최대한 적게 방문하고 목적지까지 갈 수 있을까??사고를 좀 거꾸로 할 필요가 있다. 우선 트럭을 타고 길을 지나간다.가는 길에 주유소가 있었다면 주유소에 대한 정보를 저장한다.길을 가다 보면 연료가 바닥난다. 연료가 바닥이 났을 때 이전에 저장했던 주유소 중 가장 연료가 많이 저장된 곳에서 주유를 한다.(주유를 하고 난 후 pop)이러한 방법으로 목적지까지 도달하는 것이 가능하다면 주유소에서 멈추는 횟수를 출력하고그렇지 않다면 -1을 출력한다. 즉 방문하면서 주유하는 것이 아닌 연료가 바닥으로 떨어졌을 때 이전 주유소에 대한 정보를 가지고 주유하는 것이 핵심이다. #include #include #include using n..

도화지에 선을 긋고 그은 선의 총길이를 출력하는 문제이다. 여러 번 그은 곳과 한번 그은 곳은 구분이 불가능하다. 선을 그을 때마다 배열에 저장하면서 문제를 해결할 수 있을까??답은 불가능하다.우선 선을 그을 때마다 배열에 일일이 저장하면(배열의 값을 1로 바꿔) 중복해서 그려지는 부분이 생긴다. 시간초과가 발생할 것. 그러면 시작점과 끝점에서 안 그려진 부분(0인지 1인지 확인)부터 그려진 부분까지 그리면 되는 거 아닌가?? 중간에 이미 그려졌으면 break; 시간초과가 안 발생할 것 같은데?이것도 불가능하다. 배열에 20억개 이상 저장할 수 없다. 그러면 어떻게 해결해야 하는가?앞에서부터 선을 긋는다. 그러려면 입력값을 일단 정렬해야 한다.앞에서부터 선을 긋고 마지막에 그은 점을 저장해 놓는다.다음에..

연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 문제이다.연속된 부분 구간의 합이 M으로 나누어 떨어진다??문제를 어떻게 해결하여야 하는 거지?? 이 문제를 해결하기 위해서는 아이디어가 필요하다. 누적합을 하면서 나머지를 구하는 것이다.나머지가 1나머지가 0나머지가 0나머지가 1나머지가 0 나머지가 1인 경우를 유심히 관찰해 보자.1만 있을 때와 1 2 3 1일 때 나머지가 1이다.이 둘을 빼게 된다면?? 2 3 1이 남는다 2 3 1은 3으로 나누어 떨어진다.이 아이디어를 이용해서 문제를 해결한다. 1. 나머지를 저장하는 배열을 만든다.2. 배열에는 경우의 수가 저장된다.3. 배열에 저장된 값을 가지고 2개씩 조합한다. 예를 들어 result[1]에 2가 들어 있다. 그러면 나머지..

너비우선탐색 문제이다. 생각보다 고려해야 할 경우의 수가 많아서 헷갈렸다. 1. 지훈이는 이미 이동한 경로로 다시 이동하지 못한다.2. 지훈이는 이전에 불이 난 장소로는 이동하지 못한다.3. 이미 불이 난 곳은 다시 탐색하지 않는다.4. 사람이 모서리에 도착하면 탈출할 수 있다고 판단함.5. 사람이 출발하기 전에 출발하려는 장소가 불이 났는지 안 났는지 판단해야 함. 사람이 출발하기 전에 출발하려는 장소가 불이 났는지 안 났는지 판단해야하는 이유.이렇게 주어졌을 때사람이 먼저 이동 한 후불이 이동을 하게 되면 불과 사람이 겹친다.그렇기 때문에 사람은 출발하기 전 자신의 위치에 불이 났는지 확인하는 작업이 필요하다. #include #include ;using namespace std;char arr[10..