반응형

분류 전체보기 286

[프로그래머스 42898] 등굣길 C++

문제 프로그래머스 42898 등굣길 C++ 코딩테스트 연습 - 등굣길 계속되는 폭우로 일부 지역이 물에 잠겼습니다. 물에 잠기지 않은 지역을 통해 학교를 가려고 합니다. 집에서 학교까지 가는 길은 m x n 크기의 격자모양으로 나타낼 수 있습니다. 아래 그림은 m = programmers.co.kr 풀이 해당 좌표가 웅덩이인지 저장하는 water배열을 선언하고, 웅덩이 좌표를 넣어줍니다. 그 이후에는 일반적인 길찾기 처럼 DP를 이용하되, 웅덩이일 경우에는 경로를 계산하지 않고 넘어갑니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 #include #includ..

[프로그래머스 43105] 정수 삼각형 C++

문제 프로그래머스 43105 정수 삼각형 C++ 코딩테스트 연습 - 정수 삼각형 [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30 programmers.co.kr 풀이 지금까지의 경로의 합 중 최댓값을 저장해놓은 배열을 DP라고 선언합니다. DP는 다음과 같은 규칙을 따릅니다. 1. 줄의 첫 칸 일 경우 : 자신의 DP값 = 전 줄의 첫 칸의 DP값 + 자신의 값 2. 줄의 마지막 칸 일 경우 : 자신의 DP값 = 전 줄의 마지막 칸(j-1)의 DP값 + 자신의 값 3. 그 외의 경우 : 자신의 DP값 = 전 줄의 j-1, j번째 DP값 충 더 큰 값 + 자신의 값 삼각형의 값은 0이상이므로 마지막 줄인 경우에만 최댓값을 갱신해주면 됩니다. 소스 코..

[프로그래머스 43162] 네트워크 C++

문제 프로그래머스 43162 네트워크 C++ 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 풀이 BFS를 사용합니다. 1. 네트워크에 방문해, 인근 네트워크를 모두 방문 처리 해줍니다. 2. N번째 네트워크까지 반복하면서, 그 네트워크를 방문하지 않았다면 1과정을 반복합니다. 3. 총 네트워크의 개수를 return 합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..

[프로그래머스 43165] 타겟 넘버 C++

문제 프래그로머스 43165 타겟 넘버 C++ 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 풀이 BFS를 사용했습니다. 첫 숫자의 음수 값, 양수 값을 queue에 push 해주고 queue에서 하나씩 꺼내며 양수를 더한 값, 음수를 더한 값을 다시 queue에 push 합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 #include..

[백준 1339] 단어 수학 C++

문제 백준 1339 단어 수학 C++ 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀이 처음에는 백트래킹을 활용하여 각 알파벳에 1~10까지 모두 넣어보는 브루트 포스 방법으로 풀었지만, 그리디로 접근하면 훨씬 효율적으로 풀 수 있습니다. 소스 코드 브루트 포스 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 ..

알고리즘/백준 2021.11.15

[백준 1405] 미친 로봇 C++

문제 백준 1405 미친 로봇 C++ 1405번: 미친 로봇 첫째 줄에 N, 동쪽으로 이동할 확률, 서쪽으로 이동할 확률, 남쪽으로 이동할 확률, 북쪽으로 이동할 확률이 주어진다. N은 14보다 작거나 같은 자연수이고, 모든 확률은 100보다 작거나 같은 자 www.acmicpc.net 풀이 DFS를 활용하여 전체 탐색합니다. 4^14이라 시간 초과가 발생할 것 같지만, 중간에 경로가 겹치면 그 이후 경로는 탐색하지 않는 식으로 접근하면 더 빨리 해결이 가능합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 ..

알고리즘/백준 2021.11.15

[C++] 부동 소수점

개요 C++에서 소수를 저장할 때 부동소수점 자료형을 이용한다. 상세 1/3 = 0.3333...과 같은 경우 코드 내에서 무한한 소수점을 표현할 수 없으므로 특정 자리까지만 저장하고 나머지는 손실된다. std::cout의 경우 기본 정밀도는 6으로, 소수 아래 6자리까지는 유효하고, 그 아래부터는 오차가 발생한다. cout.precision(n)을 사용하게 되면 n자리까지 cout이 표시하게 된다. (cout

언어/C++ 2021.11.12

[백준 2023] 신기한 소수 C++

문제 백준 2023 신기한 소수 C++ 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 풀이 백트래킹을 활용합니다. 1. 0자리부터 시작합니다. 2. 현재 숫자에 1~9까지 숫자를 뒤에 붙여가며 소수인지 판별합니다. 2-1. 소수라면 dfs를 재귀호출 합니다. 이 때 수와 자리수를 갱신해줍니다. 3. 현재 수가 N자리 이면 수를 출력하고 함수를 종료합니다. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28..

알고리즘/백준 2021.11.10
반응형