본문 바로가기

💻 알고리즘

 (215)
[ 프로그래머스 ] 호텔 대실 (파이썬 python) https://school.programmers.co.kr/learn/courses/30/lessons/155651 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr    💕풀이 방법 처음에 문제를 보고 든 생각은 입실과 퇴실 시간을 분으로 맞춰서 계산해야겠다 였다.입퇴실 모두 분 단위로 변경해서 정렬을 한 뒤, 가장 빠른 입실 시간을 기준으로 퇴실 시간 + 10분뒤 입실이 가능한 예약건을 찾으려면 for문을 사용해야 한다는 생각이 들었다. 그리고 그 다음번 새로운 방 입실을 처리하고 나면 이중 for문을 돌려야하나..? 라는 생각을 하게됐고,주어진 book_..
[ 프로그래머스 ] 두 원 사이의 정수 쌍 (파이썬 python) https://school.programmers.co.kr/learn/courses/30/lessons/181187 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr     💕풀이 방법 1️⃣ 원의 방정식을 사용해 y가 최솟값일 때, 최댓값일 때를 구해서 계산해 주면 되는 문제다.단, 반지름의 최대 범위가 크기 때문에 모든 점들을 구하는게 아니라 1 사분면에 있는 점들을 구한 후 4를 곱해주면 된다(예시 속 그림을 보면 대칭한다는 것을 알 수 있음) 원의 방정식 : x2+y2=r2  이제 원의 방정식을 사용해서 1사분면에 있는 두 원의 사이의 점들을 구해주면 ..
[ 백준 ] 1655 가운데를 말해요 (python) https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 백준이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 백준이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 💡 접근 방법 맨 처음엔 쉽게 생각해서 빈 리스트 arr을 만들어 값을 하나씩 append 해주고, 그때마다 sort()를 해주면서 중간값을 찾는 방법으로 구현하였다 -> 골드2 문제였고..당연히 시간 초과🙄 풀이 방법을 고민해봤는데 어떻게 우선순위 큐를 사용해서 이 문제를 풀어야 하는지 감이 잡히지 않았다 그래서 다른 사람들의 풀이를 참고해 문제를 풀어냈다. 1️⃣ 이 문제를 풀..
[ 백준 ] 1941 소문난 칠공주 (python) https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 💡 접근 방법 7명의 여학생이 구성되어야 하는 경우의 수를 구하는 문제였기 때문에 백트래킹을 사용해서 문제를 풀어보려고 했다. 기본적인 백트래킹은 이 경우가 포함될 때, 포함되지 않을 때를 고려해서 재귀 함수로 확인을 해야하는데 여기에 상, 하, 좌, 우가 인접해있는 경우 인지도 함께 고려해야 해서 너무 어려웠다. 지금까지 풀어왔던 알고리즘 문제들을 생각하면, 인접해있는 좌표를 구할 땐 BFS를 사용..
[ 백준 ] 11967 불켜기 (python) https://www.acmicpc.net/problem/11967 11967번: 불켜기 (1, 1)방에 있는 스위치로 (1, 2)방과 (1, 3)방의 불을 켤 수 있다. 그리고 (1, 3)으로 걸어가서 (2, 1)방의 불을 켤 수 있다. (2, 1)방에서는 다시 (2, 2)방의 불을 켤 수 있다. (2, 3)방은 어두워서 갈 수 없으 www.acmicpc.net 💡 접근 방법 처음 문제를 보고 단순히 BFS를 사용해서 풀면 되겠다! 라고 생각했다. 그래서 주어진 (x, y) 방에서 (a, b)방 불 켤 수 있는 좌표들도 가볍게 list를 만들어 받아줬다. 이 과정에서 첫번째 오류 발생! 문제에서 주어진 방 하나에 여러 스위치가 있을 수 있다는 것이었다..😱 예제를 보고 얘기해보자면, (1, 1) 방에선..
[ 백준 ] 1719 택배 (python) https://www.acmicpc.net/problem/1719 1719번: 택배 명우기업은 2008년부터 택배 사업을 새로이 시작하기로 하였다. 우선 택배 화물을 모아서 처리하는 집하장을 몇 개 마련했지만, 택배 화물이 각 집하장들 사이를 오갈 때 어떤 경로를 거쳐야 하 www.acmicpc.net 💡 접근 방법 문제에서 주어진 그래프만 보고 바로 플로이드 워셜 풀이법을 생각해냈다. 💖 플로이드 워셜 플로이드 워셜이란 모든 노드에서 다른 모든 노드까지의 최단 거리를 계산하는 알고리즘으로 a에서 b까지 가는 최단경로를 찾을 때, min(a -> b까지의 거리, a -> k + k -> b까지의 거리) 값을 구해 최단경로로 설정해주면 된다. 즉, 수식으로 나타내면 아래와 같다. 다익스트라 알고리즘처럼 단..
[ 백준 ] 1477 휴게소 세우기 (python) https://www.acmicpc.net/problem/1477 1477번: 휴게소 세우기 첫째 줄에 현재 휴게소의 개수 N, 더 지으려고 하는 휴게소의 개수 M, 고속도로의 길이 L이 주어진다. 둘째 줄에 현재 휴게소의 위치가 공백을 사이에 두고 주어진다. www.acmicpc.net 💡 접근 방법 1477번 문제를 풀면서 어려웠던 점 3가지 1️⃣ 문제를 보고 범위가 그렇게 크지 않다고 생각해서 이분 탐색 문제라고 생각하지 못했다. (아래의 문제 분류와 최소값의 범위를 줄여가면서 풀어야 하는 것 때문에 이분 탐색으로 접근했다.) 2️⃣ 문제 내용 중 '휴게소가 없는 구간의 최댓값의 최솟값을 출력한다.' 라는 말을 제대로 이해하지 못했다. 3️⃣ 2번에서 이어지는 내용으로, 최댓값 중 최솟값을 찾는 ..
[ 프로그래머스 ] 다리를 지나는 트럭 (Python, 파이썬) https://school.programmers.co.kr/learn/courses/30/lessons/42583 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💕풀이 방법 처음 문제를 접하고, 문제가 잘 이해가 되지 않았다. 특히 예제에서 보여준 trucks_weight = [7, 4, 5, 6] 트럭들이 차례대로 다리를 지나가는데 처음 무게가 7인 트럭이 다리를 지날 때 2초가 소요되는 건지 이해가 되질 않았다. 그래서 이미 문제를 해결한 다른 사람들의 후기를 찾아봤더니 bridge_length는 다리 길이가 2라는 뜻이고, 트럭이 1만큼 이동할때 1..

티스토리툴바