본문 바로가기

Tech67

🐨BOJ#1697 숨바꼭질]🙄BFS(feat. collections) 문제 보기 https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 풀이 아이디어 딱 봐도 dp로 풀 수 있을 것 같지만... 머리가 아파서(=어려워서) 수빈이가 도착할 수 있는 위치가 분기로 갈라지는 트리를 만들어서 풀기로 했다. 가장 적은 횟수(빠른 시간)에 동생을 찾아야 하기 때문에, 트리의 깊이가 가장 얕은 게 정답이다. 그래서 dfs로 탐색한 뒤 깊이를 비교하는 것 보다 bfs를 사용해야 한다고 생각했다. 그리고 분기.. 2024. 3. 29.
C언어 고급] 🚀배열과 포인터 목차 A. 배열과 포인터의 관계 1. 배열명으로 배열 요소 사용하기 2. 배열명 역할을 하는 포인터 3. 배열명과 포인터의 차이 3. 포인터의 뺄셈과 관계 연산 B. 배열을 처리하는 함수 1 . 배열의 값을 출력하는 함수 2 . 요소 개수가 다른 배열도 출력하는 함수 3 . 배열에 값을 입력하는 함수 3 . 배열에 값을 입력하는 함수 C. 정리 하기 1 . 요약 2 . 활용 3 . 궁금한 점 A. 배열과 포인터의 관계 -컴파일러는 첫 번째 배열의 주소를 쉽게 사용하도록 배열명을 컴파일 과정에서 첫 배열 요소 주소로 바꿈. 자료형에 따라 첫 주소에서 크기만큼 건너뛰며 요소에 접근 가능. ____1. 배열명으로 배열 요소 사용하기 - 주소는 정수처럼 보이지만 자료형 정보를 갖고 있는 특별한 값. = 자유로운.. 2024. 3. 28.
🐨백준-파이썬] 2630번 색종이 만들기& 1780번 종이의 개수🤔분할 정복 알고리즘(Divide and conquer algorithm) https://namu.wiki/w/%EB%B6%84%ED%95%A0%20%EC%A0%95%EB%B3%B5%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 분할 정복 알고리즘 분할 정복(Divide and Conquer)은 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크 namu.wiki https://ko.wikipedia.org/wiki/%EB%B6%84%ED%95%A0_%EC%A0%95%EB%B3%B5_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98 분할 정복 알고리즘 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를.. 2024. 3. 27.
🐨백준-파이썬]# 13305번 주유소(그리디 알고리즘) 이 문제는 그리디인 것을 알겠다. 지금까지 나온 최저가를 경신해가면서 다음도시까지 주유하면 된다. 어차피 더 좋은 대안이 있어도 도착해야 닿을 수 있으니 지금까지의 최대 이익만 생각하면 되는 문제라고 할 수 있다. 1. 유가경신 2다음도시 이동(거리와 곱해서 가격에 더하기) ''' 4 2 3 1 5 2 4 1 ''' n = int(input()) distance = list(map(int, input().split())) oil_price = list(map(int, input().split())) best_price = float('infinity') cost = 0 for i in range(n-1): if oil_price[i] < best_price: best_price = oil_price[i].. 2024. 3. 25.
🐨백준 파이썬]# 1541번-잃어버린 괄호(그리디 알고리즘) "-" 뒤에 있는 수는 모두 더한다. eval을 쓰면 00009같은 것 때문에 에러가 난다. def calc(exp): return sum(map(int,exp.split("+"))) expression = input() if "-" in expression: a = expression.split("-") front = calc(a[0]) back = [calc(x) for x in a[1:]] result = front - sum(back) else: result = calc(expression) print(result) 그리디라고 하는데.... 이렇게밖에 방법이 안 떠오른다 ㅠㅠ 이게 왜 그리디인지 알아보자. 주어진 코드는 먼저 입력된 수식에서 "-" 기호를 기준으로 분리하여, 각 부분의 합을 계산한.. 2024. 3. 24.
🐨알고리즘] 비트 필드를 활용한 다이나믹 프로그래밍 비트 필드를 활용한 다이나믹 프로그래밍 다이나믹 프로그래밍은 복잡한 문제를 더 작고 관리 가능한 부분 문제로 나누어 해결하는 방식입니다. 이 방법은 문제의 중복 계산을 피함으로써 효율적인 문제 해결이 가능하게 합니다. 하지만, 많은 다이나믹 프로그래밍 문제는 상태 공간의 크기가 크기 때문에, 메모리 사용량이 문제가 될 수 있습니다. 여기서 비트 필드를 사용하면 상태를 효율적으로 표현하고 메모리 사용을 줄일 수 있습니다. 비트 필드란? 비트 필드는 데이터를 비트 단위로 표현하는 방법입니다. 각 비트는 0 또는 1의 값을 가질 수 있으며, 여러 상태나 플래그를 하나의 정수로 표현할 수 있습니다. 이는 메모리를 절약하고, 비트 연산을 통해 빠르게 데이터를 처리할 수 있는 장점이 있습니다. 비트 연산의 기초 비.. 2024. 3. 24.
C 언어 기본] 포인터 목차 A. 포인터의 기본 개념 1. 메모리의 주소, 주소연산자 2. 포인터와 간접 참조 연산자 3. const를 사용한 포인터 B. 포인터 이해하기 1. 주소와 포인터의 차이, 크기 2 . 대입규칙 3 . 사용 이유 C. 요약 및 정리 1 . 요약 2 . 문제풀이 3 . 궁금한 점 A. 포인터의 기본 개념 {선언된 블록 내부에서만 사용할 수 있는 스코프 규칙}을 벗어나 데이터 공유 가능한 포인터 ____1. 메모리의 주소, 주소 연산자 - 주소값은 바이트 단위로 구분. 0부터 바이트 단위로 1씩 증가. 2바이트 이상의 크기를 갖는 변수는 여러개의 주소값에 걸쳐 할당. int a; //메모리 100번지부터 할당되었다면 100~103까지 4바이트에 걸쳐 할당됨. 변수 선언 이후에는 4바이트 전체를 a라는 이.. 2024. 3. 23.
C언어 기본] 배열 목차 A. 선언, 사용 1. 선언, 사용, 초기화 2. 반복문 3. sizeof연산자 활용한 배열처리 B. 문자를 저장하는 배열 1. char형 배열-선언 초기화 2 . 문자열 대입 3 . 전용 입출력 함수:gets,puts C. 정리하기 1 . 요약 2 . 문제풀이 3 . 궁금한 점 A. 선언, 사용 ____1. 선언, 사용, 초기화 int ary[5]; // 4바이트 * 5 배열 선언 ary[0] = 10; //사용할 때(첫번째 요소를 10으로) scanf("%d",&ary[3]); //키보드로부터 입력받아 4번째 요소에 저장 값을저장하지 않으면 가비지 값이 출력, int ary[5] ={1,2,3,4,5}; //선언과 동시에 초기화, 중괄호로 묶어서. int ary[5] ={1,2,3}; // 왼ㅉ.. 2024. 3. 22.
🐨그리디 알고리즘 그리디 알고리즘 그리디 알고리즘은 최적해 찾기에 사용되는 알고리즘으로, 각 단계에서 순간적으로 최적으로 보이는 선택을 하는 근시안적 방법을 사용한다. 이 방법은 선택을 수집해 전역적인 답을 만들어 내지만, 이 전역적인 답이 항상 전역적 최적해와 같다는 보장은 없다. 그리디 알고리즘은 주로 탐욕스런 선택 조건과 최적 부분 구조 조건을 만족할 때 잘 작동한다. 만약 이 조건들을 만족하지 않는다면, 근사 알고리즘으로서의 역할을 할 수 있다. 정의 탐욕스런 선택 조건 (Greedy Choice Property) 이전의 선택이 이후의 선택에 영향을 주지 않는다. 최적 부분 구조 조건 (Optimal Substructure) 문제의 최적해가 그 문제의 부분 문제에서도 최적해가 된다. 잘 되는 예: 거스름돈 문제 (.. 2024. 3. 19.
클러스터를 만들 겁니다.JPG 라즈베리파이 4대 입니다. 허브 노드용의 8기가램이 한 대 있고 5V5A전원 공급기도 6개( COK-4511P 인지텔레콤) 스위칭 허브 8소켓짜리도 준비완료 클러스터용 랙도 준비완료 POE는 안 할거고.... (iot멀티탭만 있으면 되는데 유선랜이 들어가는 IOT랜은 없을까요?) 2024. 3. 14.
C언어 기본] 01 프로그램 만들기 void 요약(혼공C) { C는 UNIX에서 쓰려고 개발; 컴파일 = 소스코드→컴파일러 → 기계어의 과정을 말한다; 비주얼 스튜디오는 컴파일러의 일종이라고 나와 있다. (내 생각엔 여러 컴파일러를 포함한 IDE 같다.); 유용한 단축키 Ctrl+Shift+B(컴파일) Ctrl+F5(실행) (소스)전처리(전처리 소스)컴파일(목적파일)링크(실행파일) } void 예시(검색 결과, Chat GPT) { #include int main() { printf("Hello, World!\n"); return 0; } 이 프로그램은 표준 출력에 "Hello, World!"를 출력합니다. 각 단계별로 파일이 어떻게 변화하는지 살펴보겠습니다. 1. 전처리(Preprocessing) 단계 목적: 소스 코드에서 #includ.. 2024. 3. 4.
10844번 쉬운 계단 수 동적 계획법(Dynamic Programming)을 사용해서 문제를 해결해 보자. 길이가 n이고 마지막 숫자가 0에서 9까지 각각인 계단 수의 개수를 dp[n][last]라고 할 때, (dp[1][0] = 0) (길이가 1이고 마지막 숫자가 0인 계단 수는 없다.) (dp[1][i] = 1) (1 2024. 3. 3.