본문 바로가기

전체 글110

크루스칼 알고리즘 (Kruskal Algorithm) 크루스칼 알고리즘을 이해하기 위한 필수 개념 1. 신장 트리 : 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 없는 부분 그래프를 의미한다. 2. 최소 신장 트리 : 신장 트리 중에서 최소한의 비용으로 구현된 신장트리를 의미한다. 크루스칼 알고리즘은 최소 신장 트리 알고리즘이며 그리디 알고리즘으로 구현된다 ! 크루스칼 알고리즘의 동작 과정 1. 간선 데이터를 비용에 따라 오름차순 정렬한다. 2. 모든 간선을 한번씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. 사이클 발생하지 않는 경우 => 최소신장트리에 추가한다. 사이클 발생하는 경우 => 최소신장 트리에 추가시키지 않는다. 1. 간선 데이터를 비용에 따라 오름차순 정렬 간선 ( 3 , 5 ) ( 4 , 5 ) ( 1 , 3 ) (.. 2024. 3. 4.
프로그래머스 땅따먹기 파이썬 1. dfs(x) 가능한 모든 경우의 수를 구하기 위해 dfs를 사용했다. 깊이가 깊어지면 런타임에러가 발생하게 된다. answer=0 def dfs(land,now_x,now_y,pre_y,tot): global answer if len(land)==now_x: answer=max(answer,tot) elif pre_y != now_y: for i in range(4): dfs(land,now_x+1,i,now_y,tot+land[now_x][now_y]) def solution(land): global answer for i in range(4): dfs(land,0,i,-1,0) return answer 2. i행에서 i-1행을 값 선택 i행의 각 값에 선택할 수 있는 i-1행의 값들중 가장 큰값.. 2024. 2. 23.
프로그래머스 모음사전 파이썬 완전탐색 알고리즘에 관한 문제이다. 이 문제는 permutations함수를 사용할 사용할 수 없고 재귀 함수를 이용해야 하는 문제이다. dfs를 돌면서 현재 값의 순서를 1씩 증가시켜주고 word와 동일한 단어가 되면 해당 단어의 순서를 ans에 넣어주었다. ans=0 cnt=0 alphabet=['A','E','I','O','U'] def dfs(word,str): #arr에 알파벳 추가 global alphabet,ans,cnt if str==word: ans=cnt #현재 단어와 word값 일치시 정답에 현재단어순서(cnt)를 넣음 return for i in range(len(alphabet)): if len(str) 2024. 2. 23.
프로그래머스 게임 맵 최단거리 파이썬 1. dfs 사용 (x) bfs 사용하기 위해서는 현재 위치를 다시 방문하지 않아야 하는데 이 문제는 오른쪽, 아래로 이동할 뿐만 아니라 위, 왼쪽으로 이동도 가능하므로 현재 위치를 또 방문할 가능성이 생긴다. 따라서 bfs가 아닌 완전탐색 문제로 풀어야 한다. 그러나 완전탐색으로 풀면 깊이가 너무 깊어져 효율성 테스트에서 런타임 오류가 발생한다. import sys answer= sys.maxsize #int 최대값으로 초기화 # cnt = 이동한 칸 횟수 , point = 현재 위치 좌표 , check = 방문한 좌표인지 확인하기 위해 def dfs(maps,cnt,point,check): global answer if point[0]==len(maps)-1 and point[1]==len(maps[.. 2024. 2. 23.
쇼핑몰 구현 16 - Handler 1. GlobalExceptionHandler @ControllerAdvice public class GlobalExceptionHandler { //재고부족 예외처리 @ExceptionHandler(NotEnoughStockException.class) public String handleNotEnoughStockException(NotEnoughStockException e, Model model){ model.addAttribute("message","재고수량보다 주문수량이 많습니다."); model.addAttribute("nextUrl","/"); return "printMessage"; } //해당 상품 존재하지 않을 때 사용 @ExceptionHandler(EntityNotFoundExcep.. 2024. 2. 23.
쇼핑몰 구현 15 - 메일 인증 기능 1. MailSendService @Service public class MailSendService { @Autowired private JavaMailSender mailSender; @Autowired private RedisUtil redisUtil; private int authNumber; public boolean checkAuthNum(String email, String authNum){ if(redisUtil.getData(authNum)==null){ System.out.println("authNum=null"); return false; } else if(redisUtil.getData(authNum).equals(email)){ return true; } else{ System.o.. 2024. 2. 23.

티스토리툴바