앱등개발자IOS

백트래킹을 진행하며, 각 색깔의 점 하나씩 포함하여 총 k개를 모두 골랐을 때, 최소 사물 넓이를 result에 갱신하여 저장하였다. 25~26번과 같이 백트래킹을 진행하는 도중에, 넓이가 result를 넘어가버리면 백트래킹을 더 진행할 필요가 없으므로, 넓이가 result 미만인 경우에만 다음 단계로 Back Tracking을 진행한다. 이 부분을 구현하지 않으면 시간초과 판정을 받는다.

Python알고리즘 2023. 10. 2. 16:19

강의가 끝나는 시간을 기준으로 오름차순 배열, (끝나는 시간이 같다면 시작하는 시간을 기준으로 오름차순 정렬 )

Python알고리즘 2023. 10. 2. 15:24

문제를 읽으며, " 아 이 경우들을 모두 찾기 위해서는 모든 경우를 다 확인해봐야한다!" 라는 생각이 들어야한다. 그런 생각이 들었다면?? => Back Tracking (DFS)로 구현하면 된다!

Python알고리즘 2023. 10. 2. 15:11

문제를 풀수록 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