로그 남기기

1022 - 소용돌이 예쁘게 출력하기 문제 크기가 무한인 정사각형 모눈종이가 있다. 모눈종이의 각 정사각형은 행과 열의 쌍으로 표현할 수 있다. 이 모눈종이 전체를 양의 정수의 소용돌이 모양으로 채울 것이다. 일단 숫자 1을 0행 0열에 쓴다. 그리고 나서 0행 1열에 숫자 2를 쓴다. 거기서 부터 소용돌이는 반시계 방향으로 시작된다. 다음 숫자는 다음과 같이 채우면 된다. 이 문제는 위와 같이 채운 것을 예쁘게 출력하면 된다. r1, c1, r2, c2가 입력으로 주어진다. r1, c1은 가장 왼쪽 위 칸이고, r2, c2는 가장 오른쪽 아래 칸이다. 예쁘게 출력한다는 것은 다음과 같이 출력하는 것이다. 출력은 r1행부터 r2행까지 차례대로 출력한다. 각 원소는 공백으로 구분한다. 모든 행은 같은 길이..

8979 - 올림픽 문제 올림픽은 참가에 의의가 있기에 공식적으로는 국가간 순위를 정하지 않는다. 그러나, 많은 사람들이 자신의 국가가 얼마나 잘 하는지에 관심이 많기 때문에 비공식적으로는 국가간 순위를 정하고 있다. 두 나라가 각각 얻은 금, 은, 동메달 수가 주어지면, 보통 다음 규칙을 따라 어느 나라가 더 잘했는지 결정한다. 금메달 수가 더 많은 나라 금메달 수가 같으면, 은메달 수가 더 많은 나라 금, 은메달 수가 모두 같으면, 동메달 수가 더 많은 나라 각 국가는 1부터 N 사이의 정수로 표현된다. 한 국가의 등수는 (자신보다 더 잘한 나라 수) + 1로 정의된다. 만약 두 나라가 금, 은, 동메달 수가 모두 같다면 두 나라의 등수는 같다. 예를 들어, 1번 국가가 금메달 1개, 은메달 1개를 ..

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 가운데를 ..