알고리즘10

• [백준(baekjoon)] 피보나치 함수 (C/C++) 문제 링크 : www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 그렇게 어려운 문제는 아닌 것 같은데 문제 번호가 앞 번호다 보니 정답률이 낮은 것 같다. pair를 써서 first는 0을 출력한 횟수, second는 1을 출력한 횟수로 사용하여 문제를 풀었다. fibonacci 0번째 1번째는 입력해 주고 2번째 부터는 index-1 index-2 위치의 값을 더해주어 먼저 40번째까지 선 계산 후에 입력 값을 받아 출력해 주었다. #include using namespace std; pair fibonacci[41]; int main() { fibona.. 알고리즘 2021. 1. 14.

• [백준(baekjoon)] 1012번 유기농배추 (C/C++) 가로 길이(M), 세로 길이(N) 만큼 Map을 돌면서 visit하지 않은 곳에서 부터 dfs를 돌려가면서 갯지렁이의 수를 세었다. 즉, 전체 Map에서 dfs를 몇번 수행했나를 세면 된다. #include #include using namespace std; int map[51][51]; bool visit[51][51]; int M, N; int dx[4] = {0, -1, 0, 1}; int dy[4] = {1, 0, -1, 0}; bool isRange(int x, int y) { return 0 count; for(int testCase = 0 ; testCase > M >> N >> cabba.. 알고리즘 2021. 1. 14.

• [프로그래머스] 쿠키 구입 (C/C++) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/49995 코딩테스트 연습 - 쿠키 구입 과자를 바구니 단위로 파는 가게가 있습니다. 이 가게는 1번부터 N번까지 차례로 번호가 붙은 바구니 N개가 일렬로 나열해 놨습니다. 철수는 두 아들에게 줄 과자를 사려합니다. 첫째 아들에게는 programmers.co.kr 딱히 어려운 점은 없었고 부분합의 개념을 사용했다. #include #include using namespace std; int sum[2001]; int solution(vector cookie) { int answer = 0; int cookieSize = cookie.size(); for(int index = 0; index < cookieSize;.. 알고리즘 2021. 1. 2.

• [프로그래머스] 여행경로 (C/C++) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]] [ICN, ATL, ICN, SFO, ATL, SFO] programmers.co.kr 전형적인 DFS 방식으로 문제를 풀었다. visited를 tickets+1의 크기만큼 만들고 visited와 answer를 참조로 받아 DFS 방식으로 돌렸다. #include #include #include #include using namespace std; bool dfs(string here, vector& visited, vector tickets, vector& answer.. 알고리즘 2020. 12. 30.

• [프로그래머스] 줄 서는 방법 (C/C++) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/12936 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 처음에는 next_permutation 함수를 이용해서 처음부터 순서대로 구했더니 시간초과가 났다. 그래서 맨 앞에 오는 숫자는 팩토리얼 값으로 k값을 나눴을 때 나오는 몫과 나머지를 이용해서 최대한 k의 크기를 줄여 나갔다. 배열의 길이가 5가 될 때 k줄이기를 멈추고 next_permutation으로 순열을 순차적으로 만들어서 값을 찾아내었고 .. 알고리즘 2020. 12. 22.

• 

  [프로그래머스] 멀쩡한 사각형 (C/C++) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/62048 코딩테스트 연습 - 멀쩡한 사각형 가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 programmers.co.kr 위 사진은 문제의 예시이다. 처음에는 규칙을 찾기 위해 고민을 했다. 그러다 똑같은 형태의 다각형이 반복된다는 것을 알아냈고 가로길이(W)와 세로길이(H)의 최대공약수만큼 반복 된다는 것을 알게 되었다. 그래서 다각형 한개를 기준으로 봤을때 몇개의 사각형이 포함되는지를 계산하고 거기에 최대공약수를 곱하면 되겠다고 생각했다. 위의 예시는.. 알고리즘 2020. 12. 21.

• [프로그래머스] 도둑질 (C/C++) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/42897 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 첫번째로 생각해야 할 것은 첫번째 집을 털었냐 이다. 원형이기 때문에 마지막집과 첫번째집이 붙어있기 때문이다. 그래서 cache를 2차원배열로 1000000 x 2로 선언해주었다. 어떤 index의 집에 도착했을 때 이집을 털거나 안털거나로 두가지 선택이 존재한다. 턴다면 이번 index의 cost에다가 index+2 위치로 dp를 이어나가고 안턴다면 index+.. 알고리즘 2020. 12. 20.

• [프로그래머스] 가사 검색 (C/C++) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/60060 코딩테스트 연습 - 가사 검색 programmers.co.kr 처음에는 정규표현식으로 다음과 같은 코드로 간단하게 풀었었다. #include #include #include using namespace std; vector solution(vector words, vector queries) { vector answer; for(auto query : queries) { string statement = ""; for(auto character : query) { if('a' count; } } return temp; } if(next[cur] == NULL) { return 0; } if(*(key+1.. 알고리즘 2020. 12. 19.

• [프로그래머스] 4단 고음 (C++) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/1831 코딩테스트 연습 - 4단 고음 4단 고음 I'm in my dream~↗ ~↗ ~↗ IU는 본인의 장기인 3단 고음으로 유명하다. 그러던 그녀가 어느 날 4단 고음을 성공했고 그녀의 고음은 학계에서 연구가 될 만큼 유명해졌다 [1]. [1] 견두헌, 배명 programmers.co.kr #include using namespace std; int treble(int n, int plusCnt) { int result=0; // log(n)/log(3) = *의 개수 if(n < 1 || 2 * log(n) / log(3) < plusCnt){ return 0; } // 마지막은 음높이3이고 ++이어야함 i.. 알고리즘 2020. 12. 18.

• 

  [프로그래머스] 3 x n 타일링 (C++) 문제 링크 : programmers.co.kr/learn/courses/30/lessons/12902 코딩테스트 연습 - 3 x n 타일링 programmers.co.kr 세로길이는 3으로 고정이므로 가로길이가 2일 때 경우의 수는 3가지 가로 길이 2가 추가될 때 A : 전 단계의 경우의 수 x 3 B : 위 그림과 같이 짝수 지점을 직사각형이 끼고 있을 때 2가지 경우의 수 A와 B를 생각하면서 수식을 만들어보면 가로 길이 0일 때(d[0]) : 1 이라고 가정하자 가로 길이 2일 때(d[2]) : 3 x d[2 - 2] + 2 x 0 가로 길이 4일 때(d[4]) : 3 x d[4 - 2] + 2 x d[2 - 2] 가로 길이 6일 때(d[6]) : 3 x d[6 - 2] + 2 x d[4 - 2].. 알고리즘 2020. 12. 18.