본문 바로가기

전체 글

백준 2098 외판원 순회 백준 문제를 다시 잡아봤다. DP문제에서 진짜 엄청 유명한 문제인 TSP를 풀어보고 싶어서 찾았다. 근데 진짜 TSP 키워드로 구글에서 검색하면 별의 별 곳 응용이 다 나오더라. 가장 많이 보이는게 경로 문제, 최근 드론 배달이 많이 연구 되고 있는데 그쪽 관련된 이미지가 많이 나오는 것 같다. 문제는 심플하다. 유향 가중치 그래프를 인접 행렬로 입력 받아서, 모든 노드를 방문하고 제 자리로 돌아오는 경로를 찾는 것 - 이 문제에서는 비용만 구하면 된다. 처음 접근은 DFS를 사용해서 DP에 저장해가면서 풀어보는 방식이었다. 직전 문제인 도둑질에서도 같은 접근 방법을 사용했었다. 근데 코드 구현 중, 탐색 중간에 되돌아가거나 다음 경로가 없을 때 너무 복잡해져서 엎었다... 그래서 이걸 어떻게 하나..... 더보기
프로그래머스 도둑질 프로그래머스 코딩테스트 연습의 DP 분류 마지막 문제이다. 뭔가 어디서 봤던 문제같긴 한데, 다시 생각해봤다. 근데 되게 머리가 아팠다. DP배열을 쓰고 어디서부터 어디까지 최적해를 찾아본다 했지만, 앞에서부터 찾아봐도 뒤에서부터 찾아봐도 답이 없었다. 집이 원형이 아니고 직선 형태로 배치되어 있다면 해당 접근이 괜찮아 보이는데, 맨 앞 칸과 맨 뒤 칸이 조건에 맞물려 있어 답이 없어보였다. 이렇게 해볼까 저렇게 해볼까 고민을 하다가, 질문들을 찾아봤다. 그 중에, DFS와 섞은 솔루션이 있어서 찬찬히 뜯어보면서 답을 작성해봤다. 일단 dp[i][b] 는 , 첫번째 집을 털었거나(b==true), 털지 않았을 때(b==false) i번째 집까지 털었을 경우 최대값을 의미한다. 첫번째 집을 털었을 경우, .. 더보기
프로그래머스 등굣길 프로그래머스의 DP 쪽 문제 세번째이다. 2D 지도가 주어지고, 1,1에서부터 최우하단 좌표까지 가능한 경로의 개수를 구하는 문제이다. 여기서, 특정 위치가 웅덩이가 될 수 있다. 해당 웅덩이는 경로에 포함될 수 없다(지나갈 수 없다). 움직이는 패턴이 상하좌우가 아니라, 오른쪽과 아래쪽으로만 움직인다는 제약조건이 있다. 이 제약조건이 있어서 DP를 사용해 문제를 풀 수 있다고 한다. 부분의 최적해가 전체 최적해에 포함이 되기 때문에 DP를 사용할 수 있다... 정말 코드에서 엄청난 삽질을 했다. 처음에는 dfs와 섞은 솔루션을 작성했다. 이 문제와 비슷하게 접근해서 작성했는데, 계속 문제가 발생했다... 정확도 체크는 어느정도 맞는데, 효율체크가 우수수수... 틀려 다른 방법을 찾아봤다. 그냥 위에서부.. 더보기
프로그래머스 정수 삼각형 저번 문제와 같이, DP 분류의 프로그래머스 문제이다. 머리속에서 좀 많이 생각을 해봤는데, 저번에 풀었던 문제와 아주 유사하게 접근할 수 있을 것 같다. 저번에 풀었던 문제는 dp 배열의 폭이 정해져있다면, 이번 dp 배열은 높이가 1 늘어날때마다 폭도 1 늘어난다. 그리고, 문제 지도는 피라미드 모양으로 되어있는데 이것을 왼쪽으로 챡 붙인 직각삼각형으로 생각하는게 머리속에서 문제를 푸는데 훨씬 도움이 된다. 저번 내려가기 문제에서는 폭이 정해져있고, 밑으로 내려가면서 그 자리에서 가질 수 있는 최대값/최소값을 저장하고 있었다. 이번 문제에서는 최소값이 없는 반면, 옆으로 한칸씩 증가한다. 따라서 DP 배열은 N*N 크기를 가진다. (마지막 row의 경우 N크기 이므로.) 그 외에, 각 셀을 채워주는것.. 더보기
프로그래머스 N으로 표현 프로그래머스에서 DP 문제를 찾아보고 나온 문제이다. 가장 쉬운 문젠데 역시 DP는 어렵다.... DP 배열은 dp[i] : i개의 숫자를 가지고 만들 수 있는 숫자 를 저장한다. 처음 DP를 초기화할때, 그 갯수만큼의 숫자를 저장해둔다. (예를 들어, dp[1] = 5, dp[2] = 55 ...) 그리고, 최대 8개까지 사용하는지 확인하는 것이므로, 8까지(사용 가능한 숫자 개수) 루프를 돌면서 dp 탐색을 한다. 만약 N = 5이고, 탐색하는 루프 수(숫자 개수)가 5이면, 5(op)5555 55(op)555 555(op)55 5555(op)5 이렇게 나눌 수 있다. 5를 1개 사용한 숫자들과 4개 사용한 숫자들의 연산 결과가 dp[5]에 추가되고, 2개와 3개의 연산, 3개와 2개의 연산, 4개와.. 더보기
백준 7579 앱 알고리즘 스터디에서 친구가 가져왔던 문제이다. 0-1 Knapsack문제 유형을 보고 잡은 문제라는데, 좀 어려웠다. 그냥 0-1 knapsack 문제로 생각하면, 배낭크기를 메모리로 따져서 col에 M개 열을 만들어 해볼까 했는데 메모리의 최대값이 10000000이라 배열으로 선언을 할 수 없을 것 같다. 그럼 어떻게 할까...? 친구가 풀다가 솔루션을 확인했는데, 그 방식이 너무 신기했다. col을 다른 값을 사용해서 채우는 방법이 있더라. 이 문제 같은 경우에는, col에 cost를 넣어둬 문제를 해결했다. 따라서 dp[i][j] = i번째 앱까지 봤을때, j비용으로 얻을 수 있는 메모리의 크기가 된다. dp 배열의 내용을 한번 보자, [0] [1] [2] [3] [4] [5] [6] [7] [8].. 더보기
[문을 편하게 열고 싶다] 아두이노 + RFID 태그 복사해보기(진행중) 스마트폰과 스마트워치를 등록해서 문을 편하게 열어보자! 는 대찬 목표를 세우고 시작했지만, 아쉽게도 실패로 돌아갔던 저번 포스팅에 이어, 어떻게 하면 문을 편하게 열까...? 라는 목표를 달성하기 위해, 빈 태그에 출입카드를 복사하는 소목표를 세웠다. 일단, RFID를 좀 더 쉽게 쓰고 읽기 위해 아두이노에 RFID 모듈을 붙여 사용하기로 한다. 사용하는 모듈은 RC522 모듈이다. 아두이노 RFID 키트 하면 쉽게 구할 수 있는 모듈인것 같다. 해당 모듈을 설치하고, 아두이노 IDE에 라이브러리를 설치한다. 내가 사용한 라이브러리는 여기 있다. 해당 라이브러리를 설치 한 뒤, Example 을 보면, 다양한 예제들이 있다. 일단, ReadNUID를 사용하면, RFID 태그의 고유값인 UID를 읽을 수 .. 더보기
백준 2096 내려가기 조금 쉬워보이는 것을 잡았다. 이해하기도 나쁘지 않고, 왠지 그림도 있어서 있어보인다. 문제는 쉽다. N*3 게임 판에서 한칸씩 내려가는데, 바로 밑이나 바로 밑과 붙어있는 칸만 갈 수 있다. 각 칸은 점수가 있고, 그 점수의 합이 최대가 되는것, 최소가 되는 것을 찾으면 된다. 처음 접근은 dp[N][N] 으로 정의해서 dp[i][j] = i 번째 줄에서 j번째 줄까지 최대값을 저장하려고 했다. 근데 이렇게 접근을 하면, 맨 마지막 줄에서부터 역순으로 탐색을 해야하고, 역순으로 탐색을 하는 도중에 어디 칸을 밟았는지도 저장을 따로 했어야 했다. 심지어 최소값 저장 DP, 최대값 저장 DP를 따로 저장해야 했다. 머리를 뜯다가 질문글을 슬쩍 슬쩍 봤는데, 좀 신기했다. 내가 접근했듯이 밑에서부터 한칸한칸.. 더보기

티스토리툴바