[백준 #1185]: 유럽여행 (python)
백준#1185:유럽여행 > 이 문제는 크루스칼알고리즘으로 해결할 수 있다. 하지만 중요한 점은 가중치를 a + b + (c x 2) 로 계산해야한다. 왜냐하면 MST에서 다시 시작 노드로 돌아오는 경우는 되돌아오는 경우 밖에 없기 때문이다. 하지만 여기서 의문점이 들
[백준 #1786]: 찾기(python)
\[백준문제 설명에서도 잘 나와있듯이 KMP 알고리즘을 활용하여 풀면 된다. kmp에 대한 설명은 아래 링크를 참고하면 된다.KMP 정리
[내용정리] Spring boot - 스프링 웹 개발 기초
스프링 입문 - 코드로 배우는 스프링 부트, 웹 MVC, DB 접근 기술1\. 웹 브라우저에서 url을 입력하면 내장 톰켓 서버에서 요청을 받는다.2\. 톰켓 서버는 스프링에게 요청을 넘긴다.3\. 스프링은 controller 쪽에서 hello-static이 있는지 먼
[내용정리] Spring boot -프로젝트환경설정
스프링 입문 - 코드로 배우는 스프링 부트, 웹 MVC, DB 접근 기술스프링 부트가 제공하는 Welcome Page 기능 \- static/index.html 을 올려두면 Welcome page 기능을 제공한다. 공식 사이트 링크(https://docs.
[알고리즘] 라빈-카프 알고리즘 (Rabin-Karp)
해시 값이 다르다면 두 문자열은 다르다는 것이 보장된다. 하지만 문자열이 달라도 해시 값이 같을 수 있다.Spurious Hit 때문에 해시 값이 같을 경우 추가로 문자열이 같은지 비교하는 작업이 필요하다. 이 특징을 사용하여 Rabin-Karp 알고리즘은 패턴의 해시
[알고리즘] KMP 알고리즘 (Knuth-Morris-Pratt Algorithm)
KMP 알고리즘은 패턴을 문장안에서 좌에서 우로 비교하는 것인데, Brute-force 알고리즘과 다르게 패턴의 위치를 좀 더 효율적으로 이동시킨다. 패턴과 문장의 불일치가 발생했을 때 중복연산을 최대한 피하면서 패턴을 우측으로 이동시킨다. 이를 위해서는 문장의 불일치
[백준 #15686]: 치킨 배달(python)
\[백준해당 문제는 굉장히 간단한 문제이다. 선정할 수 있는 치킨집에 대한 모든 경우의수를 조사한뒤 각각의 집의 거리를 조사한다. 그 뒤 가장 짧은 거리를 계속해서 더해주어 선정한 치킨집에 대한 치킨거리를 구한 뒤 치킨 집에 대한 모든 경우의수를 이용하여 치킨거리를 구
[백준 #14890]: 경사로(python)
\[백준이 문제는 아이디어만 잘 생가각하면 쉽게 풀 수 있는 문제이다. 각각의 길을 들고와서 현재 블럭과 이전블럭을 비교한다. 만약 현재 블록과 이전블록의 차이가 1보다 크다면 경사로를 설치할 수 없으니 바로 끝낸다. 만약 -1 또는 1이라면 현재블록이 이전블록보다 작
[프로젝트][대회] 메타버스 해커톤(유니티)
정부가 농촌을 이끌어갈 인력으로 육성해온 농민후계자와 후계농업인 산업기능요원, 농업전문학교 지원자들이 해마다 감소하고 있다.또 이미 농촌에 정착한 젊은층도 갈수록 어려워지는 농업여건 때문에 농촌을 이탈하고 있어 새로운 농촌인력 충원구조가 필요하다는 지적이 제기되고 있다
[백준 #4195]: 친구 네트워크(python)
\[백준해당문제는 서로소집합 자료구조를 활용하여 해결하였다. 하지만 효율적인 구조를 위해 union_parent함수를 수정하였다.count 딕셔너리형 변수를 추가하여 해당 변수에 자식 노드의 개수를 더하도록 설계하였고 해당 변수를 출력한다.
[알고리즘] 최소 신장 트리 (Minimum Spanning Tree)
그래프 내의 모든 정점들을 포함하는 그래프의 부분집합(subgraph) Tree최소한의 간선들로 그래프 내의 모든 정점을 포함 \- 따라서 Spanning Tree는 cycle을 포함하지 않음 \- 그래프 내의 정점의 수가 n개이면, Spanning Tree는 (n
[자료구조] 서로소 집합 (Disjoint Sets)
서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조서로소 집합 자료구조는 두 종류의 연산을 지원한다 \- 합집합(Union): 두 개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 \- 찾기(Find): 특정한 원소가 속한 집합이 어떤 집합
[백준 #1197]: 최소 스패닝 트리(python)
백준#1197:최소 스패닝 트리 >해당 문제는 최소 신장트리를 크루스칼 알고리즘을 이용하여 구현하여 해결하였다.
[알고리즘] 다익스트라 (Dijkstra)
최소 비용 중에서도, 주어진 두 노드(시작노드 , 도착노드) 사이의 최소 비용인 경로를 찾을 때 유용하게 사용된다.시작 노드와 직접적으로 연결된 모든 정점들의 거리를 비교해서 업데이트 시켜주고, 시작 노드를 방문한 노드로 체크한다.방문한 정점들과 연결되어 있는 정점들
[백준 #1916]: 최소 비용 구하기(python)
\[백준해당문제는 다익스트라 알고리즘을 활용하면 굉장히 쉽게 풀린다. 중요한 포인트는 효율을 위해 내가 원하는 도시에 최단경로가 확정이 났을경우 출력시켜주고 프로그램을 종료시켜준다.
[알고리즘] 이진 탐색 (Binary Search)
오름차순으로 정렬된 배열에서 원하는 숫자(target)을 찾는 알고리즘배열 전체의 중간값을 target 값과 비교중간값이 target 값보다 크면 왼쪽 부분만 선택왼쪽부분의 중간값을 다시 target 과 비교검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속
[백준 #1700]: 멀티탭 스케줄링(python)
\[백준해당문제는 골드1수준치고는 쉬운문제였다. 그리디 알고리즘을 이용하여 푸는 문제인데 알고리즘 자체는 간단하다.일단 멀티탭에 자리가 있다면 꼽아주고 자리가 부족하다면 멀티탭에 해당 코드가 있는지 검사해준다. 만약 없다면 꼽아야하는 코드중에서 현재 꼽혀있는 코드와 비
[백준 #1062]: 가르침(python)
\[백준해당 문제는 브루트 포스 방식으로 해결할 수 있다. 하지만 시간 초과를 해결하기위해 비트마스킹 기법을 사용해야한다. combinations을 사용하여 a,c,i,t,n을 제외한 문자들로 이루어진 모든 경우의 수를 만들고 비트마스킹 기법을 이용하여 포함관계에 있는
[백준 #3085]: 사탕 게임(python)
\[백준해당 문제는 브루트포스 알고리즘을 활용하여 해결하였다. 모든 사탕의 위치들을 바꾸어 보고 가장 많이 연결 된 사탕의 개수를출력하면 된다. 나는 최대한 효율적으로 구현하기위해 좌우를 기준으로 위치를 바꿀 경우에는 해당 사탕들의 행에대한 검사와 각각의 사탕에 대한