Algorithm

배열 메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조 인덱스를 사용하려 값에 바로 접근 가능 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어려움 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요함 배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없음 구조가 간단하므로 코딩 테스트에서 많이 사용함 리스트 값과 포인터를 묶은 노드라는 것을 포인터로 연결한 자료구조 인덱스가 없으므로 값에 접근하려면 Head 포인터부터 순서대로 접근해야 함 즉, 값에 접근하는 속도가 느림 포인터로 연결되어 있으므로 데이터를 삽입하거나 삭제하는 연산 속도가 빠름 선언할 때 크기를 별도로 지정하지 않아도 됨 즉, 리스트의 크기는 정해져 있지 않..

시간복잡도 시간복잡도: 주어진 문제를 해결하기 위한 연산 횟수 시간 복잡도 유형 빅-오메가$( \Omega(n))$: 최선일 때(best case)의 연산 횟수 빅-세타$(\theta(n))$: 보통일 때(avarge case)의 연산 횟수 빅-오$(O(n))$: 최악일 때(worst case)의 연산 횟수 연산 횟수 계산 방법 연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출 시간 복잡도 도출 기준 상수는 시간 복잡도 계산에서 제외 ex) $ 3N $ → $ N $ 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 됨 ex) $ N^2 + 10N $ → $ N^2 $ 디버깅 디버깅(debugging): 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 ..

문제가 점점 어려워진다. 별 3개가 되는 순간부터 박대가리인 나는 너무 힘들다. 앞으로는 모르는 문제에 대해 이해한 대로 풀이를 쓰는 것 보단 해결한 문제에 대해서 풀이를 쓰려고 한다. 모르는 문제를 붙잡고 있어봤자 제대로 이해도 못하면서 풀이를 쓰는 것이 무슨 의미가 있을까 싶다. 아는 것부터 확실하게 체화해야 겠다. 4주차 | 문제 1. 체크카드 문제 체크 카드를 사용할 때, 가장 중요한 것은 계좌의 남아있는 잔액에 따라서 결제가 잔액이 부족한 경우가 생기기도 한다는 점이다. 구름이는 올바른 소비 습관을 만들기 위해서 지난달 구름이가 카드를 통해서 얼마를 입금하고 결제하였는지 확인하려고 한다. 구름이가 쓰는 체크 카드는 deposit, pay, reservation의 세 가지 기능을 가지고 있다. d..

3주차 | 문제 4. 순환하는 수로 문제 구름이는 도시의 물을 관리하는 관리자이다. 현재 도시에는 물을 잠시 보관하는 물탱크와 물탱크끼리 연결하는 수로가 아래의 조건으로 설치되어 있다. N개의 물탱크와 N개의 수로가 있다. 물탱크는 1번부터 N번까지 있다. 수로가 연결된 물탱크는 양 쪽으로 물이 흐른다. 서로 다른 두 물탱크를 잇는 수로는 최대 하나이다. 물탱크에서 연결된 물탱크는 항상 다른 물탱크이다. 도시의 물은 흐르지 않으면 녹조류가 생기기 때문에, 항상 물이 순환하도록 유지하는 것이 중요하다. 하지만, 구름이는 순환하는 물이 항상 모든 물탱크를 지나지 않는다는 점을 확인했다. 구름이는 현재 상태의 수로를 확인하고, 순환하는 수로를 찾기로 한다. 이때 순환하는 수로란, 물탱크의 물이 아래의 조건을 ..

3주차 | 문제 3. 구름이의 여행 문제 구름이가 사는 구름 나라는 N개의 섬으로 이루어져 있습니다. 각 섬에는 1부터 N까지의 번호가 붙어 있고, 구름 나라는 사람들이 섬과 섬 사이를 편하게 이동할 수 있도록 다리를 M개 설치했습니다. 설치된 다리들은 아래의 특징들을 만족합니다. 모든 다리는 양방향으로 이동할 수 있습니다. 서로 다른 두 섬을 잇는 다리는 최대 하나입니다. 다리가 잇는 두 섬은 항상 다른 섬입니다. 구름이는 1번 섬에서 출발해서 N번 섬으로 가려고 하는데, 통과하는 다리의 개수가 K개 이하가 되길 원합니다. 구름이를 도와 1번 섬에서 N번 섬까지 K개 이하의 다리만을 이용해 도착할 수 있는지를 구해봅시다. 예시 첫 번째 예시를 그래프로 나타내보면 아래 그림과 같습니다. 다리의 배치가 위..

3주차 | 문제 2. 폴더폰 자판 문제 10년 전, 구름이가 처음으로 구매했던 휴대폰은 폴더 폰이다. 폴더 폰의 자판은 최근의 휴대폰의 입력 방식과는 차이가 있다. 폴더 폰의 자판 형식은 아래와 같다. 9개의 입력 버튼으로 이루어져 있으며, 각 버튼의 첫 번째 숫자로 버튼을 부를 수 있다. 한 번 버튼을 누르면 숫자가 입력이 되고, 여러 번 누르면 자판에 보이는 문자들로 순서대로 바뀐다. 예를 들면 [버튼 5]를 한 번 누르면 5가 입력이 되지만, [버튼 5]를 세 번 누르면 k가 입력된다. 또 [버튼 5]를 5번 이상 누르게 되면 다시 처음 숫자가 입력된다. [버튼 7] 이나 [버튼 1]은 6번 이상일 때 동일하게 된다. 10년 전 구름이가 구매한 폴더 폰을 오랜만에 꺼내서 작동을 했더니, 휴대폰이 고..