차트식 코딩

이전 알고리즘 글 '누적 합'을 먼저 보고 오시는 걸 권장합니다.누적 합 배열(Prefix Sum Matrix)주어진 2차원 배열이 있을 때, 각 위치 (i,j)에 (1,1)부터 (i,j)까지의 직사각형 영역에 있는 모든 원소들의 합을 저장한 배열(행렬).원본 배열을 A, 누적 합 배열을 Z라고 할 때, Z[i][j]는이고,이는 P[i][j]는 원본 행렬의 좌상단 모서리(1,1)부터 현재 위치(i,j)까지 형성되는 직사각형 영역 내의 모든 원소들의 합. 크기가 N * M인 2차원 배열의 누적 합 배열을 구하는 과정의 경우 시간 복잡도는 O(NM).누적 합을 통해 배열의 특정 구간[L, R]의 합을 구할 때 시간 복잡도는 O(1).→ Q번의 질의가 있는 경우, O(N)+O(Q)이므로 시간 복잡도는 O(NM..

누적 합(Prefix Sum)배열의 처음부터 정해진 위치까지의 합.누적 합을 미리 계산하면 배열의 특정한 범위의 합계를 바로 구할 수 있다. 길이가 N인 배열의 누적 합을 구하는 과정의 경우 시간 복잡도는 O(N).누적 합을 통해 배열의 특정 구간[L, R]의 합을 구할 때 시간 복잡도는 O(1).→ Q번의 질의가 있는 경우, O(N)+O(Q)이므로 시간 복잡도는 O(N+Q). 만약 누적 합을 사용하지 않는 경우, 특정 구간의 합을 구하는 시간 복잡도는 O(N)이며, 특히 Q번의 질의가 있는 경우 시간 복잡도는 O(NQ).과정원본 배열 A가 아래의 표와 같다고 해보자.14235 A의 누적 합 배열 P는P[0] = A[0] = 1P[1] = A[0] + A[1] = 1 + 4 = 5P[2] = A[0] +..

깊이 우선 탐색(Depth-First Search, DFS)그래프 순회 방식 중 하나.시작 노드에서부터 출발하여 출발한 그래프의 간선을 따라 이동해가며 도달 가능한 모든 노드를 처리.단일한 경로를 따라 순회. 그 후 이전 노드로 돌아가 그래프의 다른 부분을 탐색.해를 구할 수 있지만, 그렇게 구해진 해가 최적해라는 보장은 없음. 시간복잡도의 경우 O(n+m)여기서 n은 노드의 개수, m은 간선의 개수. 과정시작 노드에서부터 출발하여 출발한 그래프의 간선을 따라 이동해가며 도달 가능한 모든 노드를 처리.단일한 경로를 따라 순회. 그 후 이전 노드로 돌아가 그래프의 다른 부분을 탐색. 1번 노드에서 시작한다고 해보자. 1번 노드에서 2번 노드로 이동한다. 2번 노드에서 3번 노드로 이동한다. 3번 노드에서 ..

벨만-포드 알고리즘 (Bellman-Ford Algorithm)시작 노드에서부터 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘.다익스트라와 다르기 가중치가 음수인 경우에도 사용이 가능하지만, 최적해를 보장하지는 않는다.=> 벨만-포드 알고리즘을 이용해 가중치가 음수인 사이클을 찾을 수 있다. 시간복잡도의 경우 O(nm)여기서 n은 노드의 개수, m은 간선의 개수. 과정시작 노드에서 다른 모든 노드까지의 길이를 모두 추적.거리의 초기값은 시작노드를 0, 나머지는 INF로 설정하고, 이 값을 계속 줄여나가는 과정을 통해 더 줄일 수 있는 값이 없을 때까지 반복.위와 같은 그래프가 있다고 가정하자. 가장 먼저 파란색 간선을 통해 INF인 값을 줄인다. 3에서 4로 가는 간선을 먼저 보자.3+1  2에서 ..

선형 검색(Linear Search) 배열에서 검색하는 방법 중 가장 기본적인 알고리즘입니다. 직선(선형)으로 늘어진 배열에서 검색하는 경우 원하는 원소를 찾을 때까지 맨 앞에서부터 순서대로 검색하는 알고리즘입니다. 2 4 1 6 7 3 5 가령 위와 같은 배열이 있다고 가정해봅시다. 우리는 원소 3을 찾고 싶습니다. 그렇다면 맨 앞 배열의 0번자리부터 스캔을 시작하고, 6번째 스캔에서 3을 찾아내게 됩니다. 원하는 3을 찾았으니 검색은 성공하고 알고리즘은 종료되겠죠. 그러나 8을 찾는다고 가정해보겠습니다. 앞에서부터 스캔을 하다가 6번자리까지 지나도 보이지 않으니 배열의 맨 끝 원소를 지나가게 되고, 알고리즘은 검색이 실패한 채 종료됩니다. 위의 설명과 같이 선형 검색이 종료되는 조건은 2가지가 있습니..

알고리즘과 관련된 컴퓨팅적 사고 컴퓨팅적 사고는 컴퓨터 프로그래머 뿐만 아니라 누구나 배워서 활용할 수 있는 보편적인 사고이자 기술을 의미한다. 자료 수집 정보를 수집하는 과정 자료 분석 데이터의 의미를 만들고 분석하며 결론을 도출 자료 표현 그래프, 차트, 단어, 이미지 등으로 적절하게 데이터를 구성 및 묘사 문제 분해 크고 복잡한 문제를 작고 단순하게 분할 추상화 핵심적인 부분만 정의 알고리즘 문제를 해결하거나 결과를 달성하기 위한 순서 자동화 컴퓨터 및 기계를 통해 반복적인 작업 수행 시뮬레이션 프로세스의 모델링 표현, 모델을 이용해 실험 수행 병렬화 공통의 목표에 도달하는 작업을 수행하기 위한 자원 구성 그 외에도 캐싱, 백트래킹 등 여러 컴퓨팅적 사고 개념이 있다. (자넷 윙, COMMUNICA..

알고리즘이란? 문제를 해결하기 위한 절차를 의미한다. 같은 문제를 해결하는 다른 알고리즘과 비교해 문제 해결속도가 빠를수록 좋은 알고리즘이다. 알고리즘의 조건 5가지 입력 외부에서 제공되는 자료가 0개 이상 존재해야 한다. 출력 모든 입력에 대해 모두 같은 출력이 나와서는 안된다. 가령 어떤 알고리즘에 대해 입력할 수 있는 수가 1부터 100까지라 가정하자. 1부터 100까지 각각 입력했을 때 모든 출력이 같아서는 안된다는 것이다. 즉, 적어도 두 가지 이상의 서로 다른 출력값이 나와야 한다. 명확성 수행 과정이 명확해야 한다. 비유하기에 무리가 있을 수 있지만, 쉬운 이해를 위해 일상 생활에 비유해 보자. 거실에 서 있는 당신이 닫힌 안방 안의 의자에 앉기 위한 방법을 컴퓨터에게 설명해 보자. 만약 '..