개발저장소

학습 Point시간복잡도점근 표기법 코딩테스트에서 코드를 평가하는 방식은 크게 두 가지이다. 내가 작성한 코드의 결괏값이 테스트 케이스의 결과와 일치하는가? 문제에서 요구한 알고리즘의 성능을 만족하는가? 두 방식은 프로그래머스에서 문제를 풀 때 쉽게 볼 수 있는 '정확성'과 '효율성'이다.결과가 일치하는 것은 쉽게 확인할 수 있다. 하지만 성능을 만족하는 것은 어떻게 확인해야 할까?단순히 생각하자면 입력값을 넣고 출력값이 나올 때까지 걸리는 시간을 측정한다고 생각하면 되겠지만, 이는 컴퓨터의 성능 같은 다양한 외부 요인에 영향을 많이 받는다. 바로 여기서 시간복잡도의 개념이 등장한다. 시간복잡도란, 알고리즘의 성능을 나타내는 지표로, 입력 크기에 대한 연산 횟수의 상한을 의미한다. 연산 횟수는 전적으로 ..

문제 https://www.acmicpc.net/problem/1377 1377번: 버블 소트 첫째 줄에 N이 주어진다. N은 500,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 A[1]부터 A[N]까지 하나씩 주어진다. A에 들어있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다. www.acmicpc.net 풀이 문제의 코드 버블 정렬을 C++로 구현한 알고리즘이다. 버블 정렬에서 swap이 한 번도 일어나지 않은 루프의 위치를 알아내는 코드이다. 버블 정렬에서 swap이 일어나지 않은 루프가 존재한다는 것은 정렬이 끝났다는 뜻이다. 그러므로 루프를 알아낸 즉시 반복문을 종료하는 것이 좋다. 정렬해야 하는 배열의 크기는 최대 500,000인 자연수이고, 요소의 크기는 최대..

문제https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0www.acmicpc.net 풀이0이 아닌 정수 x를 배열에 넣는다.배열에서 절댓값이 가장 작은 값을 출력하고 제거한다.절댓값이 가장 작은 값이 여러 개라면, 그중에 가장 작은 수를 출력하고 제거한다.0이 아닌 수가 주어지면 배열에 입력하고, 0이 주어진다면 위 규칙에 맞게 수를 출력하면 된다.연산의 개수는 1보다 크고 100,000보다 작다.입력되는 정수 x는 -2^31보다 크고 2^31보다 작다.출력..

문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 풀이 N명의 사람이 0부터 N-1번까지 번호가 매겨져 있고, 이 중 일부 사람들은 친구이다. 이때, A와 B가 친구이고, B와 C가 친구이고, C와 D가 친구이고, D와 E가 친구가 되는 친구 관계 A, B, C, D, E가 존재한다면 1, 아니면 0을 출력한다. 문제 이해가 잘 안됐지만, A -> B -> C -> D -> E 처럼 일렬로 나열할 수 있는 그래프가 존재하는지 판별하는 것이 핵심이었다. 재귀가 몇 번 일어났는지 판별하기 위해서 depth를 사용해서 5번까지 일어난다면 1을 출력하도..