룰루랄라 알고리즘

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 위치를 기준으로 작성 -> 마지막 리스트의 원소는..

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

입출력에 대한 이해가 어려웠던 문제 테스트케이스를 입력으로 주지 않는 문제 파이썬의 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 이되면 추적을 멈춘다.

ACAYKP CAPCAK 앞의 문자열의 sub sequence를 X, 뒤의 문자열의 sub sequence를 Y라고 했을 때 문자를 하나씩 늘려가면서 비교해보자 X: A Y: C 두 문자열로 만들 수 있는 LCS의 길이는 0이다. X: A Y: CA 두 문자열로 만들 수 있는 LCS의 길이는 1이다. X: A Y: CAP 두 문자열로 만들 수 있는 LCS의 길이는 1이다. X: A Y: CAPC 두 문자열로 만들 수 있는 LCS의 길이는 1이다. 위와 같이 Y가 끝까지 CAPCAK까지 구하게 된다면 X를 하나씩 늘려주면 된다. X: AC Y: C 두 문자열로 만들 수 있는 LCS의 길이는 1이다. X: AC Y: CA 두 문자열로 만들 수 있는 LCS의 길이는 1이다. 표를 만들고 채우기 위해 값이 증가..

삼성 sw 역량테스트 기출문제 문제를 이해 하는게 푸는 것 보다 더 어려웠다 하라는 대로만 충실히 하면 풀리는 문제인듯. 43~48줄인 후진하는 코드에서 시간이 좀 걸렸는데 다른 분의 풀이를 보니까 그냥 nx = x - dx[d] ny = y - dy[d] 이런 식으로 했는데 내가 봤을 때 직관적이지도 않고 이해가 되지않아서 좀 지저분하지만 내 방식대로 풀었다. dx,dy 리스트의 방향 순서를 문제에서 준 대로 바꿔야 하는게 핵심인 듯 하다. 리스트의 인덱스를 +1 했을 때 보고 있던 방향의 왼쪽을 향하게 하는 순서대로 짜야지 문제를 풀 수 있다.

리스트를 잘라서 수열이 일치하는지 여부를 확인하는게 주요했던 문제 처음에는 아래 코드 처럼 백트래킹을 사용하지 않고 while문을 통해 나름대로 규칙을 세워서 시도 했었는데 백트래킹을 쓰지 않고는 풀 수 없는 문제인걸 깨닫고 다시 백트래킹 코드로 고쳤다.

처음에 이진 탐색으로 stack에 있는 값을 찾지 않고 아래와 같이 in을 써서 탐색 했다가 시간초과에 걸렸다. N,M이 각각 500,000 이하의 큰 수 임을 생각하지 못했다. 값이 큰 리스트를 탐색 할 때는 이진 탐색을 생각해보자

여태까지 중에 백준에서 가장많이 틀리고 다시 시도한 문제 내가 생각한 방식에 대한 믿음을 가지고 풀어야 풀리는 듯. 증명하라고 하면 절대 못할 것 같다. 풀이방식 1. 처음에 플러그가 다 채워질 때까지 장비를 꽂는다. 2. 이미 꽂혀있는 장비라면 건너뛴다. 3. 플러그가 다 꽂혀있고 이미 꽂혀있지 않은 장비라면 3-1. 후에 다시 쓰지 않는 장비를 빼고 그 자리에 꽂는다. 3-2. 다시 쓰지 않는 장비가 없다면 가장 나중에 쓰는 장비부터 빼고 그 자리에 꽂는다. 처음에는 나중에 쓰는 장비의 빈도수를 계산해서 가장 적게 쓰는 장비부터 빼면 된다고 생각했는데 이건 틀렸다. 그 이후에도 자잘하게 놓치는 부분이랑 인덱스 계산 오류 등등 실수가 많았다. 매우 까다로운 문제.