로그 남기기

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

이전 포스팅인 DFS/BFS와 최단 경로에서 다룬 내용도 그래프 알고리즘의 한 유형이다. 문제를 접했을 때 서로 다른 개체가 연결되어 있다는 이야기를 들으면 가장 먼저 그래프 알고리즘을 떠올려야 한다. 그래프 알고리즘에 앞서 트리 자료구조에 대해 간략히 짚고 넘어가겠다. 트리는 그래프의 일종으로 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 그래프 트리 방향성 방향 그래프 혹은 무방향 그래프 방향 그래프 순환성 순환 및 비순환 비순환 루트 노드 존재하지 않음 존재함 노드간 관계성 부모와 자식 관계 없음 부모와 자식 관게 모델 종류 네트워크 모델 계층 모델 Graph Algorithm 그래프는 주로 두 가지 방식으로 구현한다. 인접 행렬 (Adjacency Matrix) : 2차원 배열 사용 메모리 공..

Shortest Path Algorithm 길 찾기 문제라고도 불리는 최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. 한 지점에서 다른 지점까지의 최단 경로를 구하는 다익스트라 알고리즘과 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구하는 플로이드 와샬 알고리즘에 대해 알아보자. Dijkstra Algorithm 다익스트라 알고리즘은 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해준다. 음의 간선이 없을 때 정상적으로 동작하며, 매 순간 가장 비용이 적은 노드를 선택하는 과정을 반복하기 때문에 그리디 알고리즘으로 분류된다. 원리는 다음과 같다. 출발 노드 설정 최단 거리 테이블 초기화 방문하지 않은 노드 중 최단 거리가 가장 짧은 노드 선택 해당 노드를 ..