코딩 채널 알림 알림 중 알림 취소 구독 구독 중 구독 취소 구독자 4411명 알림수신 85명 @은월영 프로그래밍 및 코딩 채널 질문 동적 프로그래밍 감자가좋아 추천 0 비추천 0 댓글 15 조회수 271 작성일 2023-01-31 15:44:29 ⚠️ 이 게시물은 작성자가 삭제할 수 없도록 설정되어 있습니다. https://arca.live/b/programmer/68758012 이거 풀다가 든 생각인데.해시맵 쓰는것, 배열 쓰는것 퍼포먼스에서 큰 차이 있나? 추천! 0 ( 0) 비추! 0 ( 0) 공유 댓글 [15] 글쓰기 Aix_la_Chapelle 2023-01-31 15:49:27 답글 1로만들기 문제임? 펼쳐보기▼ Aix_la_Chapelle 2023-01-31 15:52:09 답글 dp라면 어차피 밟고가는 칸들은 무조건 생길거라 연산 초반부터 끝날때까지 메모리는 해시맵보다 더먹을거같음. 근데 해시맵에 값을 추가할필요없이 dp배열 참조만 특정 값들에서 일어날테니 전처리빼고 속도면에서는 배열이 빠르거나 같을지도 펼쳐보기▼ 감자가좋아 2023-01-31 16:02:45 답글 https://school.programmers.co.kr/learn/courses/30/lessons/154538 문제 DP로 풀라다가 뇌가 저릿저릿해서 그냥 닥 BFS박으니 됨. 프로그래머스 스쿨 코딩테스트 연습 - 숫자 변환하기 *수정됨 문제 DP로 풀라다가 뇌가 저릿저릿해서 그냥 닥 BFS박으니 됨. 펼쳐보기▼ Aix_la_Chapelle 2023-01-31 16:28:42 답글 아는 범주내에서 가장 정직한 dp문제여서 풀어봣음. 가장 오래걸린 테케가 414ms 찍히는데 님은 어때요 펼쳐보기▼ 감자가좋아 2023-01-31 16:40:44 답글 빡머갈이라 DP2시간박다가 열뻗쳐서 포기한지라... BFS로 할땐 814나옴.... 펼쳐보기▼ Aix_la_Chapelle 2023-01-31 16:42:40 답글 이게 코드구조상 큐에 가능한 모든 스텝을 싹다 박으면서 진행을 하려해서 그런듯요 dp로 짜면 x부터 y까지 i가 1씩더하면서 선형으로 찾는 구조라 차이가 좀 크게나긴 하나봐요 펼쳐보기▼ 감자가좋아 2023-01-31 16:58:42 답글 *수정됨 i에서 가능한 이전 경우b1,b2,b3중에 카운트(memo)가 가장 작은걸 선택해서 1을 더하고 memo[i]에 저장하는방식임? 전 지금까지 X에서 다음 세개를 뽑고 거기서다시 재귀시켰는데.... 접근방식부터가 틀렸구나. 펼쳐보기▼ 감자가좋아 2023-01-31 17:00:00 답글 이렇게하니까 자꾸 "가장 작은 횟수"가 아니라 "코드상 가장 먼저 도착한"값이 나와서 BFS로 도망쳤는데... 펼쳐보기▼ Aix_la_Chapelle 2023-01-31 17:00:33 답글 dp라는 분류가 점화식도 글코 문제마다 싹다달라서 감잡기 힘든게 맞져ㅠㅠ 일단 이 문제는 댓달아주신대로 풀면 어렵지않게 풀리네요 펼쳐보기▼ Aix_la_Chapelle 2023-01-31 17:02:00 답글 하나 첨언하자면 이전 세개중에 가능한거중 최소를 뽑을필요없고, 세개를 하나씩 들고와서 작은거 때려넣으면 돼요. 쓰고보니 그얘기가 그얘기같지만요. if문 3개쓰라는 뜻 펼쳐보기▼ Aix_la_Chapelle 2023-01-31 17:03:28 답글 글구 재귀도 틀린 풀이는 아니고여! 재귀로 시간이 많이난다 싶으면 현재 구한 최소스텝을 인자로 백트래킹 먹이고 시간 얼마나 줄어드는지 비교해보는것도 소소한 재미랍니다 문제는 통과하면 장땡인것 펼쳐보기▼ Aix_la_Chapelle 2023-01-31 17:16:48 답글 dfs로 풀려면 백트래킹이 필수긴 할거에여 아마 펼쳐보기▼ 감자가좋아 2023-02-01 05:07:51 답글 해보진 않앗지만 s to e범위가 넓어서 dfs로는 시간초과가 날거같고 bfs가 차선 dp가 최선인듯? 펼쳐보기▼ Aix_la_Chapelle 2023-02-01 05:10:44 답글 좀이따 백트래킹으로 짜보고 결과 말씀두림 펼쳐보기▼ Aix_la_Chapelle 2023-02-01 05:53:25 답글 백트래킹 박아도 TLE네요 낄낄 펼쳐보기▼ 새로운 댓글이 달렸습니다! 댓글 작성 음성댓글 아카콘 업로드 중 0초 해당 브라우저에서는 오디오 플레이어를 지원하지 않습니다. 녹음 중지 삭제 업로드 작성 글쓰기 전체글 개념글 등록순 추천순 (24시간) 추천순 (3일) 추천순 (전체) 댓글갯수순 (3일) 최근댓글순 추천컷 5 10 20 30 50 70 100 기타 최근 최근 방문 채널 최근 방문 채널 모두 삭제 전체 공지 정보 질문 잡담 유머 C/C++ C# Python Java Front-end Back-end 앱·겜 AI·Data 그 외 번호 제목 작성자 작성일 조회수 추천 데이터베이스가 중요한 이유 알아보기 [3] 엘프 2023.02.02 174 4 질문 멍청한 질문 하나 해봄 [6] 나이테 2023.02.02 154 0 selenium, beautifulSoup 쓰지말고 PlayWright 써라 [4] 안다라 2023.02.01 298 4 ai 대학원 컨택 붙엇슴 [6] CE 2023.02.01 254 5 잡담 코 막히니깐 진짜 미칠거 같다 EasyDae 2023.02.01 96 0 정보 존나 쩌는 공부 방법 ( 무료 ) [4] 엘프 2023.02.01 1593 12 질문 아카가 죽어서 글을 못썼네.. [6] 랑린이 2023.02.01 247 0 정보 스윙 잘하는 튀니지 아재 짭쵸네코 2023.02.01 189 3 질문 python으로 canvas 안에 들어가있는 요소를 클릭하고싶어.. [2] 랑린이 2023.02.01 169 1 css 만지다 보면 [1] 지우개로널지울수만있다면 2023.01.31 139 1 질문 동적 프로그래밍 [15] 감자가좋아 2023.01.31 271 0 ChatGpt 소감 [8] 짭쵸네코 2023.01.31 248 5 인텔리제이 가격보니 어지럽네 [9] 짭쵸네코 2023.01.31 215 0 생각해보니 여긴 파딱 안뽑음? [5] 로켓곰군 2023.01.31 154 0 코딩할때 가장 골때리는거 [15] 로켓곰군 2023.01.31 225 2 솔직히 자바스윙 / JavaFx 그냥 개적폐같음 [6] 짭쵸네코 2023.01.31 184 4 아 진짜 코딩 넘 어렵다 [4] 출퇴근용사 2023.01.31 189 1 질문 python selenium으로 체크박스 클릭해주려면 [5] 랑린이 2023.01.31 111 0 si나 sm말고 [4] ㅇㅇ 2023.01.31 181 0 스택오버플로우 형님들 의외로 친절한지도..? [2] 보빗보빗보비빗 2023.01.31 109 0 글쓰기 전체글 개념글 등록순 추천순 (24시간) 추천순 (3일) 추천순 (전체) 댓글갯수순 (3일) 최근댓글순 추천컷 5 10 20 30 50 70 100 기타 전체 제목/내용 제목 내용 글쓴이 댓글 Keyword search form input 검색 -4 -3 -2 -1 23-02-02 06:04 +1 +2 +3 +4