앱등개발자IOS

먼저 가장 중요한 아이디어는 DP를 활용해서 장마가 시작한 위치 dp[s] += 1을 해주고, 장마가 끝난 위치 e에 대하여 dp[e + 1] -= 1을 해주고, 마지막에 0번 인덱스부터 맨 끝 인덱스까지 dp[i+1] += dp[i];를 실행해주면 어느 지역에 장마가 몇 번 왔는지 다 계산할 수 있다. 이를 3일 씩 끊어서 land라는 전체 data 배열에 저장해주는데, 똑같은 논리로 python으로 풀이하였을 때는 총 5개의 testcase에서 Timeout 판정이 났다. 같은 논리로 C언어로 풀이했을 때는 모든 testcase에 대하여 정상적으로 통과되었다.

C알고리즘 2023. 9. 29. 19:44

C언어로 풀이할 때 숫자의 범위를 신경써줘야하는 게 Point인 문제였다. 각 도시 리터당 가격이 10억 이하의 자연수이고, 맨 왼쪽 도시에서 맨 오른쪽 도시까지 거리의 합이 10억 이하인데, 이들을 더해나가는 과정의 결괏값을 담을 result 만 long long(8Byte)로 처리해주면 된다고 생각하면 오류를 일으키게 된다. 23째 줄을 보면, long long 자료형의 result에 int형 변수인 now_min과 edges[i]를 곱해서 더해준다. 만약 두 int형 변수를 타입 캐스팅 없이 곱하게 되었을 때, int형의 표현 가능 범위를 넘어갈 수 있고, 이 때 값에 왜곡이 일어날 것이다. 조심할 것이, (long long) (now_min * edges[i]) 와 같이 해도, 값이 달라질 것이다..

C알고리즘 2023. 9. 29. 18:23

python으로 풀이할 때와는 다르게, C는 동적 할당하여 필요한 만큼만 메모리를 사용하고, 배열에서 최솟값을 찾는 과정, 2개의 수 중 최솟값을 찾는 과정 모두 함수를 구현해주어야해서 시간이 좀 더 걸렸다... 하지만 그만큼 Deep하게 메모리를 관리하는 것 같은 즐거움이 느껴졌다.

C알고리즘 2023. 9. 29. 14:30

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

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

python C언어 확실히 C언어는 정렬하는데도 시간이 더 걸리네요...

C알고리즘 2023. 9. 29. 12:46

c언어 python

카테고리 없음 2023. 9. 29. 01:53

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

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