Priceless

위의 문제에 포함되어 있는 예시로 설명한다 처음에는 for문을 두 개를 작성한 후 탐색하는 날짜에 필요한 상담 일 수 만큼 sum 변수를 추가로 설정하여 합하는 식으로 작성했다 물론 그렇게도 풀릴 것 같았지만 예외 처리가 많이 필요했다 그래서 다른 방법을 찾았다 내가 문제를 보고 답을 직접 구할 때도 뒤에서부터 구했던 것 같다 막상 코드로 작성하니 머리 속으로 풀었던 것 그대로 녹여내면 되는데 아직까지 쉽지 않은 듯하다 뒤에서 부터 역순으로 찾는다 날짜가 넘어가면 그 전 인덱스를 탐색하고 dp에 저장한다 이후 기존의 dp와 이전 날의 새로운 값을 더했을 때를 비교하여 더 큰 값을 dp에 저장한다 이후 dp를 모두 구했을 때 나오는 dp[1]을 출력한다 // baekjoon 15486 #include #i..

입력 받은 코인의 금액으로 코인 여러 개를 사용하여 목표 코인 금액을 맞출 수 있는 경우를 찾는 문제 물론 브루트 포스로도 풀 수 있겠지만 이 문제는 제한 시간이 0.5초로 다이나믹 프로그래밍으로 풀어야한다 dp[0]은 모든 코인이 0개가 사용되므로 dp[0] = 1로 설정한다 새로 갱신되는 dp 값은 새로운 코인 단위를 사용하기 전의 dp 값과 새로운 코인 단위의 dp 값을 합하면 새롭게 dp가 갱신된다 문제의 예시 경우를 살펴본다 1원, 2원, 5원을 사용하여 10원을 구성하는 예시이다 1원을 사용하는 경우 1원부터 10원까지 구성할 수 있는 경우는 모두 1가지 2원을 사용하는 경우 1원 1가지, 2원 2가지(1+1, 2), 3원의 경우 1원만 사용해서 3원을 구성하는 경우와 2원을 1원과 2원을 사..

이제는 dp를 푸는 대략적인 방법?을 알게 되었다 기본 배열, dp 배열, max or min 을 통해 구할 수 있다 물론 max 와 min 함수를 쓰기 위해서는 입력 값으로부터 어떻게 출력하는 과정까지 그 과정을 분석해야 함수를 쓸 수 있을 것이다 이 문제는 테스트 케이스 당 두 줄의 입력 값을 받는다 dp 배열의 초기 부분은 미리 초기화한다 배열의 길이가 1이더라도 동작한다 변이 이웃하지 않으니까 대각선이거나 두 칸 뒤의 값 중에서 최대 값을 고른다 이후 배열의 마지막에서 더 큰 값을 출력한다 // baekjoon 9465 #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); cout.tie(0); i..

Computer Systems: A Programmer's Perspective 위 책의 내용을 정리하였습니다 Chapter 1: A Tour of Computer Systems 아래 코드를 기준으로 설명 // hello.c #include int main() { printf("hello, world\n"); } 1-1. Information Is Bits + Context 프로그램은 소스 프로그램(소스 파일)로 이루어져 있다 소스 프로그램은 bit(0과 1)의 연속이며, 8bit를 1byte로 정한다 ASCII code(아스키코드)를 사용하여 문자를 정수로 변한다 아래는 hello.c를 아스키코드로 변환한 결과이다 이러한 코드를 해석하기 위해서는 context가 필요하다 context를 통해 이 코드가..

가장 긴 증가하는 부분 수열을 구하는 문제 문제 설명만 듣고는 도무지 이해가 되지 않았다 그냥 숫자가 커질 때 count하면 되지 않을까 라는 식으로 처음은 배열을 사용하지 않고 이전 값과의 비교 만으로 코드를 구성했다 int N; cin >> N; if(N == 1){ return 0; } int ascent = 1; int input; int temp = 0; for(int i = 0; i > input; if(i == 0){ temp = input; } if(i > 0){ if(temp N; int count = 0; int arr[MAX]; int dp[MAX]; for(int i = ..

원하는 상대를 저장하는 arr 방문 여부를 나타내는 visited 그룹이 확정된 상태를 나타내는 done 총 세 가지 배열을 사용하여 구현하였다 방문 여부를 먼저 탐색한 후 방문 했다면 짝이 이루어져있는지 확인한다 이후 과정을 dfs로 반복한다 이후 배열의 크기에서 조가 짜여진 사람 수를 뺀 값을 출력한다 자잘한 과정의 흔적(?)을 보면 void reset()을 구현하는 대신 memset을 통해 초기화할 수 있다 for 문이 꼭 하나씩 커지도록 선언하지 않더라도 동작한다 또한 select의 s를 소문자로 사용했을 때 pc의 컴파일러에서는 잘 작동했지만 백준에 제출했을 때는 중복된 함수 이름으로 컴파일 에러가 발생했다 백준에서 select 라는 이름의 변수를 선언할 때는 유의해야한다 // baekjoon ..

터미널을 이용하여 깃허브에 파일 업로드 하는 방법 간단하게 정리한 것으로, 용어나 표현에 오류가 있을 수 있음 OS: Mac OS Mac OS 터미널 사용 : ''를 지운 후 그대로 입력 '', "": '작은 따옴표'혹은"큰 따옴표" 내에 입력 git push 0. 터미널에서 우선 git을 설치한다 설치가 완료된 후 1. 터미널에서 우선 올리고자 하는 파일에 접근한다 cd 2. 다음 깃을 초기화 한다 git init 3. 깃허브 저장소와 파일을 연결한다 git remote add origin 이미 remote origin이 존재하는 경우 remote origin 을 삭제한다 # error: remote origin already exists. git remote remove origin 4. 원하는 파일..

이번에도 BFS를 활용한 문제 실생활에서 BFS를 많이 사용하는 것일까 BFS가 많이 쓰이는 것 같다 빙산 문제는 다음 상태의 배열까지 고려해야 하므로 두 개의 배열을 사용한다 이후 접한 면의 수를 탐색한 후 그만큼 빼고 다음 상태에 덮어쓰기한다 처음보는 함수를 많이 사용했기 때문에 조금 더 익숙해져야 할 것 같다 // baekjoon 2573 #include #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); } int arr[301][301]; int next_arr[301][301]; bool visited[301]..

BFS로 해결할 수 있는 문제 그리디 알고리즘과 유사하게 풀 수 있는 문제다 0초 동안은 2배로 이동할 수 있으므로 먼저 2배 이동이 가능한지 여부를 판단한다 이후 한 칸 전진할지 후진할지를 판단한다 이후 min_ 값을 통해 최소 시간을 구한다 함수가 많이 쓰이진 않지만 꽤 복잡하게 구성되어 있는 문제인 듯하다 // baekjoon 13549 #include #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); } int arr[100001]; //bool visited[101][101][101] ; //int dir[6]..

3차원으로 접근하는 BFS 문제 3차원으로 접근해야 하므로 움직이는 방향 또한 x축, y축, z축에 맞게 설정한다 BFS를 진행한 후 모든 토마토를 검사했을 때 0이 있다면 -1을 출력하고 즉시 종료한다 테스트 케이스는 1회이므로 별도의 방문 여부 기록과 reset함수를 구현하지 않았다 크기의 제한이 있어서 그런가 생각보다 시간을 많이 소요되진 않았다 // baekjoon 7569 #include #include #include using namespace std; // codes for fast I/O void init(){ cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); } int arr[101][101][101]; //bool visited[..