룰루랄라 알고리즘

https://www.acmicpc.net/problem/20057 20057번: 마법사 상어와 토네이도 마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 www.acmicpc.net 문제를 이해하는데도 시간이 꽤 걸렸던 문제. 풀이 순서: 토네이도의 위치 획득 -> 각 토네이도에 의해 이동한 모래의 양을 구해 범위 밖이면 결과 값 result에 추가 1. 좌표 설정 왼쪽 방향으로 이동할 때 모래가 흩어지는 좌표를 구할 수 있는 left 리스트 구성 -> 여기서 좌표는 모래바람이 이동한 후 인 y 위치를 기준으로 작성 -> 마지막 리스트의 원소는..

문제 자체가 설명이 불친절하다. 문제를 해석하자면 빈자리에 누울 때 벽부터 짐이 있는 X 까지가 한 가지 경우의 수이다. 즉 ..X.. 라면 두 가지 경우의 수가 있다는 뜻이다. 변수 switch는 이 경우의 수를 카운트할 때 까다로운 부분을 해소해준다. switch가 0일 때만 빈자리 .를 카운트해준다. count가 2라면 경우의 수를 +1 해주고 switch를 1로 변경해 X를 만날 때까지 switch를 변경하지 않으면서 빈자리 .를 카운트하지 않는다. 만약 X를 만나게 된다면 switch를 0으로 변경해 다시 빈자리 .를 카운트할 수 있게 해 준다.

진짜 여러 가지로 삽질한 문제 처음 문제를 본 후 주사위에 대한 조건을 세웠다. #3개의 면이 보이는 주사위 : 맨 위 꼭짓점 4개 #2개의 면이 보이는 주사위 : 각 모서리 (n-1)*4 + (n-2)*4 개 #1개의 면이 보이는 주사위 : 평면 n*n-(4n-4) + (n*n-(3n-2))*4 개 여기서 나는 조합을 이용해 풀었다. 3개의 면이 보이는 주사위는 아래와 같이 6개 중 3개의 조합을 구한 후 주사위에서 서로 반대편 면이 함께 있는 조합은 삭제시킨 후 합을 구해서 sum_3에 append하는 방식이다. 위와 같은 풀이를 했을 때 생각지도 못한 문제가 발생했는데, 위와 같이 코드를 작성하였을 때 결과값이 아래와 같이 나타났다. 분명 1과 6이 함께 있는 tuple은 remove 되어야 하는데..

투 포인터의 약간의 변형 문제 두개의 포인터가 양 끝쪽이 아니라 모두 왼쪽에서 부터 시작하는 문제이다. 생각보다 인덱스의 범위, left right의 인덱스 등등 헷갈리는게 많았다. 보기엔 쉬워보이지만 직접 작성해보니 생각보다 어려운 문제. 처음 작성한 코드는 아래와 같은데 위 처럼 매 순간 마다 모든 구간을 sum한다면 투 포인터의 의미가 없어져 버린다는 것을 인지하지 못했었다.

힙을 이용한 prim 알고리즘으로 풀었다. 1. heap에 시작 정점 1과 가중치 0 [[0,1]] 삽입 2. heap에서 정점과 가중치를 꺼냄 3. 꺼낸 정점이 방문하지 않은 정점이라면 결과에 가중치를 더함 4. 그 정점에서 다른 정점으로 향하는 정보 i를 힙에 삽입 5. 위의 과정을 반복하다가 count가 정점의 수 V가 되면 종료

Spanning Tree 특징 모든 정점들이 연결 되어 있어야 하고 사이클을 포함해서는 안된다. V개의 정점을 (V-1)개의 간선으로 연결되어야 한다. MST(Minimum Spanning Tree) Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리 1. Kruskal 알고리즘 2. Prim 알고리즘 시작 정점에서 부터 출발하여 스패닝 트리 집합을 단계적으로 확장 Prim 알고리즘의 동작 과정 시작 정점을 힙에 저장 방문하지 않은 정점중에서 가중치가 가장 낮은 정점을 선택 위 과정을 트리가 (V-1)개의 간선을 가질 때 까지 반복 백준 1922

코드는 알고리즘 - 위상 정렬에 있음 기본적인 위상 정렬 문제 위상 정렬을 사용하지 않고 스택을 이용해 풀었으나 당연히 시간초과로 실패 처음 위상 정렬이란 알고리즘을 알고 공부하게된 계기가 되었음

입출력에 대한 이해가 어려웠던 문제 테스트케이스를 입력으로 주지 않는 문제 파이썬의 try except를 사용해 풀었다. try는 에러가 일어나지 않을 때 작동하는 코드, except는 에러가 발생 했을 때 작동하는 코드이다. N의 최대 개수가 1000000이므로 정렬 후 투 포인터로 가장 왼쪽 값과 오른쪽 값을 더해 target X와 일치 할 때 결과를 result에 저장하고 함수를 종료한다.

처음 for문을 두번 돌려서 시간초과가 난 문제 N의 최댓값이 100,000이라서 for문을 한번만 쓰고 해결해야 된다. 이 문제의 핵심 키는 20번쨰 코드이다. 입력받은 점수를 오름차순 정렬했기 때문에 중요한 것은 2번째 인덱스인 면접 점수다. 처음 max_score로 서류심사 점수에서 가장 최고점을 획득한 사람의 면접 점수를 넣어준다. 그 이유는 서류점수의 오름차순 정렬이므로 뒤에 나오는 사람은 이미 서류점수에서 뒤처지는 사람이기 때문에 max_score보다 낮은 점수를 받은 사람은 무조건 탈락이기 때문이다. 여기서 이 max_score보다 높은 점수 즉 숫자가 적은사람이 나타난다면 결과값 result를 +1 해주고 max_score를 교체한다

개수를 구하는 코드는 LCS1 문제에 있으므로 그 부분은 생략한다. 다른 사람의 풀이를 보고 내 방식 대로 풀었다. 다른 사람의 풀이를 보지 않았다면 못 풀었을 것 같다. 역 추적으로 구하는 방식인데 아래 그림처럼 처음으로 숫자가 +1 되었을 때를 기준으로 문자열을 저장했다. 처음으로 +1이 되었다는것을 판별 할 때는 아래와 같은 규칙이 있다. 1. 자기 자신의 위나 왼쪽 중에 같은 숫자가 있다면 인덱스를 그 위치로 바꾼다. 2. 자기 자신의 위나 왼쪽 중에 더이상 같은 숫자가 없다면 대각선에 위치한 인덱스로 위치를 바꾼다. 3. 대각선으로 위치를 바꾸기 직전의 인덱스가 처음으로 +1이 된 위치다. DP의 값이 0 이되면 추적을 멈춘다.