로그 남기기

10994 - 별 찍기 19 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 코드 한마디 맨날 삼각형 관련 별 찍기만 하다가 이렇게 특이한 문제를 풀어보니 규칙 찾기 굉장히 힘들었다. 10994번: 별 찍기 - 19 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net

10997 - 별 찍기 22 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 코드 한마디 이전에 풀었던 문제에서 힌트를 얻어서 풀 수 있었지 처음 보는 유형이었다면 골치 아팠을 것 같다. 10997번: 별 찍기 - 22 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. www.acmicpc.net

1789 - 수들의 합 문제 서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까? 코드 한마디 입력 받은 S까지 for문 돌리는 코드가 왜 안되는지 아직도 모르겠다. 문제에서 주어진 최대 범위 4,294,967,295까지 돌렸더니 통과하길래 그냥 while문으로 작성했다. 1789번: 수들의 합 첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다. www.acmicpc.net

2033 - 반올림 문제 정수 N이 주어져 있을 때 이 수가 10보다 크면 일의 자리에서 반올림을 하고, 이 결과가 100보다 크면 다시 10의 자리에서 반올림을 하고, 또 이 수가 1000보다 크면 100의 자리에서 반올림을 하고.. (이하 생략) 이러한 연산을 한 결과를 출력하시오. 코드 한마디 처음엔 round 함수만 사용하면 풀리는 간단한 문제인 줄 알았는데 아니였다. 2033번: 반올림 정수 N이 주어져 있을 때 이 수가 10보다 크면 일의 자리에서 반올림을 하고, 이 결과가 100보다 크면 다시 10의 자리에서 반올림을 하고, 또 이 수가 1000보다 크면 100의 자리에서 반올림을 하고.. ( www.acmicpc.net

직전 포스팅에 다 작성하기엔 양이 많아 1, 2로 나눴다. 구간 합 구간 합 문제는 리스트 내 특정 구간의 모든 수를 합한 값을 구하는 문제이다. 여러 개의 쿼리로 구성되는 문제 형태로 출제되는데, 보통 다수의 구간에 대한 각각의 합을 구하도록 요구된다. 10, 20, 30, 40, 50 리스트가 있을 때 두 번째 수부터 세 번째 수까지의 합은 50, 두 번째부터 네 번째 수까지의 합은 90이다. N개의 수와 M개의 쿼리가 주어져 각각의 구간 합을 매번 구한다면 O(NM) 의 시간복잡도를 가진다. 그렇기 때문에 데이터가 많아질 경우 해결할 수 없을 것이다. 따라서 prefix sum 기법을 이요하면 된다. 접두사 합이란 리스트 맨 앞부터 특정 위치까지의 합을 구해 놓은 것을 의미한다. 이를 이용하면 시간..

이것이 취업을 위한 코딩 테스트다 책 부록에 있는 기타 알고리즘 몇 가지를 정리해봤다. 소수 판별 소수란 1보다 큰 자연수 중 1과 자기 자신을 제외한 자연수로는 나누어 떨어지지 않는 자연수를 뜻한다. 쉽게 말해 1과 자기 자신으로만 나누어지는 자연수이다. 보통 소수인지 아닌지 판별하는 함수를 작성하라고 하면 아래처럼 코드를 짤 것이다. 나도 대부분 위처럼 코드를 작성해왔는데, 백준에서 문제를 풀다보면 빈번히 시간 초과가 뜬다. 1,000,000 처럼 큰 수가 입력으로 들어오면 2부터 999,999까지 모든 수에 대한 연산이 이루어지기 때문에 상당히 비효율적인 코드이다. 따라서 약수의 특성을 이용하면 훨씬 효율적인 코드를 작성할 수 있다. 16이라는 수를 예로 들면, 1, 2, 4, 8, 16 가운데를 ..