본문 바로가기

분류 전체보기172

[백준] 13414 - 수강신청 by C++ https://www.acmicpc.net/problem/13414 13414번: 수강신청 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 과목의 수강 가능 인원 K(1 ≤ K ≤ 100,000)와 학생들이 버튼을 클릭한 순서를 기록한 대기목 www.acmicpc.net 어려운 문제라기보다는 map을 사용하는데 익숙하지 않다보니, map을 이해하고 적응하는 과정인 것 같다. 알고리즘 방식 map 을 사용하여, key : 학번, value : 누른 순서 로 저장하였다. 위와 같이 저장함으로 써, 중복하여 누를 경우, 누른 순서가 최후의 순서로 갱신된다. 이후, map을 vector로 변환하여, 누른 순서를 기준으로 오름차순으로 정렬 후, 수강 가능 인원.. 2023. 6. 14.
[백준] 1261 - 알고스팟 by C++ https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 처음에 메모이제이션을 활용한 dp를 생각했는데, 결국에는 시간초과가 났다. 구글링 결과 다익스트라 방식이라는 힌트를 얻고 이를 생각해서 코드로 구현했다. 알고리즘 방식 다익스트라 방식을 사용하였고, 각 격자의 하나의 노드 그리고 인접한 격자들을 간선으로 간주하여 구현하였다. 소스코드 #include #include #include #include #include #includ.. 2023. 3. 24.
그리디 알고리즘 지금 가장 최적인 답을 근시안적으로 택하는 알고리즘 = 관찰을 통해 탐색 범위를 줄이는 알고리즘 이상적인 풀이 흐름 관찰을 통해 탐색 범위를 줄이는 방법 탐색 범위를 줄여도 올바른 결과를 낸다는 사실을 수학적으로 증명 (실제 코테에서는 수학적 증명이 사실상 불가) 구현해서 문제를 통과 코딩 테스트에서의 추천 전략 거의 똑같은 문제를 풀어봤거나 간단한 문제여서 나의 그리디 풀이를 확신! ⇒ 짜서 제출해보고 틀리면 빠르게 손절 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.

티스토리툴바