c++

[BOJ] 알고리즘 스터디 boj 1939 중량제한 BFS + BINARY SEARCH

이번에는 백준 1939 중량 제한을 풀어보자BFS + 이진탐색 으로 풀어야한다. https://www.acmicpc.net/problem/1939 중량제한 성공시간 제한메모리 제한제출정답맞은 사람정답 비율2 초128 MB67011657101624.847%문제N(2≤N≤10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리..

[BOJ] 13565 침투 알고리즘 스터디 11월 21일

오늘 풀 문제는 침투 --> 백준에서 가져왔고 아래 주소가 있습니다. https://www.acmicpc.net/problem/13565 침투한국어 시간 제한메모리 제한제출정답맞은 사람정답 비율1 초512 MB165462847740.979%문제인제대학교 생화학연구실에 재직중인 석교수는 전류가 침투(percolate) 할 수 있는 섬유 물질을 개발하고 있다. 이 섬유 물질은 2차원 M × N 격자로 표현될 수 있다. 편의상 2차원 격자의 위쪽을 바깥쪽(outer side), 아래쪽을 안쪽(inner side)라고 생각하기로 한다. 또한 각 격자는 검은색 아니면 흰색인데, 검은색은 전류를 차단하는 물질임을 뜻하고 흰색은 전류가 통할 수 있는 물질임을 뜻한다. 전류는 섬유 물질의 가장 바깥쪽 흰색 격자들에 공..

[알고리즘 문제 해결 전략] Part 1. 6장 무식하게 풀기 [소풍]

지난번엔 보글게임을 공부했습니다. 다음 문제인 소풍을 공부하려고 합니다. https://algospot.com/judge/problem/read/PICNIC 6.3 문제 : 소풍 (ID : PICNIC, 난이도: 하)문제 내용은 다음과 같아요. 소풍 ID : PICNIC 문제안드로메다 유치원 익스프레스반에서는 다음 주에 율동공원으로 소풍을 갑니다. 원석 선생님은 소풍 때 학생들을 두 명씩 짝을 지어 행동하게 하려고 합니다. 그런데 서로 친구가 아닌 학생들끼리 짝을 지어 주면 서로 싸우거나 같이 돌아다니지 않기 때문에, 항상 서로 친구인 학생들끼리만 짝을 지어 줘야 합니다.각 학생들의 쌍에 대해 이들이 서로 친구인지 여부가 주어질 때, 학생들을 짝지어줄 수 있는 방법의 수를 계산하는 프로그램을 작성하세요...

1799 백준 비숍 백트래킹

초등부가 왜 이렇게 어렵나...혼자서 dfs 하려다가 말아먹고 , 결국 다른분 코드 참고해서 만들었다.문제는 아래와 같다. 원래 비숍이 놓일때마다 4방향의 대각선을 다 검색하는 방법을 사용하려고 했는데 , 시간초과가 나는 사람이 있다고도 하고무식한것 같아서 방법을 찾다가, 체스판의 대각선을 2부분으로 나눠 푸는 것을 발견했다. * 체스판을 N * N의 격자가 아니라, 2N 개의 대각선으로 바라보는 방법입니다.대각선으로 체스판을 보게 되면 다음 두가지 이점이 있습니다.1. 현재 대각선에서 비숍을 하나만 놓고 다음 대각선으로 이동하면 됩니다. 2. 현재 대각선의 어떤 위치에 비숍을 놓을 수 있는가의 검사는 반대 방향의 대각선에 비숍이 놓여졌는지를 확인하는것으로 O(1)에 수행할 수 있습니다. 이렇게 푸는 방..

11778 피보나치 수와 최대공약수 행렬 계산 방법

누가 포스팅 해놓은 것도 없고, 찾으려고하니 왜 이렇게 생각해야 되는게 많은 건지...일단 메모리 제한이 256MB라 메모이제이션 혹은 DP를 생각했는데 .. 시간초가 런타임 에러 뿜뿜...재귀함수를 만들던,, 메모이제이션을 하던 DP를 하던 O(n) 시간이 걸려서 이건 안되겠다...생각했다. 그래서 검색해보니 피보나치 수열을 계산하는 방법 중에 1. 피사노 주기(Pisano Period)2. 행렬 곱셈들이 있었는데 , 1번은 우리가 계산해야 되는 값이 1,000,000,000,000,000,000 처럼 길고 답을 1,000,000 와 같은 값의 나머지로출력할때 유용하게 쓰인다. 10^k로 나눈 피보나치 수의 나머지들을 반복적인 값의 형태를 띈다. 그것을 피사노 주기! 하지만, 피사노 주기도 O(n)이 ..

1003 번 문제 피보나치 함수 Dynamic Programming

DP를 공부하는데 처음 해보면 괜찮을 문제같다. 동전 문제를 바로 해보는 건 조금 어려운것 같기도 하고, 아무튼 0을 호출했을때 0을 출력 1을 호출했을때 1을 출력.이것을 계속 단계 별로 저장해 나아가면서, 최상단의 호출한 번호에서 몇번을 출력해 주었는지 알아내면 된다. DP 배열 0 1 2 3 4 5 6 7 8 9 1/0 0/1 1/1 1/2 2/3 3/5 5/8 . . . dp[0] = 1/0; dp[1] = 0/1;2는 0과 1을 더한 것이고, 3은 2와 1의 결과 값을 더한 것이다. 즉 앞에서 부터, 차례대로 결과값을 쌓아가면 된다. 소스 보기 #include int main(){ int dp[41][2]={0}; int n=0,t=0; scanf("%d",&n); dp[0][0]=1; dp[0..

5704 팬그램 문자열 처리 문제 백준

https://www.acmicpc.net/problem/5704팬그램알파벳 배열 25개 짜리 만든 후에 문장에 알파벳이 존재하면 체크해주고체크가 모두 되어있으면 Y 출력 아니면 N 출력 소스 보기 #include #include using namespace std;int main(){ char ar[201],alpa[26]; memset(ar,0,sizeof(ar)); memset(alpa,0,sizeof(alpa)); //배열 초기화 while(1){ cin.getline(ar,201,'\n'); int i=0; if(ar[0]=='*') break; //별이 입력되면 while문 종료 while(1){ alpa[(int)ar[i]-97] = 1; //0부터 25까지 할당된 소문자 배열에 문자가 입력..

백준 5026 박사 과정 문자열 처리

https://www.acmicpc.net/problem/5026박사과정 5026 개행문자와 1의 자리숫자 이상의 숫자일때 처리해야 하는 부분과strcmp로 글자를 비해 숫자가 아닐때 다른 값을 출력해줘야함 코드 보기 #include #include using namespace std; int main(){ int n=0,sum=0,temp=0; char ar[20]; cin >> n; cin.ignore(); for(int i=0; i