오전

인천공항

8시 35분 비행기로 6시 30분 언저리에는 도착하게 가는 것이 좋아 보인다.

다카마쓰 도착

10시 도착 예정이고, 다카마쓰 리무진 버스가 10시 40분 리무진을 타고, 11시 20분 도착으로 가는 것이 현실적이다.

리가 호텔 제스트 타카마츠

11시 30분 도착 후 호텔에 짐을 맡길 예정입니다.

점심

수타우동 후게츠

우동을 섭취한 후 다카마쓰 역을 향해서 이동

오후

다카마쓰 성터(다마모 공원)

점심 후 짧게 관광 후 바로 옆의 다카마쓰 역에서 바우처를 교환

리츠린 공원

쓰킨 돗큐 버스를 타고 12분 정도 이동(티켓 사용하면 바로 갈 듯) 내부에서 즐길 거리는 많을 것으로 생각이 됨 적당히 보고 컴백하면 될듯

마루가메마치 상점가

여기가 호텔 옆에 있는 상점가인데 여러가지 많다고 해서 쇼핑하는 계획으로 감 위의 사진처럼 되어 있고, 이 곳에서 살만한 것들 리스트를 좀 적어주자면

고급 식빵 전문점 "노가미"

줄 서서 구입하는 곳이고 솔드아웃도 엄청 된다고 함.

신발

뉴발은 화실히 국내보다 쌈

다이소

뭐 알지?

Naniwa

타코야끼 파는 곳... 꼭 가고 싶다...

저녁

호네츠키도리 잇카쿠 타카마츠점

기다릴 거 같긴 한데 이거 먹고 싶고, 안되면 다른 닭집 가야지 뭐...

08.09

오전

기상

대충 7시 30분 기상해서 9시까지 항구로 가보려고 합니다. 8시반에 호텔 앞에서 나와서 가면 대애가앙 시간 맞음 9시에 토노쇼항으로 가는 페리가 있으니 이걸 타면 될듯

토노쇼 항

올리브 공원으로 가는 버스를 타고 이동(35분 소요)

올리브 공원

10시 30분 도착해서 한 시간 정도 주변 보고

Koyomi

코요미라는 식당 앞에 방문 예정 11시반 예약 입니다.

TODAY IS THE DAY

바다 앞 카페라는데 시간이 허락한다면 가볼까 생각중임

오후

간카케이

올리브 공원에서 20분 정도 가서 나오는 곳, 풍경이 정말 정말 좋다고 함 케이블 카 타고 올라가면 됨. 다만, 날씨가 안 좋으면 패스하래.

엔젤로드

간카케이에서 1시간 30분은 걸리는 거리여서 간카케이에서 3시 반 전에는 내려와야 할듯(5시에 엔젤로드를 보기 위해서)

저녁

Shimakatsu

예약 해놓을 계획입니다. 예약 시간은 7시로 해두었습니다.

08.10

오전

기상

기차 시간을 8시 55분 기차라 전날이랑 비슷하게 일어나서 가면 될 듯

오카야마

대충 10시쯤 도착해서 10시 반까지 고라쿠엔으로 이동

고라쿠엔

대충 구석구석 보면 1시간 반 정도 걸린다고 해. 일본 3대 정원으로 유명하고 규모도 크더라고.

Megu Shabu-shabu & Sukiyaki

점심을 여기서 먹고

카페 모야우

여기서 한 시간 정도 시간을 떼우면 어떨까 싶음. 여기를 안 가면 오카야마 성이나 뭐 가볼만한 현립 미술관이나 엄청 많음

오후

구라시키 미관지구

2시쯤 출발하면 2시반쯤 도착해서 여기가 되게 살짝 옛 스러운 마을 느낌이라 쭉 둘러보면 될 듯

오하라 미술관

구경하기 괜찮은듯

오카야마 이온몰

오카야마로 돌아와서 바로 옆의 오카야마 이온몰이 엄청 유명해서 여기서 좀 쇼핑하다가

저녁

Teppan Ku-Ya okayama

8시반으로 예약 완료...

다카마쓰로 컴백

오후 10시 기차를 타고 돌아오면 대충 밤 11시임ㅋㅋ

08.11

집 가기 바쁠 듯

권장 사항

히로시마 24시간 전철 + 페리

첫 날은 몰라도 둘째 날은 무조건 사용해야 하니 구매하는 걸 추천한다. 사이트 접속 링크는 여기이다. 구매할 시 옵션에서 무조건 Ropeway 할인 쿠폰을 받자. 투어리스트 패스가 아니라 전철 + 페리를 사야한다. 이걸 안 사면 Ropeway 할인이 안되어서 손해다. 미리 구입해둬라 모두들

히로시마 공항 버스 리무진 예약권

왕복으로 2620엔짜리 구매하면 그래도 300엔 정도 아낄 수 있다. 이것까지 구매하면 사실상 스이카(교통카드)가 필요 없는 수준이기 때문에 구매를 추천한다. 위의 사이트에서 동일하게 구매할 수 있다.

환전 금액

뉴발 신발이 매우 싸서 구매할거라면 많이 들고 오고 아니라면 3만엔이면 뒤집어 쓸 것으로 예상이 된다.

기념품

미야지마섬(이쓰쿠시마 신사)에 무슨 젓가락 파는데 있는데 사실 그냥 기념품 살 건 딱히 없는 듯. 공항에서 우메슈 파는데 그거 사가는건 괜찮. 집에 놔두고 탄산수에 섞어 마시면 이게 또 기가막힘

신발

편한거 신고 오세요... 편한거 아니면 죽어요. 진짜 편한거... 편한거.. 편한거.

방사능 걱정되면 보면 되는 글(GPT)

히로시마의 방사능에 대해 걱정하시는 것은 이해할 수 있습니다. 그러나 현재 히로시마는 방사능 문제로부터 안전하다고 알려져 있습니다. 이를 이해하기 위해 몇 가지 중요한 점을 설명드리겠습니다.

먼저, 히로시마는 제2차 세계 대전 중 1945년에 원자 폭탄 공격을 받았습니다. 당시에는 방사능 오염이 있었으나, 시간이 지나면서 방사능 수준이 급격히 감소했습니다. 방사능 물질의 반감기와 자연적인 환경 복원 과정을 통해 현재 히로시마의 방사능 수준은 일반적인 자연 방사능 수준과 크게 다르지 않습니다.

현재 히로시마는 방사능 측면에서 국제적으로 인정된 안전 기준을 충족하고 있습니다. 일본 정부와 국제 기구들은 지속적으로 방사능 수준을 모니터링하고 있습니다. 예를 들어, 일본의 원자력 규제위원회(Nuclear Regulation Authority, NRA)와 국제 원자력 기구(International Atomic Energy Agency, IAEA)는 히로시마의 방사능 수준을 주기적으로 검사하고 있으며, 안전한 수준임을 확인하고 있습니다.

또한, 히로시마는 일본의 주요 관광지 중 하나로, 매년 많은 관광객이 방문하고 있습니다. 히로시마 평화 기념 공원과 원폭 돔은 세계 유산으로 지정되어 있으며, 많은 사람들이 평화를 기원하며 이곳을 찾고 있습니다. 지역 주민들도 일상 생활을 안전하게 영위하고 있으며, 건강 문제나 방사능 관련 문제가 보고된 바 없습니다.

2016년 미국의 오바마 전 대통령이 히로시마를 방문했을 때도 방사능 문제에 대한 우려 없이 방문을 진행하였으며, 이는 히로시마의 현재 안전성을 국제적으로 인정받은 사례 중 하나입니다.

사올만한 물건 추천

주류

사쿠라오 진

히로시마에 위치하는 증류소에서 나오는 진으로 공항에서 판매하고 있으면 면세로 구매하기 적당함. 가격은 3000엔 미만이면 구매하기 그냥저냥 괜찮음

가모츠루 다이긴죠 골드

히로시마에서 유명한 술이고 병이 이뻐서 선물용으로 자주 구매한다고 함. 가격은 3000엔 미만이면 구매하기 그냥저냥 괜찮음!

아사쿠라

보리소주인데 있기만 하면 정말 추천 많이 한다는 보리소주다. 다만, 도수가 40도여서 조금 높다. 가격은 3250엔

우메슈

말해 뭐하냐 섞어 마시기 너무 좋다. 강추한다.

기타

므네모시네 노트

호텔 옆 쪽 서점에 파는데 종이 질이 정말 좋은 노트이다. 개인적으로 정말 애용하는 노트이다.

7.6

오전

5시 - 6시

택시 타고 인천공항 출발 사근동 팟 - 3인 // 왕십리역 팟 - 3인 소요시간 : 약 1시간 (비용 : 6만 - 7만)

7시 - 10시

인천공항에서 비행기 탑승

10시 - 11시

국제선 정류장에서 10시, 10시 10분 버스 탑승 비용 : 1500엔(충전할 시간 없을 수 있으니 충전 필요한 경우 최대한 빨리 내리기) 한 번에 5000엔을 충전해 놓으면 편리 패스 구매로 해당 안됨

11시 - 12시

호텔 도착 및 짐 맡기고 쇼핑 거리 걸으면서 음식점

대부분 오사카식 오꼬노미야끼를 알텐데 히로시마식 오꼬노미야끼도 엄청 유명해. 보통 이거는 좀 더 재료 본연의 맛들이 잘 살아 있어서 나는 더 맛있었어/

https://maps.app.goo.gl/xr1YG2mp5nqRDW9y5 12시로 예약 완료

오후

1시 - 2시

히로시마성 : 성 자체가 엄청 크지는 않아서 1시간이면 다 봄 점심 먹고 바로 설렁설렁 걸어서 가면 괜찮음 비용 : 350엔 P.S. 히로시마 호국 신사가 있는데 히로시마판 야스쿠니 신사이니 참배는 안 하는걸 추천한다.

• 까마귀가 사는데 저번에 친구 맺음

  2시 - 4시

  슛케이엔 정원 : 여기는 절대절대절대 후회하지 않을 곳이라고 자부할 수 있는게 지금 히로시마 올해만 3번째 가는건데 여기는 거른 적이 없음. 그냥 가면 마음이 편안해져. 여기서는 다같이 다니기 보다 좀 나눠서 다니면 좋을듯 우선 난 따로 다닐거임 저리가 학생증 할인 있음

  옆에 현립 미술관도 있고 시간도 여유가 꽤 있으니 미술관 까지 다녀오고 싶은 사람들은 다녀와도 괜찮고, 여기 옆에 있는 카페에서 녹차 마시면서 시간을 즐기는 것도 좋음

4시 - 5시반

숙소 귀가 및 원폭돔 구경 이 주변에 평화공원도 있어서 편하게 구경하면 될듯

저녁

집 갈 때 이거 해주시는데 이번엔 사진 같이 찍어달라고 하면 좋을 거 같음. 참고로 저 사진은 내가 촬영한거임 ㅋㅋ 시간은 8시로 예약 해둠 꽤 여유 있음

https://maps.app.goo.gl/jQrwagPA3v9pujiG6 예상 비용 : 대략 인당 3000-4000엔(배 터질 시)

1일차 결산

예상 비용 : 6000엔 내외

7.7

오전

8시반 - 10시 50분

기상 및 이쓰쿠시마 신사 이동 9시반에는 나가서 열차를 타야지 괜찮을 듯 한 시간 타야하고, 걍 앉아서 가면 편하니깐 안대 들고 오는거 추천 모자나 모자가 필수같다.

11시 - 12시

음식점은 아래의 굴 요리점을 갈 예정

https://maps.app.goo.gl/GRWv6M47MKZH9ovg9 야키가노 하야시라고 굴 요리 전문점이야. 좀 가격대 있긴 한데 타베로그 기준 3.5가 넘고(전체 시를 기준으로 그런 타베로그 3.5이상이 10개 이럼), 후기가 구글 맵 기준 1600개가 넘어서 믿고 가보려고 함. + 예약이됨 대신 11시 잘 맞춰서 가야할듯 좀 일찍 간단 생각으로 가자. - 다만, 음식 비쌈 생각하고 와야할듯 4000엔 내외

12시 - 1시

이쓰쿠시마 신사 및 그 언저리 사슴들과 산책 사진 스팟 많음 입장료 : 300엔

1시 - 4시

케이블카를 타고 미센산을 등산하는 코스가 있다. 미리 등산을 어느정도 해놔야지만 올라갈 수 있긴 한데 나도 안 가본 코스라 좀 체력이 잘 비축되어 있다면 이걸 가는 것도 좋을 듯! 아래는 등산로 사진

정보 : 아래걸 타는데까지등산 약 20분... 갈아타는 시간 이런거 고려하면 좀 복잡할 거 같아서 시간 넉넉히 잡음 정보 : 30분 더 등산하면 꼭대기 체력 상태를 고려하자...(첨언 : 리뷰를 보면 매우 험난하다는 말이 왜이리 많지...) 조금 비쌈 : 2000엔(투어리스트 패스 구매로 500엔 할인 가능) 장점 : 6인용 케이블카라 우리끼리 타고가면됨 단점 : 30인용 케이블카"도" 타야함(두 개 갈아탐)

5시반 - 6시반

숙소까지 도착. 아마 체력적으로 죽어갈테니 1시간 정도는 쉬면서 7시반 저녁 예약한 거 준비하면 좋을듯 오는 비용 : 750엔(투어리스트 패스 구매로 무료)

저녁

7시반 - 9시

저녁 예약을 해둠

모츠나베집 - 예약 완료 https://maps.app.goo.gl/dD1BrB1wX7NGnCEM7

메뉴 : 3960엔짜리 코스나 3410엔짜리 코스 중 하나를 먹으면 될 듯 (3960엔 짜리가 말 육회가 있는데 진짜 너무 맛있어서 제발요...)

주류 : 무제한 술 코스는 과분한거 같아서 아래의 구로기리시마라는 술을 3025엔에 먹자. 미즈와리로 먹으면 좋을듯

적당히 1차로 음주를 즐기고 나서 2차로 아래의 바를 가자. 사실 이 때부터는 좀 자율적으로 그냥 숙소가서 편의점음식에 먹고 놀자 해도 난 좋을듯 -> 여기서 대충 4500엔 정도 쓸 듯

https://maps.app.goo.gl/PkjiACnSMfVc11fH8 비용 : 2000엔 이내?

2일차 정산

대충 9000엔 내외

7.8

오전

마지막 날 컨디션을 보고 결정해야겠지만 저번에는 첼시베이글을 가서 엄청 사서 냉동해두고 해동해서 먹었는데 한 한달까지는 보관 가능. 아래 감성

https://maps.app.goo.gl/Sfvcpnh4H17nfaxr7

위의 곳 외에도 한 곳 더 갈만해서(여긴 8시 오픈이라 아침 일찍 깨면 여기가서 사갖고 와서 정리해도 좋을듯)

https://maps.app.goo.gl/cUJjdjN6eu3b6B2D6

*점심은 미정으로 두고 돌아다니면서 먹고 싶어지는걸 먹자 이 날은 *

오후 - 나머진 잘 가고 킼킼

1시-2시

사코라오 양조장으로 이동

2시 - 4시

예약 완료

저녁

7시 -

菜づけ百屋中町 https://maps.app.goo.gl/1n5rmarm3juroGv49 저번에 가본 곳

7.9

자율에 맡기려고 함 캬캬

가보고 싶은데 못 가는 곳

Terashini Cafe

약 50년 전통의 카페라고 함. 여행지랑 멀지는 않지만 방문하기에 좋은 경로는 아니라서 아쉽게 뺌

히지야마 공원

히로시마 현대 미술관이 있는 곳인데 산 위에 있다. 에스컬레이터로 산을 올라갈 수 있고, 크진 않지만 꽤 전경도 아름답고 볼 것도 많은 곳 같지만 이쓰쿠시마 신사를 가니 탈락 시켰다.

나카시마

히로시마 유일의 미슐랭 3스타 음식점이다. 가자고 하면 뺨 맞을 거 같아서 아쉬운 마음에 넣어보았다. 근데 슬픈 점은 가고 싶어도 예약도 안된다...

• 일본 도착
• 버스 타고 숙소 도착 (11시)
• 짐 맡기고 iwamoto라는 라멘집 ㄱㄱ

A안

• 마쓰야마 성 구경 (약 15시까지)
• 숙소 컴백 후 짐 정리
• 휴식 하다가 16시 조금 전에 시모나다역 ㄱㄱ
• 17시쯤 도착
• 시모나다역 1시간쯤 구경(?) 후
• Umenohana 식사 경치가 괴에에엥장히 좋다고 함(7시 반 예약)
• 후 귀가 후 자유롭게 놀면 될듯

B안

• 마쓰야마 성 구경(약 15시까지)
• 숙소 컴백 후 짐 정리
• 오래 쉬다가 대충 17시 쯤 설렁 설렁 나와서 쇼핑거리 구경
• 串揚げ 串仙 튀김 꼬치 맛집이래
• 갔다가 저녁에 간단한 술 먹는 곳 주변에 방문해서 망나니처럼 놀기

C안

• 도고가 오전 시간대가 한적하고 좋다고 해서 도고 온천으로 짐만 맡기고 런
• 슬 쉬다가 저녁에 도고 공원 거리 구경
• 저녁에 도고 카이슈 예약 후 방문
• 식사 후 숙소 와서 뒹굴 댕굴

Candeo Hotel Matsuyama Okaido

조식 + 메시지로 고층 달라 요구 나이스

컨텐츠들

가시마 섬

몰루 여기 사슴 산대 사슴 좋아

시모나다역

다겸이가 너무 가고 싶어하지만 여기가 진짜 좀 어려움 아마 여길 간다면 아침 일찍 출발해서 여길 보고 집에 도시로 돌아오는길에 쇼핑하다가 숙소가서 쿨쿨해야할듯... 개인적으로는 여기 갈바에야 고고섬을 갈듯 아니면 사슴섬

潮路

https://maps.app.goo.gl/mt29XacAojaMRoTi9 음식이 신선하고 맛있어 보이고 우선 경치가 돌아버렸어. 시모나다를 간다면 필수이고, 점심만 영업하신대

도고 온천

마쓰야마 지역 메인 컨텐츠라고 봐도 되는 두 개가 도고 공원이랑 도고 온천이라고 생각이 든다. 봇짱 열차도 있고 그냥 여러가지로 즐길게 많은 지역 여긴 어차피 가야해

도고 카이슈

https://maps.app.goo.gl/82TcfYbR6RwMhXC97 오마카세인거 같은데 예약도 되고 가격도 매우 합리적(비싸지만) 이라고 함. 국내에서 25만원대 파인다이닝 급은 되는듯?

마쓰야마성

여기 주변 호텔을 예약해서 하루종일 이 주변에서 맛있는거 먹고 하는게 어떤가 싶음. 밑의 텐 팩토리도 여기 공원이랑 등등 바로 앞에 있고, 아래에 보면 즐길만한 음식이 굉장히 많음 그리고 케이블카 타고 올라가는 경치도 좋은듯. 조금 빡빡하게 본다면 도고온천과는 가까워서 둘 다 같은 날에 즐길 수 있을지도?(비추)

이와모토

https://maps.app.goo.gl/DMG6wGSgcnxDijBZ9 호텔 바로 앞에 있는 도미 라면 집인데. 이 동네 자체가 도미가 특산품 느낌이라 도미밥이 꼭 먹어야 하는 음식 중 하나임 그래서 이 도미 라면도 넣어봄

간스이

https://maps.app.goo.gl/kacuAzzMvfWJ2j7J9 도미 밥으로 꽤나 유명한 집이라고 알아 마찬가지로 호텔과 굉장히 가까운걸로 보아 칸데오 호텔이 진짜 탐이 나기 시작함.

Gosiki

https://maps.app.goo.gl/zfBbKhgXvysucUQA6 걍 가정집 밥 느낌인듯 호텔앞이라 가볼만 해보임

텐 팩토리(디저트)

https://maps.app.goo.gl/MLAk5oq7NXjBuHzPA 여긴 꼭 가라더라

기타 음식점

Umenohana

https://maps.app.goo.gl/dNZ7m5bFWfQi2Qsr5 예약 가능 가이세키 요리정식 판다고 함. 한 번 고급스러운걸 간다면 여길 가보고 싶다.

카츠레츠 테이

https://maps.app.goo.gl/aTqZ63LiA9R78CBTA 돈까스 집이라는데 나름 미슐랭도 받고 그랬다는데 맛은 있대. 주변 상권 대비 좀 비싸대.

• 논문 정리

가중치의 초기값

배치 정규화

바른 학습을 위해

적절한 하이퍼파라미터 값 찾기

계산 그래프는 계산 과정을 그래프로 나타낸 것으로 노드는 계산 결과를 표시하고 화살표는 계산의 순서를 나타낸다. 예를 들어 사과 2개의 가격을 계산하는 경우 덧셈 노드 곱셈 노드를 사용해 그래프로 표현할 수 있다.

5.1.1 계산 그래프로 풀다

계산 그래프로 문제를 푸는 절차는 다음과 같다.

1. 계산 그래프를 구성한다.

2. 그래프에서 계산을 왼쪽에서 오른쪽으로 진행한다.

   5.1.2 국소적 계산

   국소적 계산이란 전체에서 자신과 관련된 정보만으로 결과를 출력할 수 있는 것을 말한다. 최종 결과를 얻기 위해 복잡한 계산이 필요해도 중간 과정의 모든 계산 결과를 기억할 필요는 없다.

   5.1.3 왜 계산 그래프로 푸는가?

   계산 그래프로 푸는 가장 큰 이유로는 역전파를 통해 미분을 효율적으로 계산할 수 있기 때문이다. 머신러닝은 학습할 때 매개변수의 미분을 많이 사용하는데, 계산 그래프를 사용하면 이 미분을 효율적으로 계산할 수 있다.

   5.2 연쇄법칙

   연쇄법칙은 계산 그래프의 원리 이해에 아주 중요한 개념이다. 역전파는 연쇄법칙에 따라 국소적 미분을 순차적으로 전달하는 것이다.

   5.2.1 계산 그래프의 역전파

   계산 그래프의 역전파에서는 각 노드에서 다음 노드로 신호를 전달하는 순전파와 반대 방향의 전파가 일어난다. 이 전파되는 값이 앞 노드의 입력 값에 대한 미분이 된다.

   5.2.2 연쇄법칙이란?

   연쇄법칙은 합성함수의 미분에 대한 성질이다. 합성함수의 미분은 합성 함수를 구성하는 각 함수의 미분의 곱으로 나타낼 수 있다.

   5.2.3 연쇄법칙과 계산 그래프

   계산 그래프의 역전파와 연쇄법칙은 밀접한 관련이 있다. 계산 그래프에서는 국소적 미분을 전달하는데, 여기서 전달되는 값이 연쇄법칙에 따라 계산되기 때문이다.

   5.3 역전파

   덧셈과 곱셈의 경우 역전파는 다음과 같다.

   5.3.1 덧셈 노드의 역전파

   덧셈 노드의 역전파는 입력값을 그대로 다음 노드로 보내면 된다.

   5.3.2 곱셈 노드의 역전파

   곱셈 노드의 역전파는 상류의 값에 순전파때의 입력 신호를 바꾼 값(교환법칙)을 곱한 후 다음으로 보낸다.

   5.3.3 사과 쇼핑의 예

   사과 2개를 구입한다고 할 때 계산 그래프와 역전파를 설명하면 이해하기 쉽다. 덧셈 노드와 곱셈 노드로 이루어지며 역전파를 따라가보면 사과 1개의 가격과 2의 값이 최종 결과에 미치는 영향을 알 수 있다.

   5.4 단순한 계층 구현하기

   계산 그래프의 노드를 하나의 '계층'으로 구현한다. 곱셈 노드의 forward와 backward를 메서드로 구현한 것이 곱셈 계층이라 할 수 있다.

   5.4.1 곱셈 계층

   MulLayer라는 클래스로 곱셈 노드의 forward와 backward를 구현한다.

   5.4.2 덧셈 계층

   AddLayer라는 클래스로 덧셈 노드의 forward와 backward를 구현한다.

   5.5 활성화 함수 계층 구현하기

   활성화 함수로 사용되는 ReLU와 Sigmoid도 계층으로 구현한다.

   5.5.1 ReLU 계층

   ReLU 계층을 forward와 backward 메서드로 구현한다. 순전파 때는 입력값이 0보다 크면 그대로 전달하고, 0이하면 0으로 전달한다. 역전파 때는 순전파의 입력 값이 0보다 크면 상류에서 들어온 값을 그대로 하류로 흘리고 순전파 때 0이하면 0을 하류로 흘린다.

   5.5.2 Sigmoid 계층

   Sigmoid 계층도 forward와 backward를 구현한다. 순전파에서는 sigmoid 함수 출력을 다음 노드로 전달하고, 역전파 때는 상류의 값에 sigmoid의 출력(1-출력)을 곱한 값을 다음 노드로 전달한다.

   5.6 Affine/Softmax 계층 구현하기

   이제 신경망 구성에 필요한 Affine 계층과 Softmax-with-Loss 계층을 구현한다.

   5.6.1 Affine 계층

   Affine 변환을 수행하는 계층을 구현한다. 순전파에서는 X・W+B를 계산하고 역전파에서는 상류에서 온 값에 가중치의 전치행렬을 곱하고 기울기를 출력한다.

   5.6.2 배치용 Affine 계층

   Affine 계층을 배치 처리 할 수 있도록 확장한 계층을 구현한다.

   5.6.3 Softmax-with-Loss 계층

   Softmax 함수와 손실 함수(교차 엔트로피 오차)를 포함한 계층을 구현하여 마지막 출력층으로 사용할 수 있도록 한다. 이 계층을 사용하면 역전파 때 Softmax 계층과 Cross Entropy Error 계층을 개별적으로 구현할 필요가 없어진다.

   5.7 오차역전파법 구현하기

   5.7.1 신경망 학습의 전체 그림

   이제 신경망 학습의 전체 그림을 알아보자. 학습은 다음 4단계의 과정으로 수행된다. 1. 미니배치 2. 기울기 산출 3. 매개변수 갱신 4. 1-3 반복

   5.7.2 오차역전파법을 적용한 신경망 구현하기

   지금까지 구현한 계층을 조합하면 신경망을 쉽게 구현할 수 있다. Affine 계층과 ReLU 계층을 교대로 사용하고 마지막 출력 계층으로 Softmax-with-Loss 계층을 사용한다.

   5.7.3 오차역전파법으로 구한 기울기 검증하기

   수치 미분을 사용해 오차역전파법으로 구한 기울기를 검증한다. 기울기 검증은 오차역전파법의 구현에 버그가 있는지 없는지 확인할 때 유용하다.

   5.7.4 오차역전파법을 사용한 학습 구현하기

   지금까지 구현한 오차역전파법을 사용해 신경망을 학습시켜 본다. 각 매개변수의 기울기는 오차역전파법으로 효율적으로 구할 수 있다. 이 기울기를 사용하여 경사법(SGD)으로 매개변수를 갱신한다.

   이상으로 오차역전파법의 구현 과정을 살펴보았다. 다음 장에서는 학습 관련 기술들을 알아볼 것이다.​​​​​​​​​​​​​​​​

손실함수

오차제곱합(SSE)

E = 1/2 * Σ(t_i - y_i)^2    

간단하게 위의 공식인데 정말 단순하게 t_i가 정답 레이블이고 y_i는 신경망 출력 레이블로 그냥 잘못나온 값에 제곱이고 1/2는 미분 편하게 하려고 하는거다. 마침 밑 목차가 수치미분이니깐 나누는걸로 보인다.

틈새 시장으로 원-핫 인코딩에 대해서 소개가 나오는데 정답 레이블에 하나의 원소만 1로 하고 그 외의 것들은 0으로 하는 것을 원-핫 인코딩이라고 한다.

교차 엔트로피 오차(CEE)

E = -Σ(t_i * log(y_i))  

이것도 공식은 간단하다. 이거는 다른것보다 구현하는 과정에서 조금 포인트가 있는데 로그 안에 0이 들어가면 음의 무한대를 향해서 발산하므로 아래와 같이 delta를 통해서 이것이 발생하는 상황을 방지해준다.

def CEE(y, t):
    delta = 1e-7
    return -np.sum(t*np.log(y+delta))

수치미분

미분 관련 내용은 아직 따끈따끈해서 대강 넘어가겠다. 책에서도 미분 자체에 대한 설명보다는 파이썬에서 계산과정에서 나올 수 있는 문제들에 집중하여 수치미분을 구현하였다. 코드는 아래와 같다.

def numerical_diff(f, x):
    h = 1e-4
    return (f(x + h) - f(x - h)) / (2 * h)

기울기

앞서 수치 미분을 통해 미분을 구현해 보았다. 그런데 수치 미분은 하나의 차원에 대해서 국한되어 계산되므로 신경망에서 다차원으로 이루어진 가중치 매개변수에 대해서는 적용하기에 적합하지 않다.

경사법(경사 하강법)

기울기를 잘 활용하면 함수의 최소값을 찾을 수 있는데 이것이 경사 하강법이다. 최적의 매개변수 값을 찾아가는 문제에 경사 하강법을 많이 사용한다. 현재 위치에서 기울기가 낮은 방향으로 정해진 거리만 이동한다. 여기서 정해진 거리를 학습률(learning rate)이라고 한다.

신경망에서의 기울기

2장에서 단순한 함수의 미분은 변수가 하나였지만, 신경망에서는 가중치가 수천 수만 개의 다차원을 이루고 있어 기울기를 계산하는 것이 부담된다. 아래는 기울기를 쉽게 구하는 방법 중 하나이다.

def gradient(f, x):
    h = 1e-4
    grad = np.zeros_like(x)
    for idx in range(x.size):
        tmp_val = x[idx]
        x[idx] = tmp_val + h
        fxh1 = f(x)

        x[idx] = tmp_val - h
        fxh2 = f(x)

        grad[idx] = (fxh1 - fxh2) / (2*h)

        x[idx] = tmp_val

    return grad

단순하게 보자면 모든 변수의 편미분을 벡터로 정리한 것이다. 이를 그대로 사용해 단순하게 경사하강법을 수행하는 것이 gradient descent이다.

학습 알고리즘 구현하기

2층 신경망 클래스 구현하기

class TwoLayerNet:
    def __init__(self, input_size, hidden_size, output_size):
        # Weight랑 bias 초기화 해야함

    def predict(self, x):
        # forward 과정

    def loss(self, x, t):
        # 손실 함수 구하는거

    def accuracy(self, x, t):
        # 정확도 구하는거

    def gradient(self, x, t):
        # 가중치 매개변수 기울기

2층짜리 신경망을 하나의 클래스로 구현해보았다.

미니배치 학습 구현하기

# 미니배치 학습 
def train(network, x_train, t_train, epochs, batch_size, learning_rate):
    train_size = x_train.shape[0]
    iter_per_epoch = max(train_size / batch_size, 1)

    for i in range(epochs):
        # 미니배치 획득
        batch_mask = np.random.choice(train_size, batch_size)
        x_batch = x_train[batch_mask]
        t_batch = t_train[batch_mask]

        # 기울기 계산        
        grad = network.gradient(x_batch, t_batch)

        # 매개변수 갱신
        for key in ('W1', 'b1', 'W2', 'b2'):
            network.params[key] -= learning_rate * grad[key]

        # 학습 경과 기록          
        loss = network.loss(x_batch, t_batch)
        print(f"Epoch {i+1}, Loss: {loss}")

앞서 구현한 TwoLayerNet을 바탕으로 미니배치 학습을 구현했다.

시험 데이터로 평가하기

# 시험 데이터로 평가
x_test, t_test = load_mnist(flatten=True, normalize=False)
test_acc = network.accuracy(x_test, t_test)  
print(f"정확도 : {test_acc}")  

학습한 모델이 실제로 얼마나 잘 작동하는지 시험 데이터로 정확도를 평가한다.

다음은 이렇게 만든 신경망을 더 깊게 쌓아보는 과정을 진행할 예정이다.​​​​​​​​​​​​​​​​

Quiz App의 특징

저는 대학 시절, 벼락치기로 시험을 준비할 때 자주 퀴즈 프로그램을 사용했습니다. 하지만 기존 프로그램들은 문제를 추가하거나 수정하는 게 번거로웠고, 정답 판단도 너무 엄격했죠. 그래서 저는 이런 불편함을 개선하고자 Quiz App을 개발했습니다.

Quiz App은 다음과 같은 특징을 가지고 있습니다:

• JSON 파일로 문제 관리: 문제와 정답을 JSON 파일로 관리할 수 있어 문제 추가, 수정, 삭제가 쉽습니다.
• 복사본 생성: 퀴즈를 진행할 때 원본 JSON 파일의 복사본을 생성하므로 원본 파일은 안전하게 보관됩니다.
• 랜덤 문제 출제: 문제가 랜덤으로 출제되므로 같은 문제 세트로도 다양한 연습을 할 수 있습니다.
• 스마트한 정답 판단: 생성형 AI를 활용하여 사용자의 다양한 정답 표현을 이해하고 유연하게 판단합니다.
• 간편한 문제 추가: 새로운 문제와 정답을 쉽게 추가할 수 있어 자신만의 문제 세트를 만들 수 있습니다.

효과적인 벼락치기를 위한 Quiz App

벼락치기는 짧은 시간 내에 효과적으로 공부하는 방법 중 하나입니다. Quiz App을 사용하면 벼락치기를 더욱 효율적으로 할 수 있습니다.

자신이 집중해야 할 개념이나 문제를 JSON 파일로 정리하고, Quiz App으로 반복 연습하세요. 랜덤으로 출제되는 문제를 빠르게 풀어내다 보면 자연스럽게 개념이 익숙해질 거예요. 또한, 생성형 AI가 다양한 표현을 이해하므로 정확한 용어가 기억나지 않더라도 괜찮습니다.

시험 전날, Quiz App과 함께 마지막 벼락치기를 해보는 건 어떨까요? 자신이 취약한 부분을 집중적으로 공부할 수 있을 거예요.

Quiz App 사용 방법

Quiz App은 GitHub 저장소에서 소스 코드를 다운로드 받을 수 있습니다. Python과 PyQt5가 설치된 환경에서 쉽게 실행할 수 있죠. 저장소의 README 파일에 자세한 설치 및 사용 방법이 나와 있으니 참고해 주세요.

마치며

벼락치기는 결코 좋은 공부 방법이 아니지만, 우리 대학생들에게는 피할 수 없는 현실이기도 합니다. Quiz App은 여러분의 벼락치기를 조금 더 효율적으로 만들어 줄 거예요. 시험 대비 잘 하시고, 좋은 결과 있기를 바랍니다!

P.S. Quiz App은 오픈 소스 프로젝트입니다. 여러분의 기여를 언제나 환영합니다. 새로운 기능 추가, 버그 수정 등 다양한 기여를 해 주시면 감사하겠습니다!

Olympiad Pizza

최근에 시간 초과에 하도 쳐맞다 보니 시간복잡도부터 생각하는 버릇이 생겼다. N이 1000이고, 모든 수가 1000이라면 그냥 요세푸스문제0인가 풀 때처럼 다 돌아도 100만번 밖에 연산이 돌지 않으므로 이게 맞는 풀이일 것이라고 생각했다. 근데 제한 조건에 대해서 고민하던 중 while 위에 sum(arr)라는 부분을 사용했는데 이게 문제가 될 수도 있겠다는 생각이 들긴 하였다. 그래도 뭐 100만번에 2초면 아주 여유 있다는 생각에 우선 생각한대로 코드를 짜고 제출하였다.

import sys

N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))
ans = [0 for _ in range(N)]
i = 0
cnt = 0

while sum(arr) != 0: # 종료 조건
    if arr[i] == 0:
        i += 1
        i = i % N
        # 0개면 더 이상 먹을 필요 없으니 PASS
    else:
        arr[i] -= 1
        cnt += 1
        if arr[i] == 0:
            ans[i] = cnt
        i += 1
        i = i % N
        # 1개 이상이면 먹고 0개가 되는 시간을 포착하기 위한 조건문 추가

print(*ans)

EASY! 솔직히 티어는 요세푸스 0 문제와 동일하게 측정해야 한다고 생각했다. 그냥 이 문제는 그나저나 자료구조 문제인데 잘 만든 웰메이드 문제긴 한 것 같다. Tier : 실버 4 TC :

1
100
OUT : 100
1000
1000 ...
OUT : 999901 999902 ...

그나마 엣지라고 생각할 수 있을만한 부분들만 정리해보았다.

장난감 경주

개인적으로 처음 문제를 보고 이해를 잘못한 것이 이 문제를 바로 해결하지 못하고 틀렸습니다.를 여러번 받게 한 이유일 것 같다. 기본적으로 이 문제들을 풀어나가는 이유가 코드잼에서 안정적으로 70점을 획득하기 위한것에 있다는 것을 고려하면 좋지 않은 신호라고 생각한다. 우선 처음 1초간만 이동하는 것이라는 생각을 하지 못했어서 예시들을 이해하지 못했고, 종이에 안 써버릇 하다 보니 그냥 머리로만 풀려 해서 오래 걸렸던 것 같다. 난이도 자체는 실버5가 맞는 것 같은데 난이도를 끄고 문제를 푸는 연습을 이후 문제부터는 진행해보려고 한다. 아래는 간단한 주석인데 아직 6시가 지나지 않아서(일본 가서 제출하려고 아껴놓고 있는거긴 한데) 제출은 아직 해보지 않았다. 그래도 기본적인 논리와 머리 속에 떠오르는 엣지 케이스를 조금 적어보았다.

3 12 11
3 3 3
Output : 4

나의 처음 코드는 실제로 여기서 -1이 출력되는 문제가 있었다. 아래는 고친 코드이고, 풀이의 방향성은 주석에 달아두었다. 문제를 보자마자 시뮬레이션, BF(Brute Force)가 생각나긴 하였다.

import sys

for _ in range(int(sys.stdin.readline())):
    N, X, Y = map(int, sys.stdin.readline().split())
    V = list(map(int, sys.stdin.readline().split()))
    my_speed = V[-1]
    op_speed = max(V[:-1])
    # V[-1]이 최댓값인 경우를 제외하기 위하여 표현
    if my_speed > op_speed:
        print(0)
        continue
        # 내 속도가 상대의 속도보다 빠를 경우

    time1 = X / op_speed
    for i in range(Y, my_speed - 1, -1):
        temp = X
        if (temp - i) / my_speed >= time1 - 1:
            # 조금 귀찮은 작업이었지만 1초의 간극을 수식으로 적었고 부등호를 통해서 공동우승을 유지하였다.
            if i == Y:
                ans = -1
                break
                # 최대치로 뛰었음에도 같거나 더 많이 사용함으로 -1 던지기 위하여 break
            ans = i + 1
            break

    print(ans)

그런데 이 코드 조차 5%에서 바로 틀렸습니다가 나와서 왜지 하고 고민을 많이 했다. 반례는 생각보다 간단하였는데 과 동기가 제시해 주었다.

3 12 4
12 1 11
Output : -1

이거 외에도 나눗셈이 주는 불안감이 있어서 곱셈으로 코드를 좀 수정하였다. 수정한 코드는 아래와 같다. 아 근데 진짜 많이 틀렸네... 내 정답률 또륵 ㅜㅜ

import sys

for _ in range(int(sys.stdin.readline())):
    N, X, Y = map(float, sys.stdin.readline().split())
    V = list(map(float, sys.stdin.readline().split()))
    my_speed = V[-1]
    op_speed = max(V[:-1])
    if my_speed > op_speed:
        print(0)
        continue
    time1 = X / op_speed
    ans = -1
    for i in range(int(Y), int(my_speed) - 1, -1):
        temp = X
        if (time1 - 1) * my_speed + i <= X:
            if i == Y:
                ans = -1
                break
            ans = i + 1
            break

    print(ans)

#BOJ27370

지금 LG전자에서 인턴을 진행하고 있는데 부끄럽게도 백준 1등을 받고 있다. 그렇다보니 사내 코드잼 대회에서 최소한 수상을 해야지 면이 살 것 같다는 생각이 최근에 많이 들어서 예전 코드잼 기출들을 쭉 풀어보면서 개념을 익혀야 겠다는 생각이 들었다. 그런 의미에서 쉬운 문제부터 타임어택 연습을 했다. 푸는데는 대충 6분 정도 걸렸던거 같은데 확실히 엣지케이스가 딱히 나오기 힘든 구조의 문제라 금방 해결하였다. 대회장이었으면 아마 나보다 빠른 사람이 있지 않았을까 싶은 생각이 들기는 하는데... 조금 풀이의 포인트 한 줄을 더하자면 거리가 같은 경우의 처리를 있거나 없거나로 처리하였다. 무슨 의미냐면 어차피 차에서는 3번있으니 한 번 있으나 같은 영향을 주기 때문에 번거롭게 이곳 저곳 던져주지 않고 그냥 있냐 없냐를 기준으로 분배해줬다는 얘기다. 주석은 알겠지만 위대한 GPT님의 도움을 받았다.

import sys  

# 테스트 케이스의 수를 입력 받습니다.  
T = int(sys.stdin.readline())  

# 각 테스트 케이스에 대해 반복합니다.  
for _ in range(T):  
    # 집의 수, 사람 A의 위치, 사람 B의 위치를 입력 받습니다.  
    N, Pa, Pb = map(int, sys.stdin.readline().split())  

    # 집의 위치를 입력 받아서 정렬합니다.  
    house = list(map(int, sys.stdin.readline().split()))  
    house.sort()  

    # 거리를 합산할 변수, A와 B의 이동 거리를 저장할 변수를 초기화합니다.  
    sum = 0  
    a = 0  
    b = 0  
    temp = 0  

    # 각 집에 대해 반복하면서  
    for i in house:  
        # 만약 A와 집과의 거리와 B와 집과의 거리가 같다면  
        if abs(Pa - i) == abs(Pb - i):  
            # temp를 이용해 누가 이동해야 할지 결정합니다.  
            if temp == 0:  
                temp = abs(Pb - i)  
            else:  
                temp = 0  
            # 거리를 합산합니다.  
            sum += abs(Pa - i)  
        # 만약 B와 집과의 거리가 더 짧다면  
        elif abs(Pa - i) > abs(Pb - i):  
            # 거리를 합산하고, B의 이동 거리를 갱신합니다.  
            sum += abs(Pb - i)  
            b += abs(Pb - i)  
        else:  
            # 그 외의 경우에는 거리를 합산하고, A의 이동 거리를 갱신합니다.  
            sum += abs(Pa - i)  
            a += abs(Pa - i)  

    # A와 B 중 누가 더 많이 이동했는지 확인하고, 덜 이동한 사람에게 temp를 더합니다.  
    if a > b:  
        b += temp  
    else:  
        a += temp  

    # 총 이동 거리와 A와 B의 이동 거리 차이를 출력합니다.  
    print(sum * 2,abs(a - b) * 2)  

위 코드의 치명적인 오류를 발견하여 새로운 정해를 첨부하는데 이거 왜 맞게 되냐 ㅋㅋ;;

```python import sys

T = int(sys.stdin.readline()) for _ in range(T): N, Pa, Pb = map(int, sys.stdin.readline().split()) house = list(map(int, sys.stdin.readline().split())) house.sort() sum = 0 a = 0 b = 0 temps = [] for i in house: if abs(Pa - i) == abs(Pb - i): temps.append(abs(Pa - i)) sum += abs(Pa - i) elif abs(Pa - i) > abs(Pb - i): sum += abs(Pb - i) b += abs(Pb - i) else: sum += abs(Pa - i) a += abs(Pa - i) for temp in temps: if a > b: b += temp else: a += temp print(sum * 2,abs(a - b) * 2) ```

#BOJ2191

우선 어제 아기상어 그놈한테 뒤지게 당해서 죽는 줄 알았다. 사실 어제도 쓸까 했는데 퇴근 할 때까지 아기상어랑 싸우고 있었다. 풀이 자체가 어려웠다기 보다 내가 처음 고안한 풀이의 허점을 찾는데 너무 오랜 시간이 걸렸다. 며칠 전까지 그래프의 신이 되었나 하는 생각이 났었는데 지금 돌이켜보니 진아의 말대로 걍 한창 자신만만할 시기의 그 시기였던 거 같다. 그래서 오늘은 티어도 좀 올리고 그래프도 팔각형 각을 좀 세울겸 오랜만에 기하학 문제를 풀었다. 이분매칭 문제인데 기하학 태그가 달려 있어서 이게 웬 떡이냐 하고 풀었다. 간단하게 주석은 남겨두었고, 이만 줄이겠다.

import sys

def find_match(mouse):
    for hole in graph[mouse]:
        if visited[hole]:
            continue
        visited[hole] = 1
        if matched[hole] == -1 or find_match(matched[hole]):
            matched[hole] = mouse
            return 1
    return 0

N, M, S, V = map(int, sys.stdin.readline().split())  # N: 쥐의 수, M: 구멍의 수, S: 도약 거리, V: 속력
mice = [None] + [tuple(map(float, sys.stdin.readline().split())) for _ in range(N)]  # 쥐의 좌표
holes = [None] + [tuple(map(float, sys.stdin.readline().split())) for _ in range(M)]  # 구멍의 좌표

graph = [[] for _ in range(N + 1)]  # 쥐와 구멍의 연결 관계 그래프
for i in range(1, N + 1):
    for j in range(1, M + 1):
        if (mice[i][0] - holes[j][0]) ** 2 + (mice[i][1] - holes[j][1]) ** 2 <= S * S * V * V:
            graph[i].append(j)  # 쥐 i가 구멍 j로 이동 가능한 경우 연결

unmatched = N  # 탈출하지 못한 쥐의 수
matched = [-1] * (M + 1)  # 각 구멍에 매칭된 쥐의 번호
for i in range(1, N + 1):
    visited = [0] * (M + 1)  # 구멍 방문 여부
    unmatched -= find_match(i)

print(unmatched)  # 탈출하지 못한 쥐의 수 출력

백준 좀 풀어봤다면 다들 한 번쯤은 백준 허브라는 구글 익스텐션에 대해서 들어봤을 것이다. 링크는 백준허브에 달아두었다. 이 프로그램을 사용하면 내가 푸는 백준 문제들을 바로바로 업데이트 해준다.

문제점

나같은 박쥐는 주로 사용하는 컴퓨터가 세 대나 되기 때문에(VPC 포함시 4대) 백준을 푸는 컴퓨터가 따로 정해져있지 않다. 그렇다보니 이것 저것 소실되는 내 백준 업로드가 많다. 그래서 주기적으로 한 번에 업데이트 하는데 이참에 다른 사람들도 사용하면 좋을 것 같아서 아주 허접하지만 깃허브를 팠다. 그냥 푼 문제 전부 크롤링 해주고 그 페이지를 순서대로 방문함으로써 백준 허브를 아주 효과적으로 활용하는 방법 중 하나일 뿐이다. 아래에 깃허브 링크 첨부해둘테니 사용하실 분들은 사용하셔도 좋을 것 같습니다. GITHUB LINK

#BOJ1504

그래프이론

매일 골드 이상 문제 푸는 걸 틈틈이 해보고 있는데 내가 잘 못하는 영역인 그래프이론 부분의 문항을 풀기 위해서 만든 문제집 문제 중 하나를 선정해서 풀기 시작했다. 다익스트라 하면 사실 어느정도 풀이 방향이 고정되어 있고 그 안에서 한 두개의 변수 변환 만으로도 풀 수 있을 것이라고 생각하였다. 우선 제약 조건들을 고려하지 않고 그냥 다익스트라로 짜면 어떤 식으로 나올지만 생각하면서 문제를 풀었다. 다익스트라로만 구현하면 아래와 같이 나오지만 당연히 제약조건이 있기 때문에 이제부터 진짜 문제풀이 시작이라고 볼 수 있다. 사실 이정도라면 원래는 실버1 정도였을 것 같다.

import sys

N, E = map(int, sys.stdin.readline().split())
arr = [[]for _ in range(N + 1)]

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    arr[a].append([b, c])
    arr[b].append([a, c])

v1, v2 = map(int, sys.stdin.readline().split())

visited = [float("inf")] * (N + 1)
visited[1] = 0
q = [[1, 0]]
while q:
    s, v = q.pop()
    if visited[s] < v:
        continue
    for e, w in arr[s]:
        if visited[e] > v + w:
            visited[e] = v + w
            q.append([e, v + w])
print(visited[-1])

뭐 이거야 간단한 다익스트라이니 누구나(다익스트라를 공부한) 구현할 수 있는 수준일텐데 여기서 어떻게 해야할까를 고민하면서 flag를 세워볼까 하였다. 근데 그러면 논리가 너무 내 나쁜 머리로 설계하기에 까다로울 것 같아서 그냥 깔끔하게 레이어를 쌓기로 하였다. 뭔소리냐면 다익스트라를 그냥 개많이 하는거다. v1, v2가 아니라 v1만 주어진다고 가정하자. 그러면 아래 코드는 정해를 던질 것이다.

import sys

N, E = map(int, sys.stdin.readline().split())
arr = [[]for _ in range(N + 1)]

for _ in range(E):
    a, b, c = map(int, sys.stdin.readline().split())
    arr[a].append([b, c])
    arr[b].append([a, c])

v1, v2 = map(int, sys.stdin.readline().split())

visited = [float("inf")] * (N + 1)
visited[1] = 0
q = [[1, 0]]
while q:
    s, v = q.pop()
    if visited[s] < v:
        continue
    for e, w in arr[s]:
        if visited[e] > v + w:
            visited[e] = v + w
            q.append([e, v + w])
#아래부터 그냥 v1시작으로 한 바퀴를 더 돈다고 생각하면 편하다.
q = [[v1, visited[v1]]]
visited = [float("inf")] * (N + 1)
while q:
    s, v = q.pop()
    if visited[s] < v:
        continue
    for e, w in arr[s]:
        if visited[e] > v + w:
            visited[e] = v + w
            q.append([e, v + w])
print(visited[-1])

이렇게 하면 시간 초과가 좀 걱정되긴 하지만 우선 구현해 보았다.

import sys

# N: 정점의 개수, E: 간선의 개수 입력받기
N, E = map(int, sys.stdin.readline().split())
# 인접 리스트를 사용하여 그래프 구현
arr = [[]for _ in range(N + 1)]

# 간선 정보 입력받기
for _ in range(E):
   a, b, c = map(int, sys.stdin.readline().split())
   arr[a].append([b, c])
   arr[b].append([a, c])

# 반드시 거쳐야 하는 정점 v1, v2 입력받기
v1, v2 = map(int, sys.stdin.readline().split())

# 1번 정점에서 각 정점까지의 최단 거리 계산 (다익스트라 알고리즘)
visited = [float("inf")] * (N + 1)
visited[1] = 0
q = [[1, 0]]
while q:
   s, v = q.pop()
   if visited[s] < v:
       continue
   for e, w in arr[s]:
       if visited[e] > v + w:
           visited[e] = v + w
           q.append([e, v + w])

# v2에서 v1까지의 최단 거리 계산 (역방향 다익스트라 알고리즘)
qq = [[v2,visited[v2]]]
q = [[v1, visited[v1]]]

visited = [float("inf")] * (N + 1)
visited[v1] = q[0][1]
while q:
   s, v = q.pop()
   if visited[s] < v:
       continue
   for e, w in arr[s]:
       if visited[e] > v + w:
           visited[e] = v + w
           q.append([e, v + w])
q = [[v2, visited[v2]]]

# v1에서 N번 정점까지의 최단 거리 계산 (다익스트라 알고리즘)
visited = [float("inf")] * (N + 1)
visited[v2] = q[0][1]
while q:
   s, v = q.pop()
   if visited[s] < v:
       continue
   for e, w in arr[s]:
       if visited[e] > v + w:
           visited[e] = v + w
           q.append([e, v + w])
ans = visited[-1]

# v2에서 1번 정점까지의 최단 거리 계산 (역방향 다익스트라 알고리즘)
visited = [float("inf")] * (N + 1)
visited[v2] = qq[0][1]
while qq:
   s, v = qq.pop()
   if visited[s] < v:
       continue
   for e, w in arr[s]:
       if visited[e] > v + w:
           visited[e] = v + w
           qq.append([e, v + w])
qq = [[v1, visited[v1]]]

# 1번 정점에서 v1까지의 최단 거리 계산 (다익스트라 알고리즘)
visited = [float("inf")] * (N + 1)
visited[v1] = qq[0][1]
while qq:
   s, v = qq.pop()
   if visited[s] < v:
       continue
   for e, w in arr[s]:
       if visited[e] > v + w:
           visited[e] = v + w
           qq.append([e, v + w])
ans = min(visited[-1], ans)

# 결과 출력
if ans == float("inf"):
   print(-1)
else:
   print(ans)

되네? 역시 나야 ㅋㅋ

#BOJ1028 다이아까지 영차영차 가기에는 실력이 많이 모자르다는 생각이 많이 들어서 최근 골드 문제로 내실 다지기를 많이 하고 있다. 그러다가 누군가 푼 플레 문제를 훑어 보던 중 대충 풀이에 대한 아이디어가 떠올라서 점수나 올릴 겸 플레 문제를 풀었다. 그나저나 요즘 랩실 갈 준비를 하는데 생각보다 빡센거 같아서 고민이 많이 된다. 주석은 감사하신 나의 새로운 신 클로드3-opus님께서 해주셨다.

import sys

# 입력받은 행과 열 값을 저장
r, c = map(int, sys.stdin.readline().split())

# 왼쪽 위에서 오른쪽 아래로 가는 대각선의 연속된 1의 개수를 저장할 2차원 리스트 초기화
ld = [[0] * c for _ in range(r)]

# 오른쪽 위에서 왼쪽 아래로 가는 대각선의 연속된 1의 개수를 저장할 2차원 리스트 초기화
rd = [[0] * c for _ in range(r)]

# 입력받은 다이아몬드 모양의 글자를 순회하며 1인 경우 ld와 rd의 해당 위치에 1을 저장
for i in range(r):
    diamond = sys.stdin.readline().strip()
    for j in range(c):
        temp = diamond
        if diamond[j] == '0':
            ld[i][j] = 0
            rd[i][j] = 0
        else:
            ld[i][j] = 1
            rd[i][j] = 1

# 대각선의 연속된 1의 개수를 계산
for i in range(r - 2, -1, -1):
    for j in range(c):
        # 왼쪽 위에서 오른쪽 아래로 가는 대각선의 연속된 1의 개수 계산
        if ld[i][j] == 1 and j != 0:
            ld[i][j] += ld[i + 1][j - 1]
        # 오른쪽 위에서 왼쪽 아래로 가는 대각선의 연속된 1의 개수 계산
        if rd[i][j] == 1 and j != c - 1:
            rd[i][j] += rd[i + 1][j + 1]

# 최대 다이아몬드의 크기를 저장할 변수 초기화
res = 0

# 모든 위치에서 가능한 다이아몬드의 크기를 계산하여 최대 크기 갱신
for i in range(r):
    for j in range(c):
        if ld[i][j] != 0 and rd[i][j] != 0:
            res = max(res, 1)
        if ld[i][j] != 1 and rd[i][j] != 1:
            n = min(ld[i][j], rd[i][j])
            while n > 1:
                if rd[i + n - 1][j - n + 1] >= n and ld[i + n - 1][j + n - 1] >= n:
                    res = max(res, n)
                n -= 1

# 최대 다이아몬드의 크기 출력
print(res)

#BOJ 4485

요즘 그래프이론을 꽤나 열심히 풀고 있어서 오늘의 그래프로 다익스트라 문제를 건드려 보았다. 최근에 사내 역량 인증 시험에 응시했었는데 하도 자료구조를 리스트로 대체해서 쓰다보니깐 덱이 리스트 대비 어떤 장점이 있는지 기억이 안나서 테케 몇 개를 틀려서 아쉽게 만점을 받지 못하였다. 그래서 자료구조 연습도 할 겸 해서 다익스트라 문제를 꺼내왔다. 언제나 그랬듯이 별 생각없이 리스트로 먼저 구현했었다. 아래와 같이 BFS와 유사하지만 visited에 숫자를 도입해서 구현하였다.

import sys

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
cnt = 1
while True:
    arr = []
    visited = []
    N = int(sys.stdin.readline())
    if N == 0:
        break
    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))
        visited.append([float('inf')] * N)
    q = [[0, 0]]
    visited[0][0] = arr[0][0]
    while q:
        x, y = q.pop()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                cost = visited[x][y] + arr[nx][ny]
                if cost < visited[nx][ny]:
                    visited[nx][ny] = cost
                    q.append([nx, ny])
    print(f"Problem {cnt}: {visited[-1][-1]}")
    cnt += 1

결과적으로 이 코드는 시간 초과가 났다. 사실 뭐 얼마나 단축되는지는 잘 모르겠긴 한데 heapq를 사용하면 그래도 최솟값 먼저 뽑으니 뭐라도 단축되겠지 하는 생각으로 도입했다. 아래는 내가 아닌 챗봇의 나의 고민에 대한 대답이다. 틀린게 있다면 얘기해주시면 좋겠다.

우선순위 큐를 사용하면 가장 비용이 낮은 노드를 먼저 방문하게 되어 그래프를 더 효율적으로 탐색할 수 있습니다. 일반적으로 대부분의 그래프 탐색 알고리즘(DFS, BFS 등)의 경우에는 모든 노드를 방문해야 하므로 최악의 경우 시간 복잡도는 O(V + E)입니다. 여기서 V는 그래프의 노드 수, E는 에지의 수입니다. 그러나 우선순위 큐를 사용하는 알고리즘인 다익스트라 알고리즘의 경우, 각 노드는 한 번만 큐에 들어가므로 큐에 노드를 입력하거나 제거하는데 드는 시간 복잡도가 O(logV)입니다. 따라서 다익스트라 알고리즘의 총 시간 복잡도는 O((V+E) logV)가 됩니다. 그럼에도 불구하고, 이러한 로직 변경은 기존의 DFS 알고리즘이 동일한 노드를 여러 번 방문하거나 큐에 넣는 경우, 특히 그래프가 밀집해 있어서 모든 노드와 에지를 방문해야 하는 경우에 시간 복잡도를 크게 개선할 수 있습니다. 이런 상황에서는 다익스트라 알고리즘이 더 효율적입니다.

뭐 그렇다고 한다. 나는 이정도로 세밀한 거를 아는게 그리 즐겁진 않아서 대충 이러면 이거써야지 정도만 알고 넘어가는 편인데 이러면 손해보기 쉬운데 읽으시는 분들은 더 꼼꼼하게 보시길 바랍니다. 아래는 정해 코드입니다.

import sys , heapq

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
cnt = 1

while True:
    arr = []
    visited = []
    N = int(sys.stdin.readline())
    if N == 0:
        break
    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))
        visited.append([float('inf')] * N)
    q = [[arr[0][0], 0, 0]]
    visited[0][0] = arr[0][0]

    while q:
        cost, x, y = heapq.heappop(q)
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < N and 0 <= ny < N:
                next_cost = cost + arr[nx][ny]
                if next_cost < visited[nx][ny]:
                    visited[nx][ny] = next_cost
                    q.append([next_cost, nx, ny])

    print(f"Problem {cnt}: {visited[-1][-1]}")
    cnt += 1

트리

PS에서 자료 구조 자체를 선호하는 편은 아니라서 파이썬으로 트리를 다루는 경험은 진짜 1-2때 데이터구조 수업을 배운 후 처음인 것 같다. 물론 개념적으로는 계속해서 학습했었지만 이를 활용해서 알고리즘 문제를 해결하는 것은 또 다른 일이기 때문에 팔자에도 없는 파이썬으로 트리 구현하기를 시작했다. 클래스 자체가 익숙하지 않아 이거 보고 저거 보고 하면서 잘 만들어서 돌긴 하는데 아직도 저게 왜 제대로 나오지에 대해서 의문이 있다... 나 천잰가? 코드는 작성하고 언제나와 같이 GPT에게 주석을 도와달라고 했다. 오늘은 좀 찝찝한 풀이 같긴 한다.

import sys

class TreeNode:
    def __init__(self, data):
        self.data = data  # 노드의 데이터
        self.left = None  # 왼쪽 자식 노드
        self.right = None  # 오른쪽 자식 노드

class BinaryTree:
    def __init__(self):
        self.nodes = {}  # 모든 노드를 저장하는 딕셔너리

    def insert(self, parent, left, right):
        # 부모 노드가 아직 없으면 생성
        if parent not in self.nodes:
            self.nodes[parent] = TreeNode(parent)
        node = self.nodes[parent]

        # 왼쪽 자식 노드 처리
        if left != ".":
            if left not in self.nodes:
                self.nodes[left] = TreeNode(left)
            node.left = self.nodes[left]

        # 오른쪽 자식 노드 처리
        if right != ".":
            if right not in self.nodes:
                self.nodes[right] = TreeNode(right)
            node.right = self.nodes[right]

    def get_root(self):
        return self.nodes['A']  # 'A'를 루트 노드로 가정

    # 전위 순회 함수
    def preorder(self, node, result=[]):
        if node:
            result.append(node.data)  # 현재 노드 방문
            self.preorder(node.left, result)  # 왼쪽 서브트리 순회
            self.preorder(node.right, result)  # 오른쪽 서브트리 순회
        return result

    # 중위 순회 함수
    def inorder(self, node, result=[]):
        if node:
            self.inorder(node.left, result)  # 왼쪽 서브트리 순회
            result.append(node.data)  # 현재 노드 방문
            self.inorder(node.right, result)  # 오른쪽 서브트리 순회
        return result

    # 후위 순회 함수
    def postorder(self, node, result=[]):
        if node:
            self.postorder(node.left, result)  # 왼쪽 서브트리 순회
            self.postorder(node.right, result)  # 오른쪽 서브트리 순회
            result.append(node.data)  # 현재 노드 방문
        return result

접근

이런 비슷한 문제를 당장 오늘 스터디 하면서 들었었다. 16953번이었는데 이 문항을 BFS로 풀면 꽤나 비슷하지 않을까 하는 생각을 하게 되었다. 근데 나같은 그래프 혐오론자들은 이 문항을 그리디로 해결하였기 때문에 우선 16953번부터 BFS로 해결해보기로 하였다. 아 근데 진짜 어떻게 해결하는거지...라고 생각하던 찰나 그냥 큐에 다 때려넣으면 될 것 같아서. 먼저 해결하였다. 그냥 기본적으로 큐에다가 다 저장하는 형태로 넣었고, 해결할 방법을 찾았다. 다만, 문제점이 발생하였는데 연산의 횟수만 트래킹하다 보니 이게 무슨 연산을 한건지가 저장이 안되게 되어서 하나 더 추가하기로 하였다. 처음 나왔던 풀이는 이러했다.

import sys, collections

T = int(sys.stdin.readline())
for _ in range(T):
    A, B = map(int, sys.stdin.readline().split())
    queue = collections.deque([(A, '')])
    while queue:
        x, cmd = queue.popleft()
        if x == B:
            print(cmd)
            break
        queue.append(((x * 2) % 10000, cmd + 'D'))
        queue.append(((x - 1) % 10000, cmd + 'S'))
        queue.append(((x // 1000) + (x % 10000) * 10, cmd + 'L'))
        queue.append(((x // 10) + (x % 10) * 1000, cmd + 'R'))

다만 테스트케이스에서 틀린 부분이 나와서 실제 값을 던진 결과 실수로 %10000을 안해준 부분이 문제였어서 보완해서 제출하였다. 결과는 메모리 초과 파이썬으로 제출한 사람 중 맞춘 인원들 코드의 길이가 모드 긴데 다른 분들이 최소 저보다 고티어이시길래 겸손한 마음으로 PyPy3 신 님한테 다시 코드를 올려보았다. 아오 동일한 결과 어떤 부분이 문제일까? 아니나 다를까 질문게시판을 가니 저와 같은 메모리 문제를 겪는 분들이 많았습니다. 애초에 평소 같았으면 정답률 20퍼 짜리는 쳐다도 안 보는데 클래스 3에서 마지막 남은 문제여서 그래도 해결하기 위해 고민 하였습니다. 우선 방문 조건 처리를 하라는 글들이 많아서 방문 조건 처리를 위해 arr를 설정하였습니다. 이러면 끊기는 분기(어떤 느낌인지 아시죠?)를 통해서 뭔가 개선할 수 있을 것 같았다.

import sys, collections

T = int(sys.stdin.readline())
for _ in range(T):
    arr = [False for _ in range(10001)]
    A, B = map(int, sys.stdin.readline().split())
    queue = collections.deque([(A, '')])
    while queue:
        x, cmd = queue.popleft()
        if x == B:
            print(cmd)
            break
        if not arr[(x * 2) % 10000]:
            arr[(x * 2) % 10000] = True
            queue.append(((x * 2) % 10000, cmd + 'D'))
        if not arr[(x - 1) % 10000]:
            arr[(x - 1) % 10000] = True
            queue.append(((x - 1) % 10000, cmd + 'S'))
        if not arr[((x // 1000) + (x % 10000) * 10) % 10000]:
            arr[((x // 1000) + (x % 10000) * 10) % 10000] = True
            queue.append((((x // 1000) + (x % 10000) * 10) % 10000, cmd + 'L'))
        if not arr[((x // 10) + (x % 10) * 1000) % 10000]:
            arr[((x // 10) + (x) % 10) * 1000] = True
            queue.append((((x // 10) + (x % 10) * 1000) % 10000, cmd + 'R'))

제출하니 마의 3% 메모리 초과 구간은 넘길 수 있었다. 야호! 맞췄다

새해 목표

늘 그렇듯 새해 목표는 거창해야 하니깐 올해는 365일 백준을 매일매일 풀면서 벨로그도 매일 한 개씩 남겨보려고 한다. 백준에 대한 벨로그로 매일 남기는 것은 불가능에 가까울 것 같아서... 다른 분야로도 조금 남겨보려고 한다. 그래도 첫 날이니까 많이 까먹은 분야부터 다뤄보기로 했다.

이중 우선순위 큐

문제를 보고 나서 양 끝단에서 출력해주는 문제이니 그냥 Priority Queue를 두 개 만들까 했다. 하지만 한 가지 간과한 부분이 그렇게 되면 연산 과정중에 옳지 않은 값이 나올 경우의 수가 너무 쉽게 발견 되었다. 그래서 과감하게 큐를 버리고 힙큐를 사용하기로 하였다. Heap자체가 최댓값과 최솟값을 빠르게 찾기 위해서 고안된 연산이니 이를 활용해서 문항을 해결하면 해결 가능할 것이라고 생각했다. 다만, Priority Queue를 사용하는 부분이랑 같은 문제점이 발생하였는데 바로 동기화 문제였다. 동기화 문제를 해결하기 위해서 어떤 방식을 사용할까 고민을 많이 하였다. 그러기 위해서 유지되는 값에는 어떤 것이 있을 까 고민하였고, deleted라는 딕셔너리를 만들어서 사용하였다. 그 외의 과정은 단순한 heapq과정과 유사하니 생략하겠다 아래는 코드와 주석이다. 코드가 너무 더러운것은 아닌지 걱정이 된다. 주석은 우리 위대하신 GPT형님의 도움을 받았다.

import heapq
import sys
from collections import defaultdict

def sync_heaps(max_heap, min_heap, exists):
    """
    Max heap과 Min heap을 동기화하는 함수입니다.
    삭제된 원소를 추적하고, 두 힙에서 해당 원소를 제거합니다.
    """
    # Max heap에서 삭제될 원소가 있는지 확인하고 삭제합니다.
    while max_heap and not exists[max_heap[0][1]]:
        heapq.heappop(max_heap)

    # Min heap에서 삭제될 원소가 있는지 확인하고 삭제합니다.
    while min_heap and not exists[min_heap[0][1]]:
        heapq.heappop(min_heap)

def solution(operations):
    """
    주어진 연산을 수행하고, 이중 우선순위 큐에서 최댓값과 최솟값을 반환합니다.
    """
    max_heap, min_heap = [], []  # Max heap과 Min heap 초기화
    exists = defaultdict(bool)   # 원소의 존재 여부를 추적하기 위한 defaultdict
    count = 0  # 각 원소에 부여할 고유 인덱스

    for op in operations:
        operation, num = op[0], int(op[2:])
        if operation == "I":
            # 'I' 연산은 원소를 삽입합니다.
            heapq.heappush(max_heap, (-num, count))
            heapq.heappush(min_heap, (num, count))
            exists[count] = True
            count += 1
        elif operation == "D":
            # 'D' 연산은 원소를 삭제합니다.
            if num == 1 and max_heap:
                # 최댓값 삭제
                exists[max_heap[0][1]] = False
                heapq.heappop(max_heap)
            elif num == -1 and min_heap:
                # 최솟값 삭제
                exists[min_heap[0][1]] = False
                heapq.heappop(min_heap)
            sync_heaps(max_heap, min_heap, exists)

    sync_heaps(max_heap, min_heap, exists)

    # 결과 반환
    if not max_heap or not min_heap:
        return "EMPTY"  # 큐가 비어있으면 'EMPTY' 반환
    else:
        return f"{-max_heap[0][0]} {min_heap[0][0]}"  # 큐에 원소가 있으면 최댓값과 최솟값 반환

# 테스트 케이스
T = int(sys.stdin.readline())  # 테스트 케이스의 수 T
for _ in range(T):
    k = int(sys.stdin.readline())  # 각 테스트 케이스별 연산의 개수 k
    operations = [sys.stdin.readline().rstrip() for _ in range(k)]  # 연산들을 입력받음
    print(solution(operations))  # 솔루션 함수 호출 및 결과 출력