질문하나 해도 될까? - 컴퓨터공학 채널

컴퓨터공학 채널

알림 알림 중 알림 취소

구독자 3330명 알림수신 25명 @SeworL

컴퓨터를 좋아하는 사람들의 모임

C/C++ 질문하나 해도 될까?

ㅇㅇ (121.179)

추천 0 비추천 0 댓글 7 조회수 205 작성일 2021-04-22 06:33:09

https://arca.live/b/programmers/24936159

https://www.acmicpc.net/problem/14596 이 문제인데

이미지 짜집기 같은 문제더라고

그래서 짱구좀 굴리다가

두개 행렬을 겹쳐서 각 자리에 (빨간그림값 - 파랑그림값)^2값을 저장하고

첫번째 행에서 가장 적은값 찾고 그다음행은 +-1로만 탐색하게 만들려고 했는데 그렇게하면 최적의 결과가 안나오더라고..

어떤 발상의 전환이 필요할까?

댓글 [7] 글쓰기

유자차

2021-04-22 07:03:01 답글

얼핏 보기엔  DP 문제같은데
i번째 행의 j번째 위치를 선택했을때 아래로 선택하며 내려갈 때 오차 합의 최솟값을 f(i,j)라고 하면
f(i, j) = min{f(i+1, j-1), f(i+1, j), f(i+1, j+1)} + E[i][j]
이런 식으로 하면 될거같음

펼쳐보기▼

ㅇㅇ (121.179)

2021-04-22 07:10:21 삭제 수정 답글

f(i,j)가 각 행에서 최소의 오차라는 소리인가? 근데 혹시 E(i,j)는 어떤건지 알 수 있을까? dijkstra 알고리즘 내용인가?

펼쳐보기▼

ㅇㅇ (121.179)

2021-04-22 07:14:06 삭제 수정 답글

일단 또 생각난게 첫 행에 모든열을 확인해서 아래 행으로 이동하는걸 찾고 이중에 가장 최소값을 찾는거로 해볼까?

펼쳐보기▼

유자차

2021-04-22 07:19:07 답글

E[i][j]는 그냥 (i,j) 선택했을때 오차값 적은거임

기본적으론 님 생각대로 첫 행에 모든 항을 선택해 보면 최적해는 나오는데
거기서 성능을 향상시키기 위해 쓰는 기법이 DP
f(i,j) 구한 값을 배열에 저장해뒀다가 다시 연산하는 대신 값만 불러와서 계산하는거

펼쳐보기▼

유자차

2021-04-22 07:21:38 답글

이제보니 범위가 워낙 작아서 DP 없이도 될거같다
비슷한 문제 중에 범위 더 큰 것도 있던데 그건 DP 쓰는 문제일듯

펼쳐보기▼

ㅇㅇ (121.179)

2021-04-22 07:23:01 삭제 수정 답글

*수정됨

ㅇㅎ! 그르쿠만! ㄳㄳ 일단 첫행에 모든항 실행하게 하고 배열내에서 하니까 그거 주의한다음에 실행해보고 다음에 최적화를 생각해봐야겠네 ㄳㄳ

펼쳐보기▼

ㅇㅇ (121.179)

2021-04-22 07:23:46 삭제 수정 답글

일단 첫행에서 모든걸 비교하는 식으로 가볼께 팁 감사!

펼쳐보기▼

댓글 작성

업로드 중

0초

녹음 중지 삭제

글쓰기

전체글 개념글

최근 최근 방문 채널

최근 방문 채널

전체 공지사항 질문/조언 읽을거리

번호 제목

작성자 작성일 조회수 추천

블록체인 관련 대학원이 있나요? [2]

ㅇㅇ (125.128) 2021.04.24 220 0

하드웨어 노트북인데 발열이 원래 이런가요 [4]

Bi (36.11) 2021.04.24 231 0

코딩 없이 GraphQL 서버 구축하는 서비스 [4]

Wnswl 2021.04.24 366 2

게이들아 이거 나 해킹당한거냐? [8]

ㅇㅇ 2021.04.24 360 0

스마트폰 우분투를 더 발전시켰다(?) [11]

Ubuntu 2021.04.23 387 2

여러분은 코딩하다 막히면 어떻게 하시나요? [17]

코듀라416D 2021.04.23 296 0

C/C++ 질문 드립니다... [14]

ㅇㅇ (121.179) 2021.04.23 296 0

질문/조언 네카라쿠배 블랙리스트가 조언하는 네카라쿠배 입사지원 팁 [4]

갈 2021.04.23 680 3

버그바운티란걸 알게됐는데 의문점 질문드립니다 [2]

ㅇㅇ (218.55) 2021.04.22 202 0

하드웨어 스압)컴맹을 위한 CPU+그래픽 카드+RAM 보는법 [8]

ㅇㅇ 2021.04.22 1567 8

KTIS소속 SH공사 시스템관리자 하실분 찾아요

KTIS (218.152) 2021.04.22 265 0

산기/기사 시험 질문좀 [1]

타는쓰레기 2021.04.22 143 1

제가 컴퓨터를 하나 사고싶은데 조언좀 부탁드립니다 구체적으로요 [10]

엘프사이콩그루 2021.04.22 212 0

C/C++ 하다가 막혀서.. 다시 질문 드림다.. [15]

ㅇㅇ (121.179) 2021.04.22 249 0

C/C++ C언어 질문드립니다! 도움이 절실하게 필요합니다.. [1]

Gunda 2021.04.22 265 0

C/C++ 질문하나 해도 될까? [7]

ㅇㅇ (121.179) 2021.04.22 205 0

하드웨어 컴맹흑우가 묻습니다 [2]

Deus 2021.04.22 250 0

이런 멋진 채널이 있었다고? [5]

코듀라416D 2021.04.22 142 2

하드웨어 2테라 하드만 10개가 넘는데 [7]

유야 2021.04.22 211 0

휴대폰에 우분투를 깔았다 [7]

Ubuntu 2021.04.21 247 2

질문/조언 컴퓨터 오류났는데 도움 좀 주실수 있으십니까? [3]

롸잇어웨이 2021.04.21 189 0

선생님들 프론트엔드 신입으로는 어느정도까지 공부해야하나요? [2]

ㅇㅇ (39.7) 2021.04.21 331 0

C/C++ c 랜덤함수를 어떻게 구현해야할까요... [6]

환몽사 2021.04.20 244 0

인터넷 질문 [2]

색욕의_호박전 2021.04.20 102 0

하드웨어 스압?)인터넷 사용 주의점+문제 해결방법+꿀팁 [10]

ㅇㅇ 2021.04.20 2238 38

학기말 프로젝트 계획서 작성하라는데 [6]

pipip 2021.04.20 199 0

언어론, 회로이론 같은 분야를 공부하고 싶은데 [3]

ㅇㅇ (125.128) 2021.04.19 182 0

Python 작은 질문이 있습니다 [6]

말석이오너 2021.04.19 238 0

C/C++ 급합니다! 진짜 급해요! 한번만 도와주세요! [2]

ㅇㅇ (121.128) 2021.04.18 301 0

아 내일 2차 면접있음 [3]

윾동1 2021.04.18 214 1

글쓰기

전체글 개념글