코딩 공부하는 코딩류

정수가 주어질 때 주어진 정수를 1, 2, 3의 합으로 나타낼 수 있는 경우의 수를 구하는 문제 문제의 조건 1. 합을 나타낼 때엔 1개 이상의 수를 사용해야 한다. 정수 4를 1, 2, 3의 합으로 나타낸다면 다음과 같은 방법들로 나타낼 수 있다. 1+1+1+1 1+1+2 1+2+1 2+1+1 2+2 1+3 3+1 2. 주어지는 정수는 양수이며 11보다 작다. 즉 1 ~ 10 사이 숫자만 나온다. 3. 첫째줄에 테스트 케이스의 갯수 T가 주어지며 다음 줄부터 T 갯수만큼 한 줄마다 정수가 주어진다. 풀이 과정 DP를 연습하려고 푼 문제인데 아직 DP를 잘 못 해서 문제를 봤을 땐 당연히 풀이가 떠오르지 않았습니다. 그래서 또 구글링... 후 알게 된 이 문제의 풀이법 1-1. 정수 1을 만들 수 있는 ..

비가 내렸을 때 물에 잠기지 않을 지역의 최대 갯수를 구하는 문제 문제의 조건 1. 어떤 지역의 높이 정보가 위와 같이 주어진다. 2. 비가 4만큼 오면 위와 같이 높이가 4 이하인 지역은 모두 물에 잠긴다. 3. 이 때 하얀 부분을 물에 잠기지 않는 안전 영역이라 할 수 있는데 같은 안전 영역의 범위는 상하좌우로 맞닿은 영역들만 포함한다. 즉 이런 경우처럼 대각선 방향으로 맞닿아 있는 영역은 같은 안전 영역이라 할 수 없다. 2번의 경우에서 안전 영역의 갯수는 5개이다. 4. 6만큼 비가 와서 높이가 6 이하인 지역이 모두 물에 잠긴다면 위와 같이 나타낼 수 있다. 이 때 안전 영역의 갯수는 4개이다. 이 지역에서 비가 오는 양 별로 안전 영역의 갯수를 모두 확인해 봤을 때 최대 갯수는 5개이다. 5...

알고리즘 문제 풀다가 급 궁금해져서 찾아본 find와 find_if의 차이점 1. find, find_if 둘 다 algorithm 헤더에 정의되어 vector 안에 특정 값이 존재하는지 찾아주는 함수입니다. 하지만 find는 찾고자 하는 값의 타입에 operator== 가 정의되어 있어야 사용가능하고 그렇지 않다면 find_if에 비교식을 만들어 넣어야 한다는 점이 다르다고 볼 수 있습니다. 이렇게만 적으면 무슨 소리인가 싶으실 테니 각 함수의 정의를 보겠습니다. find template InputIterator find(InputIterator first, InputIterator last, const T& val); 맨 마지막 val 인자의 타입 T에 operator== 가 정의되어 있어야 사용 가..

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다. 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 입력 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 ..

주어진 수를 1로 만드는 데 필요한 최소 연산 횟수를 구하는 문제 문제의 조건 1. 1보다 크거나 같고 10^6보다 작거나 같은 정수 N이 주어진다. 2. 정수 N에 사용할 수 있는 연산은 3가지이다. 1) 3으로 나누어 떨어지면 3으로 나눈다. 2) 2로 나누어 떨어지면 2로 나눈다. 3) 1을 뺀다. 3. 위 세 가지 연산을 적절히 사용할 때 주어진 N을 1로 만들 수 있는 최소 연산 횟수를 구해서 출력하기 풀이 과정 아직 DP를 잘 몰라서 문제를 봐도 감이 잘 안 와서 풀이를 찾아봤습니다. 여러 블로그를 보고 이해한 풀이 1. DP 중에서 타뷸레이션(상향식 접근) 방식을 사용해 배열 인덱스에 해당 값을 1로 만드는 데 필요한 연산 횟수를 기록한다. 각 숫자별로 필요한 연산 횟수를 기록할 1차원 배열..

지도에 표시되어 있는 섬의 개수를 세는 문제 문제의 조건 1. h의 높이 x w의 너비 크기를 가진 지도가 주어진다. 2. 2차원 지도 배열에는 0과 1로 표시가 되어 있다. 0은 바다, 1은 땅이라는 뜻 3. 2차원 배열의 각 땅들은 상하좌우 대각선으로 연결되면 하나의 섬이라고 할 수 있다. 4. 여러 테스트 케이스가 주어질 때 각 테스트 케이스의 섬의 갯수를 구해서 출력하기 5. 입력의 마지막 줄에는 0 0 이 주어진다. 입력받은 w와 h가 둘 다 0이라면 테스트 케이스 입력받기 종료하고 프로그램도 종료 풀이 과정 BFS로 상하좌우에 연속되어 있는 같은 숫자 갯수 세던 문제에서 대각선 방향만 추가해서 풀면 될 거 같아서 기존 BFS 코드에 대각선 방향만 추가해서 풀었습니다. 1. 방향 확인용 배열에 ..

가장 마지막 마을까지 가는데 필요한 최소 주유 금액을 구하는 문제 문제의 조건 1. 도시의 개수 N이 주어진다. 도시들은 일직선상에 있기 때문에 무조건 맨 앞 도시부터 차례대로 가야 한다. 2. 처음엔 차에 기름이 없기 때문에 맨 처음 도시에서 기름을 넣고 출발해야 한다. 기름통의 크기에는 제한이 없다. 도시 간 도로를 이용하여 이동할 때 1km당 1리터를 사용한다. 3. 각 도시에는 주유소가 하나씩 있으며 각 도시마다 기름 가격이 다를 수 있다. 그렇기 때문에 다른 도시보다 기름 가격이 싼 도시에서 최대한 넣고 가는 것이 이득이다. 4. 각 도시에 있는 주유소의 리터당 기름 가격과 각 도시 간 거리가 주어질 때 마지막 도시까지 가는데 필요한 최소 주유 금액을 구해서 출력하기 풀이 과정 처음엔 기름이 없..

방향이 없는 연결 그래프에서 서로서로 연결된 덩어리가 몇 개인지 구하는 문제 문제의 조건 1. 첫째 줄에 N개의 정점을 가진 양방향 연결 그래프와 M개의 간선이 주어진다. 2. 둘째 줄부터 간선의 양 끝점이 주어진다. 3. 서로 연결된 요소가 몇 개인지 출력 풀이 과정 앞전에 풀었던 컴퓨터 바이러스 문제처럼 몇 개의 정점이 간선을 통해 서로 연결되어 있는지 확인하면 될 거라고 생각했습니다. 연결 요소라는 말이 헷갈렸는데 질문 게시판 보니까 컴퓨터 바이러스 문제처럼 간선으로 서로서로 연결된 것들을 한 덩어리로 치는 것이 맞더라고요. 풀이 1. 양방향 그래프를 만든 뒤 BFS로 현재 정점에서 방문할 수 있는 곳들을 모두 방문한다. 2. 1번 과정이 끝나고 나면 한 연결 요소(덩어리) 탐색이 끝난 것이기 때문..