알고리즘

0. 개요 최근 풀었던 문제 중 다양한 알고리즘이 가능한 문제라 인상적 생각해볼 수 있는 모든 알고리즘을 고려한 후 시간 복잡도를 분석해보도록 한다. 1. 문제 곡괭이로 광물을 캐야하며, 이때 소요되는 '피로도'를 나타낸 표 곡괭이는 한 번 쓰면 "5개"의 광물

1. 복잡도(Complexity)란 각종 자료구조를 사용해 문제를 해결한 알고리즘을 개발했다고 하자. 이러한 알고리즘은 복잡도라는 지표에 의해 "효율적"인가를 판단할 수 있다. 알고리즘이 실행되는 데 필요한 리소스의 양을 설명하는 개념 시간복잡도와 공간복잡도를 활용해

연결 리스트는 데이터를 포함한 노드를 포인터로 연결하여 공간적 효율성을 극대화한 자료구조이다.각 노드는 데이터 저장 변수와 다음 노드를 가르키는 포인터로 구성연결된 두 노드는 메모리 공간 상에서 연속적으로 저장되지 않음(즉, 인접한 메모리 공간에 저장되지 않음)① 장점

: 동적으로 요소를 할당할 수 있는 동적 배열이다. 동적 할당의 핵심은 컴파일 시점에 원소의 개수를 '모른다는 것'이다. 즉 코드를 작성하는 시점에 원소의 개수를 알지 못하는 상태이다. Random Access삽입 : push_back() 삭제 : pop_back()

정점(or 노드): 데이터를 나타내는 요소간선 : 정점들을 연결하는 선으로 방향성을 가지는지 여부에 따라 방향 그래프와 무방향 그래프가 결정됨정점 : {1,2,3,4,5,6}간선 : {(1,2),(1,5),(2,3),(2,4),(2,5),(3,4),(4,5),(4,6)

① 루트 노드, 내부 노드, 리프 노드로 구성② 부모, 자식의 계층 구조를 가진다.5번 노드는 6,7번 노드의 부모 노드이고, 6,7번 노드는 5번 노드의 자식 노드이다. ③ V-1=E 를 만족, 즉 간선의 수는 (노드의 수-1)이다.④ 임의의 두 노드 사이에는 단 1

그래프, 트리 자료구조에 이어 힙에 대해 알아보고자 한다. 힙은 완전 이진 트리 기반의 자료구조이며, 최소힙과 최대힙 2가지 종류가 있다. ※ 완전 이진 트리란?① 최대힙: 루트 노드에 있는 키는 모든 자식에 있는 키 중에 가장 크도록 한다. 또한 각 노드의 자식 노드

그래프와 양대산맥을 이루는 DP는 코딩테스트 단골문제 이자, 많은 응용이 가능한 알고리즘이다.Divide and Conquer과 차이점?분할 정복 또한, 하나의 문제를 하위 문제로 분할하는 방식이지만i. Divide and Conquer는 하위 문제를 독립적으로 해결한

단순히 조건문/반복문 등을 사용해 모든 경우의 수(case)마다 계산하여 답을 구하는 방법으로, N이 커지는 경우에는 사용이 불가하다.대부분의 경우 사용될 일이 거의 없다고 보면 된다. 완전 탐색의 경우 DFS/BFS 알고리즘과 함께 활용되는 경우가 많다. 가령 길찾기

※ 문제 출처https://school.programmers.co.kr/learn/courses/30/lessons/42883주어진 수(string)에서 k개의 숫자를 제거한 수 중 가장 큰 수(string)를 반환하는 아주 심플해보이는 알고리즘 문제이다.12

※ 문제 출처프로그래머스 lv3. 하노이의 탑이 문제는 오래된 고전 문제 중 하나로 이해하기 어렵지 않다.기둥은 3개가 있으며, 1번 원반에 N개의 원판이 있다. 이 N개의 원판을 모두 3번 기둥으로 옮기는 최소 횟수를 구하도록 한다.제약 조건\-> 원판을 쌓을 때는

※ 문제 출처프로그래머스 lv3. 하노이의 탑이 문제는 오래된 고전 문제 중 하나로 이해하기 어렵지 않다.기둥은 3개가 있으며, 1번 원반에 N개의 원판이 있다. 이 N개의 원판을 모두 3번 기둥으로 옮기는 최소 횟수를 구하도록 한다.제약 조건\-> 원판을 쌓을 때는

순열과 조합은 익히 아는 개념일 것이다.순열은 N개 중 r개를 뽑아서 줄세우는 경우의 수 = nPr조합은 N개 중 r개를 뽑는 경우의 수 = nCr\-> 즉 순열과 조합의 차이는 "줄세우기"의 유무이다. nPr = nCr x r!그렇다면 프로그래밍을 하다보면 이러한

문제 출처 : 프로그래머스 순위 검색 lv2"java and backend and junior and pizza 100"\-> java로 코딩테스트를 봤으며, backend 직군을 선택했고 junior 경력이면서 소울푸드로 pizza를 선택한 지원자 중 코딩테스트 점

1. Greedy 알고리즘이란? 문제 해결의 각 단계에서 최선의 선택을 함으로써 전체 문제에 있어서 최적의 해를 찾는 것. 즉, 각 단계 별 최선의 선택을 계쏙 진행하여 전역적으로 최적의 해를 찾고자 한다. Greedy 알고리즘은 비교적 간단하게 적용되지만, 항상 최

지난 글(hjee02018.log - Greedy 활용 ① )에 이어 Greedy를 활용한 문제 풀이를 해보도록 한다.문제 출처 : 프로그래머스 구명보트 lv2배에 최대 2명을 태울 수 있으며, 태운 무게는 limit을 넘지 않도록 하는 최소 보트의 수를 구할 것① 입

지난 글 hjee02018.log - Greedy 활용 ② 에 이어 Greedy를 활용한 문제 풀이를 해보도록 한다.문제 출처 : 프로그래머스 섬 연결하기 lv2.모든 정점(섬)을 연결하는 다리의 최소 건설 비용을 구할 것위 문제의 경우 별다른 제한 사항이라기 보다 다

지난 글 hjee02018.log - Greedy 활용 ②에 이어 Greedy를 활용한 문제 풀이를 해보도록 한다.문제 출처 : 프로그래머스 단속카메라 lv2.① 진출지점 기준 오름차순 정렬② 차량마다 진입 위치가 이전 차량의 진출 위치보다 크다면 카메라 설치 (반복)

1. 문제 개요 문제 출처 : 프로그래머스 아이템 줍기 lv3 1) 문제 정의 사각형의 외각 경로를 따라 (characterX,characterY) -> (itemX,itemY) 최소 이동 경로를 구할 것 2) 제한 사항 ![](https://velog.velcd

데이터의 연산(산술연산, 논리 연산등) 수행 시 대부분의 경우 수치 및 논리적 조건을 다룰 때 bit 단위가 아닌 변수가 나타내는 데이터의 단위로 연산이 수행된다. 그러나, ip나 서브넷 마스크를 다루거나, 플래그 설정 및 해제 등의 경우에서는 비트 단위의 연산이 요

※ 문제 출처 : 소프티어 징검다리 lv3.dpi : i번째 돌을 밟을 때를 마지막으로 하는 연속된 돌의 최대 길이dp 배열의 최대값을 찾으면 그 값이 철수가 밟을 수 있는 돌의 최대 개수이다.위 코드 실행 및 제출 시 다음과 같은 결과를 확인할 수 있다.시간 초과 혹

문제 출처 : 프로그래머스 땅따먹기 lv2.1행(5) -> 2행(7) -> 3행(4) = 16점 획득① N행X4열로 구성된 맵의 1행부터 N행까지 이동② 각 행마다 한 개의 열만 지날 수 있음③ 같은 열은 연속해서 밟을 수 없음④ N행을 모두 탐색 후 최고점을 retu

1. 문제 개요 문제 출처 : 프로그래머스 퍼즐조각채구이 lv3 1) 문제 정의 초기 상태가 위와 같다고 하자. 좌측은 게임보드 현상태, 우측은 놓을 수있는 퍼즐의 상태 놓는 순서 : ③ -> ④ -> ⑤ > ③ -> ④ : 빈칸이 생김 ⑤ : 양옆에 빈칸 존재

boj 23288. 주사위 굴리기2N x M 지도의 (1,1) 위치에 주사위가 놓여있다. 주사위가 동서남북으로 이동하며 얻게되는 점수를 계산한다. 주사위의 초기 이동 방향은 '동'쪽이다.주사위는 이동 방향으로 +1칸 쿨러간다. 만약 칸이 없다면(지도 밖의 범위라면) 반

프로그래머스 PCCP 기출/석유시추 lv2.NxM 격자 지도 위 석유가 존재한다. 석유는 "덩어리" 단위로 존재하며, 시추관은 "수직으로" 단 하나만 뚫을 수 잇다. 이때 가장 많은 석유를 뽑을 수 있는 시추관의 위치를 찾도록 한다.만약 위와 같이 석유가 존재하는 경우

※ 문제 출처 : 프로그래머스 k진수에서 소수 개수 구하기 lv2. 1. 개요 1) 문제 개요 2) 입출력 형식 3) 제한 사항 2. Solution I. 1) 알고리즘 개요

※ 출처 : 프로그래머스>PCCP 기출 LV2. 충돌 위험 찾기 1. 문제 개요 1) 문제 설명 (r,c) 좌표 (r: x좌표, c: y좌표) 로봇마다 다음 포인트로 이동 시 최단 경로를 잡을 때, 행(위아래) 이동을 먼저 수행 -> 열(좌우)이동 동일 좌표에 로봇