본문 바로가기

알고리즘 관련/BOJ

BOJ)13460 구슬탈출2 문제: icpc.me/13460 빨간 공과 파란 공이 동시에 움직일 때 빨간공을 구멍에 넣게하는 최소 횟수를 출력하는 문제이다. 우리는 빨간공과 파란공의 위치를 동시에 조작하며 BFS를 돌리며 횟수를 출력한다. 이 때 공이 겹치는 경우를 잘 처리해주어야 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374#include #include #include using namespace std;int n, m, disc[11][11][11][11], bx, by, rx, ry;char a[11][11];int .. 더보기
BOJ)1520 내리막 길 문제:icpc.me/1520 지도에서 자기보다 숫자가 낮은 곳으로 이동할 수 있을 때 0,0에서 n-1 ,m-1로 갈 수 있는 경로의 개수를 출력하는 문제이다. 우리는 다이나믹 프로그래밍을 이용하여 문제를 해결할 수 있다. dp[x][y]는 0,0에서 x,y로 이동할 수 있는 경로의 수라고 정의한 뒤 4방향 탐색으로 테이블을 채워나가면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;int dx[] = { 0,0,-1,1 };int dy[] = { -1,1,0,0 };int n, m;int chk(int x, int y) { return 0 더보기
BOJ)10422 괄호 문제: icpc.me/10422 괄호 문자열이 되려면 괄호 문자열이 채워져 나가는 과정에서 )의 개수가 (개수보다 많으면 안된다. 이를 만족하면서 채워져 나가는 길이가 N인 괄호문자열의 개수를 다이나믹 프로그래밍을 이용하여 구해주면 된다. N이 홀수인 경우 0을 출력하고 N이 짝수인 경우 dp[n/2][n/2]를 출력하면 된다. dp[x][y]의 정의는 (가 x개 )가 y개 까지 그려진 괄호문자열의 개수 이다. 점화식은 dp[x][y]=dp[x-1][y]+dp[x][y-1]이 된다. 123456789101112131415161718192021222324252627282930#include #include #include #define MOD 1000000007typedef long long ll;usin.. 더보기
BOJ)1194 달이 차오른다, 가자. 문제: icpc.me/1194 가중치 없는 그래프에서의 최단거리를 구해야 하므로 BFS를 이용하면 된다, 이때 열쇠라는 조건이 추가로 붙는데 우리는 열쇠를 쥐고 있는 상태를 비트마스킹을 통하여 표현해주면 된다. qu의 3번째 인자는 해당 상태가 가지는 열쇠를 비트로 표현한 것이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include using namespace std;int n, m, disc[51][51][1 더보기
BOJ)2146 다리만들기 문제: icpc.me/2146 dfs를 이용하여 각 나라들을 구분해준 후 bfs를 이용하여 각 나라들에서 어떤 다른 나라로 갈 수 있는 최단 거리를 모두 구해준 뒤 그 중 최솟값을 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include #include #include #include #include using namespace std;int n, a[101][101], disc[101][101], c;bool chk(int x, int y) { return 0 더보기
BOJ)5427 불 문제: icpc.me/5427 가중치가 없는 그래프에서의 최단경로 이므로 BFS를 이용하여 문제를 해결해준다. 단 불이라는 새로운 조건이 존재하는데 우리는 queue에 상근이와 불을 동시에 삽입해주어 불일 경우와 상근이일 경우를 다르게 처리해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include #include #include #include using namespace std;int t, w, h, sx, sy;char a[1001][1001];in.. 더보기
BOJ)1745 숨기 문제: icpc.me/1745 F개의 방이 있을 때 각방마다 학생들이 숨을 수 있는 수와 현재 몇명의 학생들이 있는지 수가 주어진다. 이 때 방 A에서 B로 이동할 때 걸리는 시간이 주어질 때 모든 학생이 숨을 수 있는 최소 시간을 구하는 문제이다. 우리는 소스 -> I번 방 -> I번 방에서 ->J번 방으로 연결 된 정점 -> J번 방 ->싱크로 모델링을 하여 모든 학생들이 숨을 수 있는지 여부를 알 수 있다. 이때 capacity를 소스 -> I번 방은 현재 i번방에 있는 학생 수 / J번 방 -> 싱크는 j번 방에 숨을 수 있는 학생 수 나머지는 INF를 주면 된다. 이렇게 하여서 흘린 maximum flow가 현재 있는 학생들의 수의 총합과 같다면 현재 모델링에서 학생들이 전부 숨을 수 있는것이다.. 더보기
BOJ)5397 키로거 문제:icpc.me/5397 메모장에 커서의 입력하는 단어와 커서의 움직임과 누른 백스페이스가 기록될 때 최종적으로 남는 단어를 출력하는 문제이다. 중간에 삽입 삭제가 가능한 링크드리스트를 구현하여 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091#include #include using namespace std;struct Node { char data; Node *prev, *next; Node() :data('\0'), pr.. 더보기
BOJ)2075 N번째 큰 수 문제:icpc.me/2075 N^2개의 수가 들어올 때 N번째로 큰 수를 구하는 문제이다. N이 최대 1500 밖에 안들어오므로 단순히 값을 다 받아서 정렬해주는 N^2logN의 해법으로 해결할 수 있다. 하지만 메모리제한이 10MB이므로 힙을 이용하여 수를 받을 때 마다 큰 수 N개만큼만 저장해주고 그 수들중 가장 작은 수와 들어오는 수를 비교를하여 힙을 관리해주면 된다. 123456789101112131415161718192021222324#include #include #include using namespace std;int n, x;priority_queue pq;int main() { scanf("%d", &n); for (int i = 0; i 더보기
BOJ)1326 폴짝폴짝 문제: icpc.me/1326 각 징검다리에 숫자가 써있고 해당 징검다리에서는 숫자의 배수만큼 떨어져 있는 징검다리까지 점프 할 수 있을때 a에서 b까지 의 최단거리를 출력하는 문제이다. 해당 징검다리에서 갈 수 있는 모든 징검다리까지 cost가 1인 간선을 연결해주고 다익스트라를 이용하여 최단거리를 구해줄 수 있다. 이 때 주의할 점은 배수 이기 때문에 나보다 작은 지점으로도 점프할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include #include using namespace std;int n, a[10001], s, e, dp[10001];vector vt;in.. 더보기

티스토리툴바