알고리즘 검색 결과

해당 글 7건


5. 백준 1463 1로 만들기 문제 공부

1. 문제를 풀면서 백준 온라인 저지에서 푼 문제를 내 블로그에 다루려고 한다. '동적 계획법 기초 단계'의 다섯 번째 문제이다. 동적 계획법을 이런 방식으로 사용하는구나 하고 느낄 수 있다. 2. 문제 출처 및 보기 https://www.acmicpc.net/problem/1463 3. 문제 해결 이 문제도 동적 계획법의 문제이다. 다른 문제와 마찬가지로 이전 문제(작은 문제)의 해결로 현재 문제를 해결하는 방식으로 풀었다. 입력 값이 N이라면 '1 ~ (N-1)'의 해답을 이용해서 풀 수 있다. 해결 방법의 KEY로 주어진 값을 '-1'하거나 '/2', '/3'할 수 있다는 조건이 있다. 그러므로 func(N)은 1 + func(N-1), 1 + func(N/2), 1 + func(N/3) 중 하나일..
알고리즘 (백준 온라인 저지 공부)/동적 계획법 기초 단계 7년 전

4. 백준 2579 계단 오르기 문제 공부

1. 문제를 풀면서 백준 온라인 저지에서 푼 문제를 내 블로그에 다루려고 한다. '동적 계획법 기초 단계'의 네 번째 문제이다. 동적 계획법을 이런 방식으로 사용하는구나 하고 느낄 수 있다. 동적 계획법 기초 단계 9번 문제인 '포도주 시식' 문제와 비슷하다! 2. 문제 출처 및 보기 https://www.acmicpc.net/problem/2579 3. 문제 해결 계단 오르기는 한 번에 한 칸 또는 두 칸 오를 수 있으며 연속으로 두 두 번까지만 오를 수 있다. 예를 들면 한 칸을 1, 두 칸을 2라고 한다면 (1) 1+1(2) 1+2(3) 2+1 (4) 2+2이렇게 네 가지 방법이 있는 것이다. 하지만 더 간단하게 생각해볼 수 있다. 현재 N번째 계단에 서 있다고 한다면 한 칸 전에서 오는 방법(CA..
알고리즘 (백준 온라인 저지 공부)/동적 계획법 기초 단계 7년 전

3. 백준 1932 숫자삼각형 문제 공부

1. 문제를 풀면서 백준 온라인 저지에서 푼 문제를 내 블로그에 다루려고 한다. '동적 계획법 기초 단계'의 세 번째 문제이다. 동적 계획법을 이런 방식으로 사용하는구나 하고 느낄 수 있다. 2. 문제 출처 및 보기 https://www.acmicpc.net/problem/1932 3. 문제 해결 숫자 삼각형은 아래와 같다. 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 7은 이전 값이 없으므로 3부터 문제를 해결해 나갈 수 있다. 두 번째 줄부터 모든 수는 왼쪽 위 또는 오른쪽 위 수와 더해서 너 높은 값을 만들어 나갈 수 있는데, 왼쪽 경사에 있는 3같은 경우에는 왼쪽 위에 수가 없으므로 오른쪽 위의 수를 더한다(오른 쪽도 마찬가지..). 이런 방식으로 맨 마지막 줄까지 계산을 완료했다면 이제..
알고리즘 (백준 온라인 저지 공부)/동적 계획법 기초 단계 7년 전

2. 백준 1149 RGB거리 문제 공부

1. 문제를 풀면서 백준 온라인 저지에서 푼 문제를 내 블로그에 다루려고 한다. '동적 계획법 기초 단계'의 두 번째 문제이다. 동적 계획법을 이런 방식으로 사용하는구나 하고 느낄 수 있다. 2. 문제 출처 및 보기 https://www.acmicpc.net/problem/1149 3. 문제 해결 이 문제는 동적 계획법을 처음 풀어보면 어려울 수 있다. 해결 방법은 이렇다. RGB 색상을 칠하면서 집을 옮겨다녀야 한다. 그리고 반드시 첫 집에서 R, G, B 중 하나를 선택해야 한다. 첫집은 물론이고 다음 집으로 가면서 무엇을 선택해야 할지는 아직 모른다. 그러므로 현재 집에서 각각의 색상을 선택했을 때, 이전 집까지의 최소 값과 더하여 현재 집에서 최소가 될 수 있는 색상을 찾아야 한다. 이 때 신경 ..
알고리즘 (백준 온라인 저지 공부)/동적 계획법 기초 단계 7년 전

1. 백준 1003 피보나치 함수 문제 공부

1. 문제를 풀면서 백준 온라인 저지에서 푼 문제를 내 블로그에 다루려고 한다. '동적 계획법 기초 단계'의 첫 문제는 피보나치 함수 관련된 문제이다. 이 문제에서 주어지는 조건은 동적 계획법이 아닌 방식으로도 쉽게 풀 수 있게 해줬다. 하지만 조건(구하려는 N번째 피보나치 수의 N)이 최대 40으로 정해지지 않았다면 동적 계획법을 사용해야 했을 것이다. 이는 피보나치 수를 구하는 알고리즘에 동적 계획법을 적용하는 것에 대해 생각해 보라는 뜻을 주는 문제가 아닌가 싶었다. 2. 문제 출처 및 보기 https://www.acmicpc.net/problem/1003 3. 내 소스코드 이 문제는 딱히 설명이랄게 없다. 동적 계획법을 사용한 것이 아니고, 0과 1이 반환되는 상황마다의 카운트를 출력해주었다. 1..
알고리즘 (백준 온라인 저지 공부)/동적 계획법 기초 단계 7년 전

[자료구조] 스택(배열 이용) - push, pop

안녕하세요. PEACE-입니다.자료구조 스터디 [세 번째] 글입니다. 1. 스택 스택이란 자료구조 중 하나입니다. 가장 최근에 들어간 데이터가 가장 먼저 나오며 흔히 후입선출(Last In First Out)이라고 말합니다. 이와 같은 데이터 구조를 통해 다양한 작업을 수행할 수 있습니다. 하나의 예를 들겠습니다. 재귀적 함수의 작업 수행 중에 함수의 호출이 일어나면 스택에 함수에 대한 정보가 push되고 함수의 끝이나 return을 만나면 함수가 종료되면서 pop을 통해 나중에 호출된 함수가 스택에서 빠져나옵니다. 2. 스택 구현 배열은 사이즈가 정해져있습니다. 현재 데이터의 위치를 알기 위해 top이라는 변수를 사용합니다. 스택 포인터라고도 합니다. 또한 push 메서드는 스택(배열)에 데이터를 넣는..
자료구조 8년 전

[자료구조] 선형 연결리스트 - 삽입, 삭제(First)

안녕하세요. PEACE- 입니다.자료구조 스터디 [첫 번째] 글입니다. 1. 연결리스트 노드는 데이터와 다른 노드를 가리키는 공간을 가지고 있습니다. 연결리스트는 데이터 구조로써 노드간의 연결로 이뤄진 데이터 구조를 말합니다. HEAD는 첫 번째 데이터가 담긴 노드를 가리키며 연결리스트를 식별할 수 있고 연결리스트의 시작이라고 할 수 있습니다. 또한 HEAD를 통해 삽입, 삭제 기능 구현을 효율적으로 할 수 있습니다. 이러한 구조의 연결리스트를 이용해 원하는 위치에 데이터를 삽입하고 삭제하는 기능을 구현할 수 있습니다. 본 포스팅에서는 맨 앞에 데이터를 삽입하고 맨앞의 데이터를 삭제하는 기능에 대해 다루겠습니다. 2. 삽입 (First) 첫 번째 위치에 노드를 삽입하기 위한 방법은 아주 간단합니다. 하지..
자료구조 8년 전