뜬금없는 부산대학교 프로그래밍 경진대회 후기

알고리즘 문제를 해결하는 Problem Solving을 다루는 갤러리입니다.

매니저

캐티(tae826)

부매니저

부재중입니다.(ailedear) Gravekper(gravekpe…) 옥토끼(moonrabb…) 나는최고(mebest)

개설일

2018-05-28

[일기] 뜬금없는 부산대학교 프로그래밍 경진대회 후기앱에서 작성

행복을좇아

2024.05.15 15:37:52

조회 552 추천 7 댓글 1

문제들 질이 좋아서 너무 재밌는 시간이었어요. 몇몇 개는 에디토리얼을 봐서 슬프긴 했지만 오랜만에 Manacher 알고리즘도 보고 즐거웠답니다. 역시 부산은 최고의? 도시에요.

7cea8173b2876df63aed82e3459f34337bffd475e61dcf4dbc00b9c8

A번(모험의 시작) : 그냥 for문 돌면서 가진 돈으로 살 수 있고 후안보다 공격력이 높은 무기가 있는지 확인해주면 되네요.

풀이 : http://boj.kr/2c69385d9f534908b001997432480e61

B번(아~파트 아파트) : 저는 deque 자료 구조를 이용해서 맨 뒤에 있는 애를 빼서 맨 앞에 넣어주는 연산을 구현했어요. 정렬한 다음에 작은 얘부터 차례대로 deque에 넣어줬고요.

풀이 : http://boj.kr/59cb77c7a9d5432da4d1bb6855ebf59f

C번, F번(한빛 미디어) : 저는 multiset 자료구조를 이용해서 구현해줬고 가장 작은 것부터 시작해서 가격이 2배 이상이 되는 책을 lower_bound method를 이용해 찾아가면서 끝에 도달할 때까지 필요한 페이지의 개수를 구해줬어요.

풀이 : http://boj.kr/eea0f3feaf404cd8bb1493db538d6098

D번(간단한 문제) : 간단한데 간단한 문제가 아니네요. 에디토리얼을 보면서 풀었고 발상은 어려운데 구현은 간단한 문제였어요. 에디토리얼 그대로 옮긴 코드라서 풀이는 생략할게요.

E번(바이러스 공격) : 저는 queue 자료 구조를 배열로 만들어서 BFS 돌리면서 풀어줬어요. i번째 시간에는 i번째 큐에서 뽑아서 BFS를 돌리도록 한다면 건물에서 바이러스 전파가 지연되는 것을 비교적 간단하게 처리할 수 있어요.

풀이 : http://boj.kr/a86db577ca394a949d3d1ca44f848b41

G번(공 굴리기) : 이것도 에디토리얼 보면서 풀어서 넘길게요. 간단한 재귀함수로 구현이 가능하긴 하더라고요.

H번(V. I. P) : dp1(i) := i번째 정점에서 시작하는 경로의 개수, dp2(i) := i번쨰 정점에서 끝나는 경로의 개수로 정의해주면 O(N)으로 동적 계획법을 이용해서 전처리를 해줄 수 있고 각 쿼리마다 O(1)에 답할 수 있어요.

풀이 : http://boj.kr/61c51b1000174545ac48a7d9bcc91c54

i번(두유노팰린드롬?) : 백 만년만에 Manacher 알고리즘 쓰는 문제를 봐서 반가왔어요. Manacher 알고리즘을 이용해서 각 문자마다 최장 palindrome의 반지름을 전처리해두고 imos법을 활용해주면 시간 제한 내에 통과할 수 있답니다.

풀이 :

http://boj.kr/76541939fa454f8f9243ee309e132c13

다들 좋은 하루 보내세요:)

- dc official App

고정닉 1

원본 첨부파일 1

1715755042463.png

전체 댓글 0개

등록순

본문 보기

타인의 권리를 침해하거나 명예를 훼손하는 댓글은 운영원칙 및 관련 법률에 제재를 받을 수 있습니다.
Shift+Enter 키를 동시에 누르면 줄바꿈이 됩니다.

갤러리 리스트
번호	말머리	제목	글쓴이	작성일	조회	추천
2864	설문	비난 여론에도 뻔뻔하게 잘 살 것 같은 스타는?	운영자	24/06/03	-	-
44906	공지	피갤컵 call for tasks를 진행합니다! [7]	*나는최고*	24.05.22	703	16
44466	공지	[ps 정보글 모음집] [2]	*나는최고*	24.05.07	797	12
44058	공지	알고리즘 대회 공부 과정 [22]	*나는최고*	24.04.20	2430	31
19170	공지	규칙 v2022.02.16 [8]	*0xrgb*	22.02.06	6798	36
1	공지	와 PS! [24]	*0xrgb*	18.05.28	21848	30
45309	일기	E 풀이가 대충 나오자마자 전의 상실함 [6]	EN_SA	01:45	35	0
45308	일반	구현 셋인듯	ㅇㅇ(49.165)	01:39	26	0
45307	일반	D 왤케 많이 풀렸냐 [5]	ㅇㅇ(211.184)	01:35	55	0
45304	일반	백준 랜덤 마라톤 근황 [1]	ㅇㅇ(112.217)	06.06	175	1
45303	일반	실무에서 제일 많이 쓰이는 알고리즘이 뭐임?? [22]	ㅇㅇ(211.234)	06.06	400	0
45302	일반	자구뉴비인데 이거 왜캐 재밌죠 [9]	ㅇㅇ(118.235)	06.06	211	0
45301	일반	DP 씨발년아	ㅇㅇ(223.62)	06.06	129	2
45300	풀이	코린이C, 시간제한 도와줘 [2]	코린이(218.235)	06.06	140	0
45299	일반	백준 스트릭 이은 기억 [4]	ㅇㅇ(211.234)	06.06	216	1
45298	일반	갑자기 클래스 따짐;;	dpk	06.06	160	1
45297	일반	실버 1 DP문제를 한번에 푸는 정도의 능력 [3]	ㅇㅇ(123.214)	06.06	300	14
45295	일반	끄앙 티어 떨어졌다 [6]	진막	06.06	341	2
45294	일반	IT쪽 일안하고 PS하는 사람있냐 [6]	ㅇㅇ(218.48)	06.06	314	0
45293	일반	1학년인데 알고리즘 대회 때문에 언어 고민중임 [14]	ㅇㅇ(59.29)	06.06	346	0
45291	일반	마라톤 문제 이거맞음...? [5]	투투♡	06.06	351	13
45288	일반	[피갤컵] call for tasks 재공지 [2]	나는최고	06.06	423	21
45287	일반	마라톤 겨우 다 밀었다 [1]	노는게제일좋아	06.06	288	0
45286	일반	밑글보고 평소 생각 말해보자면 [35]	ㅇㅇ	06.05	542	1
45285	일반	(나무위키) 다익스트라의 INF에 대해 질문 있습니다. [12]	ㅇㅇ(211.234)	06.05	415	0
45284	일반	니들 궁국적인 목표가 취업인거임? [14]	ㅇㅇㅇㅇ(221.144)	06.05	396	0
45283	일반	찐 늒네 마라톤 [1]	ㅇㅇ(220.93)	06.05	215	1
45282	일기	님들 근데 마라톤만 있는게 아님 [3]	EN_SA	06.05	315	8
45281	일반	랜덤 마라톤을 하는 피붕이들 모습 [2]	ㅇㅇ(218.52)	06.05	373	12
45280	일반	마라톤 좋네 [2]	ㅇㅇ(61.101)	06.05	247	4
45279	일반	랜마 브1에서 트라이나와서 당황했네 [1]	ㅇㅇ(106.101)	06.05	217	0
45278	일반	c++ 초고수만 [15]	ㅇㅇ(218.153)	06.05	310	0
45277	일반	늒네 마라톤 다했다 [2]	ㅇㅇ(182.215)	06.05	296	5
45276	일반	자랑 좀 하겠습니다 [11]	biximo	06.05	500	16
45275	일반	백준 다익스트라 문제 정답 비율 왜 이렇게 되는거임? [7]	ㅇㅇ(183.98)	06.05	326	0
45274	일반	solved질문좀요 ㅠㅠ	ㅇㅇ(223.39)	06.05	124	0
45273	질문	피붕이 뉴비인데 [2]	dd(210.104)	06.05	174	0
45272	일반	45살인데 코딩 시작하려 합니다. [13]	ㅇㅇ(223.62)	06.05	610	27
45271	일반	ps파다가 취직못해서 알고리즘 대학원 가는 경우잇냐 [6]	ㅇㅇ(211.36)	06.05	367	0
45270	구인	경비일 구했다 [2]	ㅇㅇ(218.48)	06.05	198	0
45269	일기	마라톤 [3]	Bubbler	06.05	328	3
45268	일반	카이 전산 어떰 [7]	히츠비르	06.05	308	0
45267	풀이	BOJ 28495 Topical [2]	ㅇㅇ(218.235)	06.05	188	1
45266	일반	이분탐색을 모르겠다 [3]	ㅇㅇ(112.217)	06.05	197	0
45265	일반	스트릭에 인생 팔아먹은게 자랑 [3]	ㅇㅇ(112.160)	06.05	307	7
45263	일반	골랜디 시키네 [9]	EN_SA	06.05	462	10
45262	일반	솔브닥 마라톤 다들 어떻게 뜸? [4]	rich-chanel	06.05	402	0
45261	일반	내가 누구? [2]	rich-chanel	06.05	285	13
45259	일반	dp 몇 문제쯤 풀어야 감옴? [3]	ㅇㅇ(123.214)	06.05	225	0
45258	일반	Solved ac 시즌바뀌면 티어 초기화임? [5]	ㅇㅇ(223.39)	06.05	349	0
45257	일반	플레 언제쯤 해볼까....? [3]	ㅇㅇ(223.33)	06.05	243	0
45256	일반	자료구조 좀 더 파보려는데	ㅇㅇ(211.234)	06.05	126	0
45255	일반	컴공이 좆망인건 틀린소리는아닌데 [4]	ㅇㅇ(106.101)	06.04	449	0
45254	일반	공익 활동하면서 PS 문제 푸는데 [1]	ㅇㅇ(114.202)	06.04	233	0
45252	일반	막차 탔냐?	rich-chanel	06.04	360	12
45251	질문	출제자도 못 푸는 문제를 내는 대회 등이 있나여? [9]	ㅇㅇ	06.04	364	0