[알고리즘] A* 알고리즘

A* (A star algorithm) 알고리즘이란??그래프의 한 정점에서 다른 한 정점까지의 최단거리를 각각 구하는 알고리즘목적지까지의 거리를 계산하는 휴리스틱 추정값을 이용해 다익스트라를 개선한 알고리즘휴리스틱 함수의 성능에 따라 알고리즘 성능이 달라진다. 시간복잡도O(b^d) (완전 탐색) ~ O(E log V) (최적화 시)b는 분기 계수 (한 노드에서 이동할 수 있는 평균 갈래 수)d는 최단 경로의 깊이(시작점에서 목표까지의 단계 수)E는 그래프의 간선 수, V는 노드 수 공간복잡도O(b^d) (최악) ~ O(V) (일반적인 경우)   다익스트라와의 차이점 다익스트라출발점에서 모든 노드에 대한 최단거리를 탐색함단순히 현재 지나온 거리가 가장 짧은 노드를 선택해 탐색A*출발점에서 도착점까지의 최단..

• format_list_bulleted 알고리즘공부/알고리즘
• · 2025. 2. 3.
• textsms

[JAVA] 양궁대회

양궁대회링크 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 3유형 : dfs, 백트래킹코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > 양궁대회 풀이라이언이 어피치를 가장 큰 점수 차이로 이기기 위한 n 발의 화살의 경우의 수를 구하는 문제.근데 가장 큰 점수 차이의 경우의 수가 여러 가지일 경우, 낮은 점수를 더 많이 맞힌 경우가 정답. 각 점수대 마다 라이언이 점수를 가져가냐, 안 가져가냐 둘 중에 하나니까 이걸 그래프로 생각을 해서 dfs로 모든 경우의 수를 보고가장 큰 점수 차이면서 낮은 점수가 더 많이 맞은 경우를 result에 저장하며 풀었다. ..

• format_list_bulleted 알고리즘공부/프로그래머스
• · 2025. 2. 3.
• textsms

[JAVA] 신고 결과 받기

신고 결과 받기링크 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 1유형 : 구현코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > 신고 결과 받기 문제 설명신입사원 무지는 게시판 불량 이용자를 신고하고 처리 결과를 메일로 발송하는 시스템을 개발하려 합니다.무지가 개발하려는 시스템은 다음과 같습니다.각 유저는 한 번에 한 명의 유저를 신고할 수 있습니다. 신고 횟수에 제한은 없습니다. 서로 다른 유저를 계속해서 신고할 수 있습니다. 한 유저를 여러 번 신고할 수도 있지만, 동일한 유저에 대한 신고 횟수는 1회로 처리됩니다. k번 이상 신고된 유저는 게시판 이..

• format_list_bulleted 알고리즘공부/프로그래머스
• · 2025. 2. 1.
• textsms

[JAVA] k진수에서 소수 개수 구하기

k진수에서 소수 개수 구하기링크 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 2유형 : 구현, 소수판별코딩테스트 연습 > 2022 KAKAO BLIND RECRUITMENT > k진수에서 소수 개수 구하기  문제 설명양의 정수 n이 주어집니다. 이 숫자를 k진수로 바꿨을 때, 변환된 수 안에 아래 조건에 맞는 소수(Prime number)가 몇 개인지 알아보려 합니다.0P0처럼 소수 양쪽에 0이 있는 경우P0처럼 소수 오른쪽에만 0이 있고 왼쪽에는 아무것도 없는 경우0P처럼 소수 왼쪽에만 0이 있고 오른쪽에는 아무것도 없는 경우P처럼 소수 양쪽에 아무것도 없는 경우단, P는 각 ..

• format_list_bulleted 알고리즘공부/프로그래머스
• · 2025. 2. 1.
• textsms

[JAVA] 로또의 최고 순위와 최저 순위

로또의 최고 순위와 최저 순위링크 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 1유형 : 구현코딩테스트 연습 > 2021 Dev-Matching: 웹 백엔드 개발자(상반기) > 로또의 최고 순위와 최저 순위 문제 설명 로또를 구매한 민우는 당첨 번호 발표일을 학수고대하고 있었습니다. 하지만, 민우의 동생이 로또에 낙서를 하여, 일부 번호를 알아볼 수 없게 되었습니다. 당첨 번호 발표 후, 민우는 자신이 구매했던 로또로 당첨이 가능했던 최고 순위와 최저 순위를 알아보고 싶어 졌습니다.민우가 구매한 로또 번호를 담은 배열 lottos, 당첨 번호를 담은 배열 win_nums가 매개변..

• format_list_bulleted 알고리즘공부/프로그래머스
• · 2025. 2. 1.
• textsms

[JAVA] 행렬 테두리 회전하기

행렬 테두리 회전하기링크 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 난이도 : Level 2유형 : 배열코딩테스트 연습 > 2021 Dev-Matching: 웹 백엔드 개발자(상반기) > 행렬 테두리 회전하기 문제 설명 rows x columns 크기인 행렬이 있습니다. 행렬에는 1부터 rows x columns까지의 숫자가 한 줄씩 순서대로 적혀있습니다. 이 행렬에서 직사각형 모양의 범위를 여러 번 선택해, 테두리 부분에 있는 숫자들을 시계방향으로 회전시키려 합니다. 각 회전은 (x1, y1, x2, y2)인 정수 4개로 표현하며, 그 의미는 다음과 같습니다.x1 행 y1 열부터 x2 행 y2 열..

• format_list_bulleted 알고리즘공부/프로그래머스
• · 2025. 2. 1.
• textsms