본문 바로가기

# 미사용

 (138)
# 미사용 [백준 1520] 내리막길 문제풀이 위 로고를 누르면 해당 문제로 이동합니다. 1차 풀이 (2018-07-05, 3948 KB, 4 MS) 높이가 낮은 칸은 모두 탐색한다. 왼쪽 위에서부터 오른쪽 아래로 이동하는 경로를 구하는 문제이지만,그렇다고 모든 경로가 항상 오른쪽으로, 항상 아래쪽으로 향하지 않는다. 첫 번째 예시는 왼쪽선택을 포함한 최적 경로이고,두 번째 예시는 위쪽선택을 포함한 최적 경로이다. 정리하자면 항상 오른쪽으로 항상 아래로 움직이려고 하지 말고,가능한 모든 방향을 탐색해야 한다. 루프는 없다. 모든 방향을 탐색하다가 루프에 빠지면 어떻게 될까,빙글빙글 돌다가 시간초과로 오답처리되는게 아닐까?루프검출 로직을 넣어야 되는게 아닐까? 걱정말자, 루프는 발생하지 않는다. 루프가 만들어지려면 원 형태의 경로가 생성되어야 하는데,..

2018. 8. 16. 16:22
# 미사용 [백준 2156] 포도주 시식 문제풀이 위 로고를 누르면 해당 문제로 이동합니다. 1차 풀이 (2018-08-14, 2060 KB, 4 MS) 부분 문제로 나눌 수 있을까? K개의 포도주 잔이 있을 때, 한번에 해결하기 힘들다면 각 선택별로 부분 문제를 만들어 해결해보자고 생각했다. 각 문제에서 가능한 선택마다 부분 문제를 만들었을 때,각 문제는 일정한 입력에 대해 일정한 결과만을 출력하며,원래 문제와 부분 문제는 서로 독립적이고, (앞의 선택이 뒤의 선택에 영향을 주지 않음)부분 문제가 최적일 때, 원래 문제도 최적으로 구해질 수 있으므로,최적 부분 구조를 가진 동적 계획법으로 풀 수 있다. 제한을 올바르게 이해하고 있었나? 주어진 제한은 "연속으로 3잔 마시는 것은 안된다" 이지만, 연속으로 고르지 않아도 된다는 점에 유의해야 한다. 만약..

2018. 8. 15. 13:11
# 미사용 [백준 2293] 동전 1 풀이노트 위 로고를 누르면 해당 문제로 이동합니다. 1차 풀이 (2018-08-08, 메모리 초과) 적당히 동전을 고르고, 채워야 할 나머지 가치를 부분문제로 만든다. 100원을 만들어야 하는 문제에서 40원 동전 1개를 선택했을 경우,남은 60원은 재귀적으로 호출하여 문제를 해결한다. 답의 형태를 제한하자. 한 차례에 하나의 동전을 선택하도록 구현했다고 하자. 다음과 같이 "순서는 다르지만 실제로는 같은 경우"인 해답이 도출된다.20원 → 10원 → 30원 → 20원10원 → 30원 → 20원 → 20원 30원 → 20원 → 20원 → 10원...위처럼, 중복되는 경우도 모두 정답으로 해석하므로,구해진 값은 정답보다 항상 크게된다. 위의 문제점을 해결하려면 답의 형태를 제한해야 한다.다음과 같이 조건을 거는 것..

2018. 8. 9. 14:48
# 미사용 [백준 10844] 쉬운 계단수 풀이노트 위 로고를 누르면 해당 문제로 이동합니다. 1차 풀이 (2018-08-07, 1988 KB, 0 MS) 최적부분 구조에 눈치채자. 첫번째가 first로 시작하고, 전체가 n자리인 수를 살펴보자.nn-1n-2... 10first first가 이미 정해져있기 때문에,n-1에는 first+1 또는 first-1 밖에 올 수 없다. 따라서 원래문제는 다음과 같은 부분문제로 나뉜다.첫번째가 first+1로 시작하고, 전체가 n-1 자리인 계단수의 개수는?첫번째가 first -1로 시작하고, 전체가 n-1 자리인 계단수의 개수는?위의 부분문제와 원래문제는 독립적이므로 최적부분 구조로 볼 수 있다.최적부분 구조는 동적 계획법으로 풀 수 있다. 적당한 메모이제이션을 사용하면 성능향상도 가능하다. 1자리수도 계단수인가?..

2018. 8. 7. 16:21
# 미사용 [백준 1005] ACM Craft 풀이노트 위 로고를 누르면 해당 문제로 이동합니다. 1차 풀이 (2018-08-07, 2380 KB, 576 MS) 최적부분 구조에 눈치채라. 이 문제는 건물 N의 최소건설시간을 구하는 문제이며,건물 N을 짓기위해 필요한 건물들을 X라고 하면,다음 포인트를 짚을 수 있어야 한다.모든 X가 지어져야 N을 건설할 수 있다.X 내에서 최소건설시간이 가장 긴 건물이 완성되었을 때, 이미 모든 X는 건설되어 있다.즉, solve(N)을 풀려면 선행건물들에 대한 부분문제를 풀어야 한다.원래문제와 부분문제는 독립적이므로 최적부분 구조이다. 최적부분 구조는 동적계획법으로 해결할 수 있으며,중복되는 부분문제를 해결하기 위해 메모이제이션(캐싱)을 활용한다.

2018. 8. 7. 15:29
# 미사용 [백준 1463] 1로 만들기 풀이노트 위 로고를 누르면 해당 문제로 이동합니다. 1차 풀이 (2018-08-05, 5892 KB, 4 MS) 무식하게 위에서부터 전부 계산하자. int *S 이라는 배열을 하나 선언하고,S[x]는 x을 만들기 위한 최소횟수라고 정의하자. 입력받은 N에서부터 1까지 내려오면서,모든 S[x]를 항상 최소로 갱신시키면,S[1]은 해당 케이스의 결과를 가르킨다. 큰 배열은 동적할당을 사용하자. 크기가 100001인 배열을 생성했을 때,정적배열은 런타임 오류가 발생했지만,동적배열은 정상적으로 실행되었다. 2차 풀이 (2018-08-05, 1984 KB, 0 MS) 최적 부분 구조에 눈치채자. 정답인 최소 연산횟수를 반환하는 함수를 count(n) 이라고 하자. count(n)을 풀기 위해서 우리는 3가지 연산을 사용할..

2018. 8. 5. 03:48
# 미사용 [백준 2579] 계단 오르기 풀이노트 위 로고를 누르면 해당 문제로 이동합니다. 1차 풀이 (2018-08-04, 1984 KB, 0 MS)1칸으로 2번 시도하면 안된다. (1)처음 계단을 올라갈 때를 제외하고는 1칸으로 2번 연속 시도하면 안된다.연속한 3개의 계단을 밟을 수 없다는 룰 때문이다. 0 1 2 3 0에서 시작했을 경우 ) 0, 1, 2 → 연속되는 계단 2개로 규칙위반 아님. 1에서 시작했을 경우 ) 1, 2, 3 → 연속되는 계단 3개로 규칙위반. 0에서 시작한 경우를 먼저 처리하고,이후로는 1칸을 2번 시도하지 않으면서 차근차근 계단을 건너본다. 1칸으로 2번 시도하면 안된다. (2)1칸을 2번 시도하지 않는다는 것은,1칸을 시도한 차례의 전후는 항상 2칸으로 시도해야 한다는 것을 의미한다. → 1칸을 시도한 후에는 반드..

2018. 8. 5. 01:38
# 미사용 임베디드, 간단한 OTP 프로젝트 개요학교에서 실습용으로 사용되는 임베디드 키트를 활용하여,간단한 OTP 기능을 구현해보고, 실제 로그인 페이지를 구축하여 실습. OTP 핵심 기능에만 초첨을 맞추었기 때문에굳이 DB 연동까지 하지는 않았다. 프리뷰 구현 상세하드웨어단HTTP 메세지를 통해 서버측에 로그인 요청.서버측에서 온 응답메세지를 파싱하여 로그인 결과를 알아냄.각각의 계정(아이디)에는 고유한 OTP 키트의 일련번호가 부여됨.해당 계정에 1:1 대응된 OTP 키트로만 로그인이 가능함.로그인 성공시 종료.서버단로그인 시도 시, 4자리 숫자를 출력하고 일정시간 후 만료되도록 함.일정주기마다 로그인이 성공되었는지 확인. (Long Polling, AJAX)로그인 성공 시, 팝업을 통해 알림. 코드공개하지 않음.

2018. 8. 3. 14:47

티스토리툴바