본문 바로가기

MegabyteSchool13

그리디 알고리즘 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘 이상적인 풀이 흐름 관찰을 통해 탐색 범위를 줄이는 방법 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명 (실제 코테에서는 수학적 증명이 사실상 불가) 구현해서 문제를 통과 코딩 테스트에서의 추천 전략 거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 확신! ⇒ 짜서 제출해보고 틀리면 빠르게 손절 100%확신은 없지만 맞는 것 같은 그리드 풀이를 찾았다. ⇒ 일단은 넘어가고 다른 문제를 풀게 없거나 종료가 20-40분 남은 시점에 시작 ⇒ 코테에 그렇게 잘 나오는 문제는 아니다. 11047 - 동전 1931 - 회의실배정 t 이후에 회의 A와 B를 선택하는 경우에서 회의 B를 .. 2023. 2. 17.
[미완] Spring에서 url-pattern은 뭘까 Server 실행 시, localhost:8080/admin/init을 통해 init() 메서드에 접근할 것 을 기대 1. 위 : controller 아래 : web.xml localhost:8080/admin/admin/init 입력 시 init() 메서드에 접근 가능 2. @Request Mapping("/admin")을 @WebServlet("/admin")으로 수정 localhost:8080/admin/init 을 통해 init() 메서드에 접근 가능 3. 1을 2를 통해 해결했다라고 생각할 수 있지만, 문제가 있다. 위는 servlet-context(admin-context.xml로 수정해서 사용했음) 일부인데, resource mapping을 통해 css와 js폴더에 접근하지 못한다. 확인 결.. 2023. 2. 3.
[백준] 23564 - 재귀 문자열 by C++ https://www.acmicpc.net/problem/23564 23564번: 재귀 문자열 $(c, \{7\}), (cc, \{1,3\}), (ccc, \{1,1,1\})$ 등이 모두 정답이다. www.acmicpc.net 최근들어 제일 오래걸린 문제였다.... 오늘따라 머리가 안굴러가긴했는데, 그렇다보니 잘못된 방식 고집하면서 날린 시간도 너무 길었다. 아닌 것 같으면 다른 방식 생각해보는 습관도 가지자.... 알고리즘 방식 X1 = s1...s1 X2 = [s1...s1]s2...[s1...s1] X3 = {[s1...s1]s2...[s1...s1]}s3{[s1...s1]s2...[s1...s1]} X1, X2, X3를 각각 풀어서 작성하면 위와 같다. 이를 기반으로 X3를 통해 S, A 집합을 .. 2023. 1. 27.
[백준] 11265 - 끝나지 않는 파티 https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net 알고리즘 방식 플로이드 워셜 방식으로 구현이 가능한 알고리즘이며 다익스트라를 활용해도 구현이 가능한 알고리즘이였다. 먼저 정점의 개수는 V, 간선의 개수는 E이며, V^2 >= E가 성립한다. 다익스트라의 경우 시간복잡도는 O(ElogV)이다. 플로이드 워셜의 경우 시간복잡도는 O(E^3)이다. 다익스트라를 활용한 풀이의 경우 기본 다익스트라 알고리즘에 for문.. 2023. 1. 20.
[백준] 1520 - 내리막 길 https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 알고리즘 방식 DFS를 활용한 DP 방식이였다. 코드를 보면 DP배열을 모두 -1로 초기화하는 부분이 있는데, 이 부분이 핵심이다. 먼저 dp배열의 값은 해당 위치에서 도착지점에 도달할 수 있는 경우의 수이다. 따라서 특정 위치가 0이라면, 해당 위치에서 도착지점에 도달할 수 있는 경우는 0이라는 의미다. 이는 즉, 해당 위치에서 도착 지점에 도달할 수 있는지를 이미 탐색을 했다라는 의미도 된다.. 2023. 1. 9.
[백준] 18870 - 좌표 압축 https://www.acmicpc.net/problem/18870 18870번: 좌표 압축 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다. Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다. X1, X2, ..., XN에 좌 www.acmicpc.net 알고리즘 방식 간단히 예제를 통해 생각하면, [2, 4, -10, 4, -9] 내림차순 정렬과 중복 제거 후 전체 크기에서 현재 인덱스의 값을 빼주면 해당 인덱스의 좌표 압축 결과였다. 중복 제거는 헤더의 unique 함수를 통해 O(N)으로 구현할 수 있다. (unique 함수는 중복 제거된 벡터의 마지막 값을 iterator로 반환한다.) 따라.. 2022. 12. 30.

티스토리툴바