본문 바로가기

알고리즘8

투포인터 (Two-Pointer) 알고리즘 00 개요목표: 코딩테스트 뽀개기!01 투포인터1. 투포인터란각 원소마다 모든 값을 순회해야할 때, O(N^2)연속하다는 특성을 이용해서 처리, O(N)두 개의 포인터(커서)가 움직이면서 계산처음부터 생각해내기 어려움, 쉬운 방법부터 생각하는 것 추천 (i.e., 일일히 다 계산해 본 후, 어떠한 패턴이 보이면 그 때 적용해보기)2. 연습 문제: 백준 2559 수열참조: https://www.acmicpc.net/problem/25591) 문제Q:매일 아침 9시에 학교에서 측정한 온도가 어떤 정수의 수열로 주어졌을 때, 연속적인 며칠 동안의 온도의 합이 가장 큰 값을 알아보고자 한다. 예를 들어, 아래와 같이 10일 간의 온도가 주어졌을 때, 3 -2 -4 -9 0 3 7 13 8 -3 모든 연속적인 이.. 2025. 2. 7.
DP (Dynamic Programming) 알고리즘 00 개요목표: 코딩테스트 뽀개기!01 DP1. DP란Dynamic Programming이전의 값을 재활용하는 알고리즘예) 1 ~ 10 숫자 중 각각 이전 값들을 합한 값 구하기이전의 값을 활용해서 시간복잡도 축소 가능2. 연습 문제: 백준 117262×n 타일링링크: https://www.acmicpc.net/problem/117261) 문제Q:2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.입력:첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)출력:첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.예제 입력 1:더보기2예제 출력 1:더보기.. 2025. 2. 6.
시뮬레이션 (Simulation) 알고리즘 00 개요목표: 코딩테스트 뽀개기!01 시뮬레이션1. 시뮬레이션이란각 조건에 맞는 상황을 구현하는 문제예: 지도상에서 이동하면서 탐험하는 문제, 배열 안에서 이동하면서 탐험하는 문제 등별도의 알고리즘이 없이 풀 수 있으나 구현력 중요매 시험마다 1문제 이상 무조건 출제됨2. 준비하기다른 알고리즘들과 달리, 상황을 보고 판단!3. 연습 문제: 백준 14503 로봇 청소기링크: https://www.acmicpc.net/problem/14503비고: 현재는 웹사이트에 없는 문제1) 문제Q:로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.로봇 청소기가 있는 장소는 N x M 크기의 직사각형으로 나타낼 수 있으며, 1 x 1 크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽.. 2024. 12. 21.
DFS (Depth-first search) 알고리즘 00 개요목표: 코딩테스트 뽀개기!1. 그래프 탐색이란 어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법 Graph: Vertex (어떤 것) + Edge (이어지는 것)2. 그래프 탐색 종류BFS: Breadth-first search (너비 우선 탐색)DFS: Depth-first search (깊이 우선 탐색) 01 DFS1. DFS란Depth-first search, 깊이 우선 탐색그래프 탐색 종류 중 하나Stack 또는 재귀 함수 사용, Queue 미사용!재귀 함수는 백트래킹 알고리즘에서도 사용!2. 재귀함수란자기 자신을 다시 호출하는 함수# 예시def my_function(a): c = a + 1 if c 주의: 재귀 함수가 종료되는 시점을 반드시 명시해야 됨재귀 함수의 깊이가 .. 2024. 11. 8.
BFS (Breadth-first search) 알고리즘 00 개요목표: 코딩테스트 뽀개기!1. 그래프 탐색이란어떤 것들이 연속해서 이어질 때, 모두 확인하는 방법Graph: Vertex (어떤 것) + Edge (이어지는 것)2. 그래프 탐색 종류BFS: Breadth-first search (너비 우선 탐색)DFS: Depth-first search (깊이 우선 탐색) 01 BFS1. BFS란Breadth-first search, 너비 우선 탐색그래프 탐색 종류 중 하나Queue 사용, Stack 미사용!2. 준비하기1) 아이디어시작점에 연결된 Vertex 찾기 찾은 Vertex를 Queue에 저장 Queue의 가장 먼저 것 뽑아서 반복2) 시간 복잡도O(V+E)3) 자료구조검색할 그래프 방문여부 확인(재방문 금지) Queue: BFS 실행3. 연습 문제:.. 2024. 11. 4.
코딩테스트 개요 00 개요다짐: 코딩테스트 뽀개자1. 코딩테스트란시간 안에 주어진 문제를 푸는 시험, 적절한 알고리즘 선택하여 문제 해결이 목적채점 방식: 입력값을 여러개 넣고, 모두 통과하는지 확인 (하나라도 통과 못하면 틀림)공부 방법: 개념 이해, 기본 문제, 코드 imitate, 안 보고도 코드 작성할 수 있을 정도로 외우기, 유사 문제 풀어보기각 알고리즘 이해 후: 하루에 몇 과목 씩 돌아가면서 풀기, 한 문제 Max 30분 넘기지 않기, 틀린 문제 복습하면서 반복, 시간 정하면서 문제 풀기, 스터디 활용2. 필수 알고리즘 10개:BFS, DFS, 백트래킹, 시뮬레이션, 이진탐색, Greedy, DP, MST, 다익스트라, 플로이드3. 문제 페이지백준: https://www.acmicpc.net/프로그래머스: .. 2024. 11. 4.
2 초급 알고리즘 (sum, sequence, count, avg, max, min) 00 개요목표: Visual Studio라는 IDE를 사용하여 C 알고리즘 구현하기01 Visual Studio 사용하여 프로그램 만들기1. 솔루션 탐색기 보기'보기' > '솔루션 탐색기' 클릭2. 새 프로젝트 만들기Visual Studio 연 후 '새 프로젝트 만들기' 클릭 또는 '파일' > '새로 만들기' > '프로젝트' > '빈 프로젝트'프로젝트 이름: 원하는 거로 지정위치: 원하는 위치 지정솔루션: 새 솔루션 만들기솔루션 이름: 원하는 거로 지정> '만들기' 3. c 파일 또는 c++ (소스 파일) 생성Visual Studio 연 후 어느 프로젝트 안에서 시작솔루션 탐색기에 어느 '프로젝트명' > '소스파일' 우클릭 > '추가' >  '새 항목' > 'C ++ 파일' 한 번 클릭 > '파일명.c'.. 2024. 6. 18.
1 알고리즘과 절차 지향 프로그래밍 01 알고리즘과 절차 지향 프로그래밍배우기 쉬운 알고리즘을 몇 가지 소개할 것지금까지 배운 프로그래밍 언어의 기능으로 특정 문제를 해결하는 코드를 작성하는 기법을 배울 것알고리즘을 바탕으로 입력, 처리, 출력의 단계로 진행되는 프로그래밍 언어의 절차 지향 프로그래밍 기법을 정리함절차 지향 프로그래밍에서 사용되는 것이 입력, 처리, 출력의 단계1. 알고리즘 (Algorithm)알고리즘(풀이법)이란, 프로그램 개발에 있어 필요한 문제를 해결하는 방법을 체계적으로 정리한 것, 즉, "문제 해결 능력"주어진 문제를 어떻게 풀이하는가에 따라 그 문제를 해결할 수도, 못할 수도 있으므로 프로그램 작성에 있어 알고리즘이란 중요한 자리를 차지하고 있음프로그램의 가장 작은 단위는 일반적으로 입력(input) → 처리(p.. 2024. 6. 15.