본문 바로가기

Set4

[백준/C++] 새로운 하노이 탑 (No. 12906) 문제 문제 설명 ">문제 문제 설명 풀이 ">풀이 [문제 풀이] 이 문제는 N이 최대 10이기 때문에 모든 경우를 생각해보면 3종류의 원판을 순서대로 하노이 탑의 막대에 놓는 것과 같다. 그러므로 최대 (3^10)의 경우의 수만 고려하면 된다. (물론 중복 경우도 있기 때문에 실제로는 더 적을 것이다.) 잘 생각해보면 하노이탑을 정상적으로 만드는데 걸리는 최소 횟수를 구하는 것이므로, 각 막대에서 다른 막대로 원판을 옮기는 경우를 BFS로 구하면 빠르게 계산할 수 있다. 왜냐하면 BFS로 구할 경우 처음 하노이 탑이 정상적으로 완성 되는 경우가 가장 적게 원판을 이동시켜 정상적으로 만든 경우가 되기 때문이다. 여기서 중복되는 경우를 체크하기 위해 Set을 이용했다... 2025. 1. 17.

[프로그래머스/C++] 등산코스 정하기 (2022 KAKAO TECH INTERNSHIP) HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 [문제 풀이] 이 문제에서 핵심은 특정 노드를 방문할 때마다 경로 중에서 가장 시간이 오래걸린 값을 저장해야 된다는 것이다. 그리고 가장 시간이 오래 걸리는 구간의 크기가 같다면 봉우리의 숫자가 가장 작은 값을 return해야한다. 이와 비슷한 문제를 해결하는 알고리즘 중에는 다익스트라 알고리즘이 있는데, 다익스트라 알고리즘은 최단 경로를 구하는 알고리즘으로 가장 작은 값을 계속해서 계산해 나가는 알고리즘이다. 이 문제도 마찬가지로 항상 intensity가 가장 작은 값을 가지고 있으면서 만약 intensity가 같다면 mountain의 번호가 가장 작은 경로를 먼저 계산하면 편하다. 여기서 위 그림과 같이 S에서 시작을 한다.. 2024. 3. 7.

[프로그래머스/C++] 불량 사용자 HTML 삽입 미리보기할 수 없는 소스 HTML 삽입 미리보기할 수 없는 소스 이 문제는 중복된 경우의 수를 제거하는게 핵심인 문제다. 먼저 banned_id 와 user_id를 비교해서 ban을 할 수 있는 사용자 목록을 뽑고, ban할 수 있는 경우의 수를 완전 탐색해 풀었다. 이 때, 한번 ban할 수 있는 목록으로 뽑힌 사용자가 다시 뽑힐 수 는 없으므로 이 경우를 제거했고, ban할 수 있는 사용자가 전부 뽑히면 Set에 넣어 중복을 제거 했다. [아이디어 정리] user중 ban할 수 있는 사용자의 목록을 뽑는다. ban 할 수 있는 사용자들이 중복되지 않게 뽑고, Set에 넣어 중복을 제거한다. 최종적으로 구한 Set의 size를 return 한다. HTML 삽입 미리보기할 수 없.. 2024. 1. 6.

[백준/Python] 18870번 - 좌표 압축 HTML 삽입 미리보기할 수 없는 소스 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 N이 주어진다. 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다. HTML 삽입 미리보기할 수 없는 소스 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다. HTML 삽입 미리보기할 수 없는 소스 1 ≤ N ≤ 1,000,000 -109 ≤ Xi ≤ 10.. 2024. 1. 2.

이전 1 다음

티스토리툴바