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

PS 갤러리
마이너

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

매니저

캐티(tae826)

부매니저

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

개설일

2018-05-28

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

행복을좇아

2024.05.15 15:37:52

조회 551 추천 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	691	16
44466	공지	[ps 정보글 모음집] [2]	*나는최고*	24.05.07	779	12
44058	공지	알고리즘 대회 공부 과정 [22]	*나는최고*	24.04.20	2392	31
19170	공지	규칙 v2022.02.16 [8]	*0xrgb*	22.02.06	6792	36
1	공지	와 PS! [24]	*0xrgb*	18.05.28	21840	30
45263	일반	골랜디 시키네	EN_SA	07:35	133	3
45262	일반	솔브닥 마라톤 다들 어떻게 뜸? [1]	rich-chanel	06:13	162	0
45261	일반	내가 누구? [1]	rich-chanel	06:09	132	5
45259	일반	dp 몇 문제쯤 풀어야 감옴? [1]	ㅇㅇ(123.214)	03:29	109	0
45258	일반	Solved ac 시즌바뀌면 티어 초기화임? [5]	ㅇㅇ(223.39)	01:26	207	0
45257	일반	플레 언제쯤 해볼까....? [3]	ㅇㅇ(223.33)	00:16	158	0
45256	일반	자료구조 좀 더 파보려는데	ㅇㅇ(211.234)	00:09	82	0
45255	일반	컴공이 좆망인건 틀린소리는아닌데 [3]	ㅇㅇ(106.101)	06.04	303	0
45254	일반	공익 활동하면서 PS 문제 푸는데	ㅇㅇ(114.202)	06.04	153	0
45253	일반	컴공 ㄹㅇ ㅈ망인데 [15]	ㅇㅇ(211.234)	06.04	410	0
45252	일반	막차 탔냐?	rich-chanel	06.04	284	11
45251	질문	출제자도 못 푸는 문제를 내는 대회 등이 있나여? [9]	ㅇㅇ	06.04	269	0
45250	일반	비트마스킹 << 이거 공부 대체 어케 해야함? [7]	ㅇㅇ(58.237)	06.04	229	0
45249	일반	코드포스 레이팅과 무공 레벨 [11]	코드포스(118.235)	06.04	388	11
45248	일반	파이썬 넘파이는 아주 빠르다 [3]	ㅇㅇ(106.241)	06.04	235	0
45246	일반	C++ 파이썬 동시 능력자있음? [11]	ㅇㅇ(211.36)	06.04	348	0
45245	일반	여기서 말하는 디코가 어디임? [8]	ㅇㅇ(223.39)	06.04	394	0
45244	일반	소수 문제 풀다가 리만가설에 근접했는지 [5]	ㅇㅇ(223.38)	06.04	310	0
45243	일반	C 핵 따잇 [2]	ㅇㅇ(175.215)	06.04	181	0
45242	일반	SCPC 떴냐 [6]	EN_SA	06.04	413	0
45241	일반	scpc 수상 할만함? [5]	ㅇㅇ(163.152)	06.04	305	0
45240	일반	dp랑 그래프 문제는 뭔가 감각을 익혀야하는 느낌인데 맞음? [1]	ㅇㅇ(183.98)	06.04	155	0
45239	일반	for else << 이거는 반복문이냐 조건문이냐? [4]	ㅇㅇ(39.127)	06.04	243	1
45237	일반	ps 할때마다 배 ㅈㄴ 아픔 [4]	ㅇㅇ(117.111)	06.04	273	0
45236	일반	구현 잘하는건 구현 많이하기 말고 답 없겠지? [1]	ㅇㅇ(106.101)	06.04	89	0
45235	일반	5+ 찍음 [1]	ㅁㄴㅇㄹ(106.101)	06.04	193	5
45234	일반	gradient 구하는거 행렬곱이다 아님? [9]	ㅇㅇ(118.176)	06.04	305	0
45233	일반	c++ 해본적 없으면 [1]	ㅇㅇ(112.133)	06.04	144	0
45232	일반	실버2 뉴비인데 [2]	ㅇㅇ(211.195)	06.04	108	0
45231	일반	f1 누가 힌트 좀 [5]	ㅇㅇ(220.92)	06.04	142	0
45230	일반	대회 끝난거 같은데 왜 코포 안들어가짐? [2]	ㅇㅇ(61.101)	06.04	128	0
45229	일반	D 힌트 좀... [10]	ㅇㅇ(220.76)	06.04	205	0
45228	일반	G어케품? [13]	ㅇㅇ(182.231)	06.04	181	0
45226	일반	딥러닝쪽에서 행렬곱 이런거 많이 쓸 텐데 [13]	ㅇㅇ(118.176)	06.04	326	1
45225	일반	브루트포스 진화 : 백트래킹 [4]	ㅇㅇ(123.214)	06.03	181	1
45223	일반	디코도 진짜 ㅈ됐나보다 [9]	ㅇㅇ(119.207)	06.03	564	16
45222	일반	코테만 보면 뇌가 멈춘다 [1]	ㅇㅇ(116.39)	06.03	176	0
45220	일반	수학 좋아하는 애들은 첫눈에 문제 안풀리면 좋아함 [2]	ㅇㅇ(116.39)	06.03	345	6
45219	일반	학교에서 만들었는데 ㅁㅌㅊ? [7]	ㅇㅇ(118.235)	06.03	488	14
45218	일반	코딩 이제 시작한 고1 공부조언 해주세요 [9]	ㅇㅇ(118.221)	06.03	292	0
45217	일반	코포 블루 목표면 [7]	ㅇㅇ(117.111)	06.03	288	2
45215	일반	BOJ 랜디 망캐되서 슬프다 [5]	ainta(112.169)	06.03	435	9
45213	일반	고인물님들.. 혹시 취업용 코테문제집 따로 추천 없나요? [6]	1515(119.56)	06.03	294	1
45212	일반	형들 저 대학 이따구로 다녀도 괜찮은건가요? [12]	ㅇㅇ(211.235)	06.03	389	1
45211	일반	물리학과 학부생.. ps 재밌어서 2개월만에 실3-> 골4 등극 [6]	ㅇㅇ(223.39)	06.03	343	4
45210	일반	ps 뒤늦게 입문했는데 그냥 많이 풀면 되나요 [6]	똑단발	06.03	316	0
45209	일반	어우 실골 구간 들어가니까 정답률 씹창나네 [1]	개허접임	06.03	215	1
45208	일반	c++ 관련 블로그 신고함. [15]	ㅇㅇ(125.209)	06.03	594	2
45206	일반	오렌지는 플5랜디 시간안에 해야할정도가 되야는건가 [9]	개드립퍼	06.03	400	0
45205	일반	갑자기 솔브닥 안되는 것 같음 [2]	ㅇㅇ(211.234)	06.03	300	0