전체 글

📌 - 동적 메모리 할당 메모리를 할당하는 방법에는 정적으로 할당하는 정적 할당과 동적으로 할당하는 동적 할당이 있다. 정적할당은 이때까지 계속 사용해왔던 int arr[100]과 같은 고정된 크기의 배열을 정적할당이라고 한다. 그렇다면, 잘 사용하고 있는 배열을 사용하지 않고 동적할당을 사용하는 이유가 무엇일까?? 👉 - 정적배열은 처음 생성할 때 크기가 고정되어 있으며, 이러한 문제 때문에 고정된 크기보다 더 큰 입력이 들어오게 된다면 index 에러가 나타나게 되고, 더 작은 입력이 들어오게 되면 남는 만큼 메모리를 사용하지 않아 메모리 낭비로 이어지게 된다. 이런 문제를 해결하기 위해서 동적할당이란 개념을 사용한다. 동적 할당이란? 실행 시간동안 사용할 공간을 동적으로 할당하는 것 사용이 끝난 뒤..

https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 📌 - 문제 해결 방법 구해야 하는 횟수가 10만이기 때문에 시간초과가 날 수 있기 때문에 DP로 문제를 해결해야한다. 먼저 해당하는 전체 구간의 합들을 DP배열에 갱신을 한다. 해당하는 구간의 합을 구하는 방법은 해당하는 칸의 구간합 -> dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + arr[i][j] 구한..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 📌 - 처음 접근한 방법 내리막이 나올때마다 그 칸의 값을 다음 내리막 칸의 값에 더해준다 모든 경로를 전부 탐색해서 마지막 칸의 값을 출력 이렇게 브루트포스로 풀었었는데, 바로 메모리 초과가 났다 📌 - 두번째 접근 방법 시간초과와 메모리초과를 동시에 해결하려면 DFS만으로는 풀 수가 없다. DFS나 BFS를 사용하면서 DP개념을 활용해야 이 문제를 해결 할 수 있다. DFS로 경로의 끝까지 ..

https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📌 - 무인도 여행 - 접근 이 문제는 map의 크기도 100으로 제한되어 있고, 상,하,좌,우를 이용하면서 해당하는 경로의 숫자를 전부 더해주는 방식이라 DFS, BFS 문제라고 생각했고 백준의 안전 영역이나 빙산 문제와 비슷하다고 생각해서 BFS로 풀었다. 0,0부터 N,M까지 전부 탐색하면서 방문체크 방문하지 않은 섬일때 BFS를 이용해서 인접한 섬들의 수를 더해주고 다시 방문체크 인접한 ..

📌 - G5_12865_평범한 배낭 문제 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net DP문제를 풀기 시작했는데, 계속 머리를 굴려봐도 풀이법이 생각나지 않아서 다른 사람들 풀이를 참고했다. 이때까지는 2차원 배열을 컨트롤 할 때 i,j를 이용해서 i,j의 값에 맞는 칸을 업데이트 시켜주는 느낌이었는데, DP는 여러 문제들을 보다보니 i,j로 컨트롤 하긴 하지만 , 아래의 예..

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 해당 문제는 전에 푼 토마토 문제와 매우 유사하다. 본인이 푼 해결 방식은 이러하다 - 이 문제는 결국 낮은 숫자의 바이러스들부터 큰 숫자의 바이러스들까지 순서대로 퍼지게 만드는 것이 요점인데 순서를 정렬하기 위해 힙큐를 써서 해결을 했다. for 문으로 전체 배열을 돌면서 0이 아닌 바이러스들을 힙큐에 넣는다. 1초마다 BFS로 힙큐를 비우면서 인접한 배열의 정보를..