본문 바로가기

전체 글275

[이코테]9장_다익스트라 알고리즘, 플로이드 워셜 알고리즘 다익스트라 최단 경로 알고리즘 다익스트라 최단 경로 알고리즘 최단 경로 문제 최단 경로 알고리즘은 가장 짧은 경로를 찾는 알고리즘을 의미함 다양한 문제 상황 한 지점에서 다른 한 지점까지의 최단 경로 한 지점에서 다른 모든 지점까지의 최단 경로 모든 지점에서 다른 모든 지점까지의 최단 경로 각 지점은 그래프에서 노드로 표현 지점 간 연결된 도로는 그래프에서 간선으로 표현 다익스트라 최단 경로 알고리즘 개요 특정한 노드에서 출발하여 "다른 모든 노드"로 가는 최단 경로를 계산한다 다익스트라 최단 경로 알고리즘은 음의 간선이 없을 때 정상적으로 동작한다 현실 세계의 도로(간선)은 음의 간선으로 표현되지 않습니다 다익스트라 최단 경로 알고리즘은 그리디 알고리즘으로 분류된다 매 상황에서 가장 비용이 적은 노드를.. 2024. 3. 7.
[이코테]8장_다이나믹 프로그래밍 문풀 _개미_전사:_문제_설명" style="color: #000000; text-align: left;" data-ke-size="size26"> 개미 전사: 문제 설명개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 메뚜기 마을에는 여러 개의 식량창고가 있는데 식량창고는 일직선으로 이어져 있다각 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으면 바로 알아챌 수 있다따라서 개미 전사가 정찰병에 들키지 않고 식량창고를 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다예를 들어 식량창고 4개가 다음과.. 2024. 3. 5.
[이코테]6장_정렬 문풀 정렬 알고리즘 비교하기앞서 다룬 네 가지 정렬 알고리즘을 비교하면 다음과 같다추가적으로 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN) 을보장하도록 설계되어 있다정렬 알고리즘평균 시간 복잡도공간 복잡도특징선택 정렬O(N²)O(N)아이디어가 매우 간단하다삽입 정렬O(N²)O(N)데이터가 거의 정렬되어 있을 때는 가장 빠르다퀵 정렬O(NlogN)O(N)대부분의 경우에 가장 적합하며, 충분히 빠르다계수 정렬O(N + K)O(N + K)데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠르게 동작한다선택 정렬과 기본 정렬 라이브러리 수행 시간 비교from random import randintimport time#배열에 10000개의 정수를 삽입array.. 2024. 3. 3.
[이코테]10장-개발형 코딩 테스트 개발형 코딩 테스트 정해진 목적에 따라서 동작하는 완성된 프로그램을 개발하는 것을 요구하는 코딩 테스트 유형 일부 기업은 해커톤을 통해 채용을 진행한다 해커톤(Hackathon)이란 단기간에 아이디어를 제품화하는 프로젝트 이벤트이다 대개 1~2일 정도 진행되며 다수의 해커톤이 대회 형식을 빌려 해커톤이 끝나면 만든 프로그램을 시연하고 발표한 다음 채점을 진행한다 개발형 코딩 테스트는 분야에 따라 상세 요구사항이 다를 수 있다 예시 1) 모바일 클라이언트 개발: 안드로이드, iOS 앱 개발 예시 2) 웹 서버 개발: 스프링(Spring), 장고(Django) 등의 서버 개발 프레임워크 활용 하지만 분야에 상관없이 꼭 알아야 하는 개념과 도구에 대해서 학습할 필요가 있다 서버, 클라이언트, JSON, RES.. 2024. 3. 3.
[이코테]7장_이진탐색 문풀 파라메트릭 서치 (Parametric Search)원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제파라메트릭 서치란 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법이다예시: 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다_떡볶이_떡_만들기:_문제_설명" style="color: #000000; text-align: left;" data-ke-size="size23"> 떡볶이 떡 만들기: 문제 설명오늘 동빈이는 여행 가신 부모님을 대신해서 떡집 일을 하기로 했다. 오늘은 떡볶이 떡을 만드는 날이다.동빈이네 떡볶이 떡은 재밌게도 떡볶이 떡의 길이가 일정하지 않다. 대신에 한봉지 .. 2024. 2. 20.
[이코테]3장_구현 문풀 구현: 시뮬레이션과 완전 탐색 구현(Implementation) 구현이란, 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정이다 흔히 알고리즘 대회에서 구현 유형의 문제란 무엇을 의미할까? 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제를 지칭한다 구현 유형의 예시는 다음과 같다 알고리즘은 간단한데 코드가 지나칠 만큼 길어지는 문제 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제 적절한 라이브러리를 찾아서 사용해야 하는 문제 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬(Matrix)의 의미로 사용된다 for i in range(5): for j in range(5): print("(", i , ",", j, ")", en.. 2024. 2. 19.

티스토리툴바