[프로그래머스] Level 2 : N-Queen(Java)

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/12952 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 N-Queen 문제는 행렬에 퀸을 놓았을 때, 서로 공격할 수 없는 상태가 되도록 배치하는 문제로, 전형적인 백트리킹 알고리즘입니다. 문제를 분석해보면 다음과 같습니다. 퀸은 하나의 행에 하나만 존재할 수 있다. 즉, 재귀함수 탐색의 기준(depth)으로 사용할 수 있습니다. 마지막 행에 퀸 배치를 성공한다면, 가능한 경우의 수가 하나 증가한다. 불가능한 경우는 탐색을 중단해 ..

• format_list_bulleted 알고리즘/프로그래머스
• · 2023. 10. 23.
• textsms

[프로그래머스] Level 3 : 합승 택시 요금(Java)

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 풀이 문제를 읽어보면, 도착 지점까지 가기 위한 최단거리를 구해야 하는 것에서 다익스트라를 떠올릴 수 있지만, 어느 지점까지 같이 이동한 후, 도착점 A, B로 이동하게 된다(물론, 아닌 경우도 있지만). 따라서, 한 지점에서 모든 지점까지의 최단거리를 구하는 것을 넘어서(다익스트라), 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 한다. 이때, 플로이드-워셜 알고리즘..

• format_list_bulleted 알고리즘/프로그래머스
• · 2023. 10. 17.
• textsms