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..

대표적인 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차원 배열을 선언한다.이 배열을 부모노드의 값을 저..

연속된 부분 구간의 합이 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가 들어 있다. 그러면 나머지..

절댓값이 가장 작은 값을 제거하는 문제이다.만약 x가 0이 아니라면 배열에 x를 추가하고 0이라면 절댓값이 가장 작은 값을 출력하면 된다. 어떻게 절댓값이 가장 작은 값을 출력할 수 있을까??정렬을 하면 어떻게 될까?? -8 -3 -2 -1 1 2 3 4 5 6 7 이렇게 정렬이 되어있다면?-1과 1은 절댓값이 같으니 같은 우선순위이고 2와 3도 동일하다. 근데 값을 넣을 때마다 정렬을 해버리면??시간 초과.이러한 문제점 때문에 나는 우선순위 큐를 사용하였다.음수와 양수를 합쳐놓으면 원하는 대로 절댓값이 가장 작은 값을 제거하는 것은 불가능하기 때문에양수 pq와 음수 pq로 나누었다. 이렇게 양수와 음수를 나누고 top의 값을 확인해서 더 절댓값이 작은 값을 출력하면 된다.양수와 음수를 나누었기 때문에 ..

이 문제는 큐를 사용하는 문제이다.먼저 N을 4로 입력받으면 큐에 1, 2, 3, 4를 순서대로 push 해준다.큐에서 제일 앞에 있는 요소를 pop 해주고 그다음 앞에 있는 요소는 맨 뒤로 보내준다.(값을 저장한 후 pop 하고 다시 저장한 값을 push)pop을 할 때 큐가 비었는지 안 비었는지 꼭 확인을 해줘야 한다.#include #include using namespace std;queueq;int main(void){ int N = 0; cin >> N; for (int i = 1; i

오른쪽으로 가면서 제일 가까우면서 자신보다 큰 친구를 찾는 문제이다. 수열의 크기가 100만까지 주어지기 때문에 이중 for문을 이용해서 문제를 해결하려고 하면 시간초과가 발생한다.효율적으로 자신보다 큰 사람을 찾아야 한다.(어떻게 해결??) 숫자를 뒤에서부터 하나씩 stack에 넣으면서 top과 비교하는 방식을 사용하였다.7을 stack에 넣는다.2를 stack에 넣는다.5를 넣는다.stack에는 5 2 7이 들어가 있는데 여기서 우리가 주의 깊게 봐야 할 숫자는 2이다.만약 다음으로 오는 숫자가 (1||2||3||4)이면 5가 출력이 될 것이고다음으로 오는 숫자가 6이면 7이 출력이 된다.2라는 숫자는 사실상 이제 필요가 없다. 왜냐하면 5가 2보다 크기 때문에 걸려도 5에서 걸리지 2에서는 걸리지 ..

윈도우 안에서 최솟값을 찾는 슬라이딩 윈도우 문제이다.N과 L이 500만까지 들어오기 때문에 윈도우 안에서 for문을 돌려 모든 수를 확인하고 최솟값을 찾으면 시간초과가 발생한다. 윈도우 안에서 효율적으로 최솟값을 찾을 수 있어야 한다. 나는 우선순위 큐를 활용해서 최솟값을 효율적으로 찾았다. 흐름을 한번 살펴보면이런 식으로 진행이 된다.나는 우선순위 큐에 윈도우 안에 있는 값을 넣고 우선순위 큐의 top에 있는 부분을 출력하게 하였다.top을 출력할 때는 이 top의 있는 값이 윈도우 내부에 있는지 확인하기 위해서 visited[]배열을 활용하였다.start가 움직이면 visited[start]를 1로 만들어 주었고 top을 확인했는데 만약 방문된 곳이면 pop을 하고 다시 top을 확인하는 형식이다...