위 문제는 원하는 인원수를 최소 비용으로 구하는 방법을 요구하는 문제입니다. 제 풀이는 다이내믹 프로그래밍을 사용해서 풀었고 이 문제를 구현할 때는 "이때, 호텔의 고객을 적어도 C명 늘이기 위해 형택이가 투자해야 하는 돈의 최솟값을 구하는 프로그램을 작성하시오." 문장을 잘 확인해야 합니다. 예제 2번같은 경우를 보면 dp [10]을 구해야 하지만 dp [3]=1 , dp [6]=2, dp [9]=3이 될 때 dp [10]은 4로 구해지는 것을 봤을 때 뒤에 부분까지 구하고 최솟값을 구한다고 생각하면 됩니다. 따라서 범위는 구하고자하는 C의 범위에 배열 arr의 최대 인원값을 더해준 범위까지 구한 것의 최솟값을 구하면 됩니다. 전체 코드 from sys import stdin as s s=open('i..

이 문제를 처음 봤을 때 정렬돼있는 부분과 입력값의 범위가 큰 것을 보고 그리디 알고리즘을 활용해야 하는 부분까지는 접근하였는데 아무리 생각해도 한번의 탐색을 통해 값을 구할 수 있는 방법을 찾지 못했습니다. 친구의 설명을 통해 문제에 대한 접근 방법을 알 수 있었고 DP와 그리디는 방법만 알면 구현하기는 정말 쉬운데 그 방법을 생각하는 과정이 어려운 것 같다. 우선 이 문제는 K개의 조가 1이라고 가정하면 1 3 5 6 10에서 (10-1)로 값은 9가 나온다. 하지만 K가 2라고 생각하면 2개의 조로 나눠야하는데 이때 (1 3 5 6) | (10)으로 나눈 값이 최솟값을 의미한다. 이는 앞 뒤의 차가 가장 큰 부분을 나누면 조를 나눴을 때 가장 큰 값을 갖게 된다는 것을 의미한다. 그래서 한번의 fo..

이 문제는 구현문제로 그래프 탐색과 더불어서 풀었습니다. 처음에는 미세먼지가 확산하는 부분까지는 기존 bfs문제들과 비슷해서 작성할 수 있었는데 이 문제에서는 공기청정기 윗 부분과 아랫 부분을 나눠서 한칸씩 밀려나가는 것을 구현하는 부분이 어려웠습니다. 머릿속으로는 벽에 부딪히면 방향을 전환하고 값들을 하나씩 이동시키는 형식으로 구현하면되겠다라고 생각은 드는데 막상 구현을 하자니 어디서부터 어떻게 구현해야하는지가 어려웠던 것 같습니다. R,C,T = map(int,s.readline().split()) arr = [list(map(int,s.readline().split())) for _ in range(R)] #로봇의 위치 저장하는 배열 machine=[] #미세먼지 누적 합 저장 result=0 #동..

동적 메모리 할당기를 만드는 이유? - 동적 메모리 할당을 하지 않는다면, 배열을 정해진 최대 배열 크기를 갖는 정적 배열로 정의할 것이다. 작은 프로그램에서는 이 방법이 크게 문제가 되지 않을 수 있지만 코드 길이가 길어질수록 사용자가 많은 규모의 소프트웨어라면 정적배열 선언은 관리가 어려워집니다. - 이 어려움을 해결하기위해 런타임시 메모리에 데이터를 동적으로 할당해야 합니다. 할당기에는 아래와 같이 크게 2종류가 있습니다. 명시적 할당기(Explicit Allocator) : 명시적 할당기는 프로그래머가 직접 메모리를 할당하고 해제하는 방식을 의미합니다. 프로그래머는 메모리를 동적으로 할당하기 위해 할당하는 함수(malloc) 해제하는 함수(free)를 호출해야 합니다. 묵시적 할당기(Implici..

1.동적 메모리 할당이란? - 프로세스는 더 큰 메모리를 할당해서 사용할 수 있도록 힙(Heap)영역을 제공한다. - 힙영역은 지역변수와 매개변수등을 저장하는 스택(Stack)영역과 달리 실행시점에 원하는 크기만큼 메모리를 할당할 수 있습니다. - 메모리 사용이 끝나면 언제든지 할당한 메모리 공간을 해제할 수 있습니다. 1.1 malloc - 힙은 스택처럼 관리되는 공간이 아니라서 변수를 선언하는 행위로 메모리를 할당할 수 없습니다. 그렇기 때문에 C 표준 함수인 malloc과 free를 통해서 메모리 할당 및 해제 해야합니다. - 함수 원형 void *malloc(size_t size); /* size_t는 unsigned int와 같음 */ - void*를 사용하면 형 변환을 해야하는 불편함이 있기 ..

지난번 RB-TREE 구현을 마치고 이제 c언어 2주 차인 동적메모리할당과 관련된 malloc, calloc, realloc에 대해서 공부하고 있다. 주어진 테스트 코드를 테스트해 보려면 메인코드를 구현해봐야 하는데 각 주가 시작되고 나서는 선뜻 코드를 이해하기가 너무 어려운 것 같은 느낌이 든다.. 그래도 뭔가 주어진 기간 안에 이것을 끝내야 한다는 생각 때문에 기간을 맞춰서라도 끝내게 되는 것 같다. 오늘 malloc-lab 관련해서 책을 읽다가 같은 팀원들끼리 모르는 부분을 얘기하고, 각각의 팀원들이 모두 백엔드 스프링을 하고 싶어 하는 공통점이 있어 객체지향 관련 정보에 대해서 얘기를 나누는 시간을 가졌다. 팀원들과 얘기를 나눠보니 내가 알고 있는 지식은 너무 보잘것없다고 느꼈고 새로 배워야 할 ..

문제 링크 : https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 풀이과정 이 문제는 그래프 탐색, bfs, 브루트 포스 알고리즘, 백트래킹 등 여러개의 알고리즘이 섞여있는 문제이다. 우선 어느 경우의 수에서 최대 안전 영역의 개수가 나오는지 모르기 때문에 모든 경우를 탐색하는 수 밖에 없다. 배열의 첫번째부터 벽을 세워나가서 벽의 개수가 3개가 됐을 때 bfs를 실행하고 바이러스를 전염 시키고 나서 안전 영역의 개수를 카운터해서 저장해놓고 제일 큰 값을 나중..

이 문제를 처음 봤을 때 지문을 잘못이해해서 왼쪽으로90도 회전하고 이동하고를 같은 자리를 무한 반복하는 줄 알았다.. 질문 게시판을 가보니 나와 같은 문제를 갖고 있는 사람들이 많아서 질문을 읽고 이해를 하게되었습니다. 우선 문제의 풀이방법을 생각해보면 dfs,bfs 방식으로 접근할 수 있고 제가 풀이한 방식은 dfs의 방식을 사용했습니다. N,M = map(int,s.readline().split()) r,c,d = map(int,s.readline().split()) cnt=0 #북동남서순서 dx=[-1,0,1,0] dy=[0,1,0,-1] arr = [list(map(int,s.readline().split())) for _ in range(N)] dfs(r,c,d) 처음 주어진 방향의 값이(d)..