앱등개발자IOS

문제를 풀수록 HSAT 문제들이 알차게 구성되어있다는 것을 느꼈다.. 5만개의 숫자가 들어오고, 쿼리는 20만개까지 들어올 수 있으므로, 편하게 로직을 짜면 바로 시간초과가 날 것 같았다. 쿼리에서 어떤 숫자가 주어지면, 해당 숫자가 data 배열에서 몇 번째에 있는지 바로바로 알아낼 수 있어야한다. data.index(찾아야 할 수) 와 같은 연산을 매 번 반복하면 시간초과가 나게 된다. 따라서 dictionary 형태로 구성하여 key는 우리가 찾는 수, value는 (그 숫자 앞에 있는 숫자의 갯수, 그 숫자 뒤에 있는 숫자 갯수) 로 구성하여 쿼리에서 곱셈만 해서 print하면 되도록 HASH를 미리 구성해두는 것이 핵심이다.

Python알고리즘 2023. 10. 2. 14:49

3차원 DP를 사용해야하는 문제였다. data[i-1][n][m]이 뜻하는 것은, i-1번째 작업을 하는 라인들에서, n번 라인에서 일을 하고, m번 라인으로 이동해 다음 작업을 하려고 할 때 드는 비용 ( m번 라인으로 이동하는 비용까지 포함) 이렇게 하나의 2차원 배열 ( data[i] ) 하나를 완성하면, 그 윗칸 ( data[i + 1] )을 이어서 완성시키면 되는데, data[i + 1][n][n] ( n은 0 ~ 라인 수 )에 data[i][][n] ( 배열에서 세로 부분 ) 중 최솟값을 구해 더해주고 시작한다.

Python알고리즘 2023. 10. 2. 01:30

while 문을 사용하면서, 규칙 구간을 넘겨야 할 때는 r += 1, 실제 운행 구간을 넘겨야 할 때는 d += 1을 해주며 over라는 변수에 가장 위반 폭이 클 때를 저장해두는 것이 포인트이다!

Python알고리즘 2023. 10. 1. 19:32

비트연산으로 풀이하라고 준 문제인 듯 싶다. Level2 문제가 맞나 싶었다.... digi에 먼저 각 숫자 별 전구로 나타낼 때 켜져야하는 위치를 2진수 형태로 변환한 수의 10진수 형태를 저장하였다. ( 1의 경우 2, 5 번째만 1이므로 0010010 0> 18이 됨) dif(a, b) 함수는 두 숫자의 대응하는 각 자리를 체크하며, 양 숫자를 나타내는 전구 위치를 digit에서 가져와 XOR(^)연산 하였고, 그 결과로 나온 값을 count_one()함수에 보내 1의 갯수를 세주었다.. 이렇게 총 5자리에 대해 체크해주면 된다.

Python알고리즘 2023. 10. 1. 19:04

Python알고리즘 2023. 9. 30. 14:46

코딩테스트 문제를 풀 때 문해력도 정말 중요하다는 것을 매 코딩테스트마다 깨닫는다... ㅎ 이 문제는 테스트케이스도 하나 밖에 주어지지 않고, 문제와 자료의 형태를 파악하는데 시간이 꽤 걸렸다. 하지만 문제에는 필요한 정보들이 다 담겨있었다...! 암튼 생각한 것 만큼 오래걸리지는 않고 풀이하였다. 기본적인 DP문제인데, 자료의 형태 파악에 어려움을 가미해놓은 문제. 그냥 위에서 아래로 내려가며 Memoization을 수행하면 되는데, data[i][j]가 의미하는 바는, "i번째 작업작의 j번째 라인에서 조립을 완성한다고 가정했을 때, 가장 빠른 시각"이다.

Python알고리즘 2023. 9. 29. 13:53

Python알고리즘 2023. 9. 29. 01:46

Python알고리즘 2023. 9. 28. 23:07