들어가며코딩테스트에서 자주 등장하는 "다각형의 면적" 문제, 어떻게 풀어야 할지 막막했던 경험 있으신가요?오늘은 GIS, 게임 개발, CAD 등 실무에서도 널리 쓰이는 신발끈 공식(Shoelace Formula)을 활용해,백준 2166번 문제를 쉽고 빠르게 해결하는 방법을 소개합니다.문제 요약문제: N개의 꼭짓점으로 이루어진 단순 다각형의 넓이를 구하라.입력: 꼭짓점 좌표가 시계/반시계 방향으로 주어짐출력: 넓이를 소수점 첫째 자리까지 반올림예시 입력40 04 04 30 3예시 출력12.0신발끈 공식(Shoelace Formula)이란?신발끈 공식은 다각형의 꼭짓점 좌표만으로 넓이를 구할 수 있는 강력한 수학 공식입니다.이름의 유래는, 좌표를 곱해가며 더하고 빼는 모습이 신발끈을 엮는 모양과 닮았기 때문..

들어가며코딩 테스트를 준비하는 개발자라면 누구나 한 번쯤 마주치는 그래프 탐색과 최단 경로 문제. 이 글에서는 코딩 테스트에서 자주 출제되는 핵심 알고리즘들을 Python 코드와 함께 정리했습니다.💡 Tip: 이 알고리즘들은 시험장에서 바로 떠올리기 어려울 수 있으므로, 반드시 외워두시기 바랍니다.1. 그래프 탐색 알고리즘1.1 BFS (Breadth-First Search, 너비 우선 탐색)BFS는 가까운 노드부터 탐색하는 알고리즘으로, 큐(Queue) 자료구조를 사용합니다. 미로 찾기, 최단 거리 탐색 등에 자주 등장합니다.from collections import dequedef bfs(graph, start): visited = set() queue = deque([start]) ..

이미지 출처 - https://www.geeksforgeeks.org/backtracking-meaning-in-dsa/"모든 가능성을 탐색해야 하지만 불필요한 경로는 빠르게 포기하는 지혜가 필요합니다. 백트래킹은 마치 미로에서 막다른 길을 만났을 때 이전 갈림길로 되돌아가는 전략적 탐색과 같습니다."목차백트래킹이란?완전탐색과 백트래킹의 차이백트래킹의 적용 조건백트래킹의 동작 원리재귀 함수를 활용한 백트래킹 구현핵심 예제: 순열 구하기시간복잡도 분석백트래킹 문제 유형과 판단 기준실전 구현 팁대표적인 백트래킹 문제결론백트래킹이란?백트래킹(Backtracking)은 해를 찾는 도중에 막히면(해가 아니면) 되돌아가서 다시 해를 찾아가는 알고리즘입니다. 가능한 모든 경로를 탐색하되, 특정 조건을 만족하지 않는 ..

이미지 출처 - https://skilled.dev/course/depth-first-search"그래프를 탐색하는 것은 미로를 탐험하는 것과 같습니다. DFS는 한 길을 끝까지 탐색한 후 다시 돌아와 다른 길을 탐색하는 방식으로, 깊이 있는 탐험을 선호하는 여행자와 같습니다."목차그래프 탐색의 기본 개념DFS란 무엇인가?DFS와 BFS의 차이점재귀 함수의 이해DFS의 동작 원리시간 복잡도 분석DFS 구현에 필요한 자료구조실전 문제 분석: 백준 2667번코드 구현 가이드복습 전략 및 추천 문제결론그래프 탐색의 기본 개념그래프 탐색이란 그래프 구조에서 모든 노드(정점)를 체계적으로 방문하는 과정입니다. 컴퓨터 과학에서 가장 기본적이면서도 중요한 알고리즘 중 하나로, 다양한 실생활 문제 해결에 응용됩니다.그..

이미지 출처 - https://skilled.dev/course/breadth-first-search"모든 길을 가장 효율적으로 탐색하는 방법을 찾는 것은 알고리즘의 핵심 과제입니다. BFS는 마치 물결이 퍼지듯 가까운 곳부터 체계적으로 탐색하는 방법을 제공합니다."목차BFS란 무엇인가?BFS vs DFS: 핵심 차이점BFS의 동작 원리시간 복잡도 분석필요한 자료구조실전 문제 분석: 백준 1926번코드 구현 단계별 가이드최적화 전략과 주의사항학습 전략 및 추천 문제결론BFS란 무엇인가?BFS(Breadth-First Search, 너비 우선 탐색)는 그래프나 트리 구조에서 모든 노드를 효율적으로 방문하기 위한 알고리즘입니다. 시작 노드에서부터 가까운 노드를 먼저 방문하고, 멀리 있는 노드를 나중에 방문하..