기록장

문제https://www.acmicpc.net/problem/9084동전의 가지 수 N1, 5, 10, 50, 100, 500원으로 M원을 만드는 모든 방법의 수를 출력하라.풀이d[i][j] = i번 동전까지 사용해서 금액 j원을 만들 수 있는 경우의 수//점화식if(j  예) 1원, 2원, 5원으로 10원을 만들 수 있는 경우의 수코드import java.io.*;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new In..

문제https://www.acmicpc.net/problem/190400 또는 1을 총 n개 붙여서 만들 수 있는 이진수열의 개수를 구하는 문제풀이n을 1부터 5까지 늘려가며 어떤 수열이 만들어질 수 있는지 구해보면 규칙을 찾을 수 있다.n번째에 만들 수 있는 이진 수열의 개수 = (n-1번째에 만들 수 있는 이진 수열 개수) + (n-2번째에 만들 수 있는 이진 수열 개수) 이 규칙의 원리는 n-1번째에 만들어진 이진 수열의 맨 뒤에 '1'을 붙인 값들 + n-2번째에 만들어진 이진 수열의 맨 뒤에 '00'을 붙인 값들이 두 가지가 합쳐져서 n번째의 이진 수열이 만들어진다는 점을 고려하면 쉽게 찾을 수 있다. 오답노트문제에서 답을 출력할 때 숫자를 15746으로 나눈 나머지를 출력하라고 해서 최종 값에..

문제https://www.acmicpc.net/problem/11403 가중치 없는 방향그래프가 주어졌을 때, 모든 정점(i, j)에 대해 i->j로 가는 길이가 양수인 경로가 있는지 없는지 구하는 프로그램을 작성하라. 양수인 경로가 있으면 i행 j열의 숫자를 1로, 없으면 0으로 출력해야 한다. 입력:30 1 00 0 11 0 0풀이i행 j열의 값이 1이면 양수인 경로가 있다고 했으므로 입력으로 인접행렬이 주어진 것과 같다. 그런데 이 인접행렬은 정점 i에서 j로 바로 가는 경로가 있는가에 대한 정보이다.i에서 j로 바로 갈 수는 없지만 k를 거쳐서 가는 경로가 존재할 수도 있다. 이 경우를 찾아내야 한다. 노드 k는 그래프 상에서 i, j를 제외한 모든 노드가 될 수 있기 때문에 3중 for문을 돌리..

플로이드 워셜개념정점 i에서 j까지 가는 최단 경로를 구할 때 중간 정점을 거쳐서 갈 수 있으면 거쳐서 가는 게 더 빠른지 확인하면서 최단 경로를 구하는 알고리즘임의의 경로 p에 중간 정점 k가 존재하면 k를 거쳐 가는 경로와 비교하여 더 작은 값으로 갱신하고, 중간 정점이 존재하지 않으면 아무 것도 하지 않는다.여기서 알 수 있는 특징은 거쳐갈 중간 정점이 여러 개가 될 수 있는데, 중간 정점 개수가 늘어날 수록 경로가 더 다양해지고 더 짧은 경로를 발견할 수 있는 확률이 늘어난다는 것이다.그리고 중간 정점 후보가 {1, 2, 3, ..., k} 이렇게 존재한다면 중간 정점을 단계적으로 확장해나가며 점점 더 정교한 최단 경로를 계산해나간다.즉 경로를 점점 확장해가면서 가능한 모든 조합을 다 비교하고 있..

3.4 정보 접근하기x86-64 cpu는 범용 레지스터 16개를 가지고 있다.정수 또는 포인터(주소)를 저장각 레지스터 크기는 64비트rdi, rsi, rdx, rcx, r8, r9 -> 함수 1~6번째 인자를 전달할 때 사용하는 레지스터rsp-> 함수 7~ 번째 인자를 전달할 때 사용하는 레지스터-> 7번째 인자부터는 stack을 통해 전달됨-> rsp를 스택 포인터라고도 함rax-> 함수 리턴값을 담는 레지스터현재 레지스터 형태로 오기 까지8086 cpu 시절에는 16비트짜리 레지스터 8개만 있었다.ax, bx, cx, dx, si, di, bp, sp IA32 cpu 시절에는 32비트짜리 레지스터로 바뀌었다.eax, ebx, ecx, edx, esi, edi, ebp, esp x86-64 cpu가 ..

3.1GCC 컴파일러GNU Compiler CollectionGNU에서 만든 컴파일러리눅스, 유닉스 계열 시스템에서 많이 사용됨C언어로 작성된 코드를 컴파일해서 실행 가능한 바이너리 프로그램으로 만들어주는 도구전처리(.c->.s) 컴파일 (.s->.i) 어셈블 (.i->.o) 링크 (.o->.exe)어셈블리 코드는 하드웨어에 의존적이다CPU 아키텍처 마다 해석할 수 있는 Instruction들이 각자 다름따라서 하드웨어에 맞게 어셈블리 코드로 변환시켜야 그 위에서 애플리케이션 실행 가능기계어 코드를 배워야 하는 이유?고급 언어의 추상화 계층으로 인해 감춰진 런타임 동작을 이해할 수 있음즉 Java와 같은 언어로는 보지 못하는 것들 (데이터가 어떻게 공유되고 있는지, 데이터가 정확히 어디서 어떻게 접근되고..

문제https://www.acmicpc.net/problem/12865풀이dp[i][j] = i개의 물건까지 고려했을 때 배낭 최대 허용 무게가 j인 경우 얻을 수 있는 최대 가치dp[i][j] = max(v + dp[i-1][j-w], dp[i-1][j])현재 물건을 넣어주고 남은 무게를 채울 수 있는 최대값을 이전 물건 값에서 가져와 더해주거나,현재 물건이 아닌 이전 물건으로 채우는 것 중에서 더 큰 값을 넣어줌코드import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedRead..

문제https://www.acmicpc.net/problem/9251두 문자열의 LCS(Longest Common Subsequence, 최장 공통 부분 수열)을 구하는 문제풀이 1 - 재귀 + dpa와 b는 배열 형식으로 주어졌다고 가정l(i, j)는 a(0..i), b(0..j) 사이의 lcs 길이로 정의l(i, j)의 재귀적인 구조를 찾기두 문자열을 탐색하다가 다른 문자가 나오면a[k]값을 무시하고 a[k+1], b[k]부터 다시 lcs 탐색하거나b[k]값을 무시하고 a[k], b[k+1]부터 다시 lcs 탐색하기-> 두 분기 중 매칭 수가 더 많은 부분을 리턴같은 문자가 나오면 a[k], b[k]값이 같으므로 a[k+1], b[k+1]부터 계속 lcs 탐색하고 그 결과에 1을 더해준 후 리턴bas..

Divide & Conquer분할정복 방식의 대표적인 예 : merge sort둘로 나눔 (나눈 문제들은 원래 문제와 같은 입려값을 가져야 함)각각 정렬합침최댓값 찾기를 분할 정복 방식으로 구현해보자배열 A를 두 부분 배열 A1, A2로 나눔 -> 나눌 때 부분 배열 각각이 다시 최대값 찾는 단계로 재귀호출될 것이라고 생각하기그리고 원래 문제를 다시 생각해봄-> A1의 최댓값, A2의 최댓값 둘 중 더 큰 값이 A의 최댓값이다.슈도코드 :max(a[0...n-1])if n=1 return a[0]mid m2 then return m1 else return m2 //참고 : 재귀호출의 시간 복잡도 : T(n) = 2T(n/2) + O(1) // 재귀호출에서 사용되는 시간 (T로 표현. 인스턴스..

챗지피티 사용 방법??지피티를 사용해서 코드를 짠다고 해서 내 코드 스타일이 지피티처럼 바뀌는 게 아니다. 관점을 달리하면 지피티는 그냥 도구로 활용되는 거임지피티의 코드를 가져다쓰기 x내가 탐구하고자 하는 부분이나 의문점들을 최대한 상세히 질문할 수 있다는 것이 지피티의 장점이므로 이를 잘 활용하자그러기 위해서는 먼저 내가 그 내용에 대해 잘 알아야 지피티에게 최대한 상세히 물어볼 수 있음멘탈 극복 방법?내 능력의 기대치는 높은데 내 실력이 그 정도에 미치지 못할 때 좌절감이 올 수 있다.나의 현재 능력을 인정하고 앞으로 나아가는 것이 중요진짜 코치님이 이 말씀 해주실 때 혼자 눈물 고였음 이번 주는 정말 힘들었다. 완전 탐색 자체는 어느정도 이해하고 있어서 딱 완전탐색만 하도록 요구하는 문제들은 괜찮..