알고리즘

알고리즘 들어가기

1. 순차 탐색과 이진 탐색 ⚠️ex. 891, 358, 250, 915, 324, 797, 738, 151, 230, 198 세 자리 자연수 ABC는 위 수열 내에 존재할까? 만일 존재한다면 어느 위치에서 ABC를 찾을 수 있을까? ✅Sequential Search

Max Heap 자료구조를 이용해 다음의 절차를 거쳐 정렬을 수행1\. 비어 있는 Heap에 주어진 원소를 순서대로 삽입하되 도중에 Heap의 성질이 유지되게끔 함2\. Heap의 최상단에는 최댓값이 존재함이 보장되므로, 새로운 수열의 맨 끝에 Heap 최상단 값을 위

1. 재귀적 접근의 원리와 실제 재귀적 접근이란? recursion 함수의 정의부에서, 함수 자기 자신을 재귀적으로 호출할 수 있음 재귀호출은 분할정복 패러다임 구현을 위한 도구로 흔히 사용됨 문제 해결을 위한 접근과 하향식 접근 문제 해결을 위한 접근은 상향식 bot

1. 동적계획의 이해와 구현 💡Dynamic Programming 과거에 계산하였던 결과 활용 점화식을 세워 문제 해결 피보나치 수열의 항을 DP로 구하기 지난 풀이 1️⃣Memoization ✅top-down 접근법 ✅값을 기록하여 효율성을 높인다. 2️⃣Ta

링크텍스트니보다 연산이 적다!니보다 연산이 크다! 위 두 개의 사이. 샌드위치다 해보는 거 노가다!!!링크텍스트이름 그대로다. 첫번째부터 순차적으로 점검해나가는 것정렬이 되어 있다는 전제!!!!!이진 탐색의 이름따라 반으로 가른다!반에 나오는 수가 찾고자 하는 수보다

백트래킹에 대해 알아보자

직선에 대한 점의 좌우 판별...

스털링 수, 카탈란 수, 교란순열

1. 연관분석 알고리즘과 그 개선 지지도: 전체 사례 대비 해당 항목이 등장하는 사례의 비율 보통 분모는 고정되기 때문에 분자만 비교하는 경우가 많다. {A}의 support, {A, B}의 support로 표기한다. Apriori 알고리즘 개념 사전에 지정한 최소 지지도보다 높은 지지도를 갖는 모든 조합을 알아내기 위한 방법 확장과 가지치기를 반복하면...

문제 https://www.acmicpc.net/problem/14620 예제 입력 6 1 0 2 3 3 4 1 1 1 1 1 1 0 0 1 1 1 1 3 9 9 0 1 99 9 11 3 1 0 3 12 3 0 0 0 1 예제 출력 12 풀이 1. 입력 처리 N과 arr 2차원 배열에 화단 가격 입력 받기 2. 방문 배열 생성 이미 꽃을 심은 자리에는...

📍문제 https://www.acmicpc.net/problem/7576 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 ...

문제 https://www.acmicpc.net/problem/2146 N x N 격자에서 1은 땅(섬), 0은 바다다. 서로 다른 두 섬을 잇는 다리를 만들 때, 지나는 바다 칸의 최소 개수를 구하면 된다. 다리는 상하좌우로만 연결되고, 섬 내부 칸은 다리 길이에 포함되지 않는다. 풀이 과정 기본 알고리즘은 완전탐색으로 하면 된다. 각 섬 구분하기...

문제 규영이와 인영이는 1에서 18까지의 수가 적힌 18장의 카드로 게임을 하고 있다. 한 번의 게임에 둘은 카드를 잘 섞어 9장씩 카드를 나눈다. 그리고 아홉 라운드에 걸쳐 게임을 진행한다. 한 라운드에는 한 장씩 카드를 낸 다음 두 사람이 낸 카드에 적힌 수를 비교해서 점수를 계산한다. 높은 수가 적힌 카드를 낸 사람은 두 카드에 적힌 수의 합만큼...

도시 분할 계획 ☑️ 1. 문제 설명 N개의 마을과 그 마을을 연결하는 M개의 길이 있다. 이 마을을 두 개로 분리하여 관리하고 싶다. 최소의 길만 존재하게 하면서 길의 유지비가 최소가 되도록 하여라. 분리된 두 마을 사이에는 길이 없다. ☑️ 2. 알고리즘 선정 이 문제는 결국 마을의 모든 집을 연결하면서 총 유지비를 최소로 만드는 문제이므로, 최소 ...

플로플로

널 위해서라면 하늘의 별도 따다 줄 수 있어

dfs 백트래킹

시그널 보내 찌릿찌릿

미세미세

문제 > [1719번 : 택배] (https://www.acmicpc.net/problem/1719) LV 골드 3 그래프에서 최단 경로를 찾는 문제이다. 다른 문제와의 차이점은 '최단경로'를 찾는 것이 아니라 '최단경로를 위해 첫번째로 방문해야 하는 노드'를 구해야 한다는 것이다. 풀이 과정 플로이드 워셜 알고리즘 '어디를 거쳤을 때 가장 가깝냐'를...

🔑문제 > 19238번: 스타트 택시 Lv : 골드 2 🔑문제 풀이 흐름 1. 택시 위치, 손님 위치 저장하기 1) 택시 위치 택시 시작 위치를 배열로 저장한다. 2) 손님 위치 Customer 객체를 만들어 출발지와 목적지를 저장 customers 리스트에 객체를 저장 2. 손님의 수만큼 반복하여 이동 한 사이클에서 수행하는 과정: 이번에 태울...

문제 > 1976번: 여행가자 LV: 골드 4 주어진 도시 $N$개와 도시 간의 연결 정보($N \times N$ 인접 행렬)를 바탕으로, 정해진 여행 계획($M$개의 도시 순서)을 따라 여행하는 것이 가능한지 판별하는 문제 특징: 중간에 다른 도시를 경유하는 것은 자유롭게 허용되며, 같은 도시를 여러 번 방문할 수 있다. 즉, 두 도시가 직접 연결되어...

문제 백준 11000 : 강의실 배정 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들...

🍊문제 프로그래머스 : 등굣깃 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = 4, n = 3 인 경우입니다.

문제 합승 택시 요금 두 사람(A와 B)이 같은 출발지 S에서 출발해서 각자의 목적지 A, B까지 이동해야 한다. 모든 지점 간 이동 비용이 주어진 그래프가 있을 때, 중간 지점까지 합승 후 갈라지기 혹은 아예 처음부터 따로 이동하기 이 둘 중 가장 비용이 적게 드는 경우의 총 택시요금을 구하는 문제. 풀이 접근 최소 거리를 구하는 그래프 문제이고,...

이분탐색 이해하기

문제 > 백준 9935 문자열 폭발 골드 4 📌 문제 요약 주어진 문자열에서 폭발 문자열(bomb) 이 등장할 때마다 즉시 제거해야 한다. 폭발 문자열이 제거되면 양쪽 문자열이 합쳐지고, 합쳐진 문자열에서도 다시 폭발 문자열이 등장할 수 있다. 모든 폭발이 끝난 후 남은 문자열을 출력하며, 아무 문자도 남지 않으면 "FRULA" 를 출력한다. 📌 ...

문제 > 줄 세우기 골드 3 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다. 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우...

문제 > 백준 : 7682 Lv 5 문제 틱택토 게임은 두 명의 사람이 번갈아가며 말을 놓는 게임이다. 게임판은 3×3 격자판이며, 처음에는 비어 있다. 두 사람은 각각 X 또는 O 말을 번갈아가며 놓는데, 반드시 첫 번째 사람이 X를 놓고 두 번째 사람이 O를 놓는다. 어느 때든지 한 사람의 말이 가로, 세로, 대각선 방향으로 3칸을 잇는 데 성공하면 ...