티스토리

영충이 알고리즘
검색하기

블로그 홈

영충이 알고리즘

2youngjae.tistory.com/m

영충이의 알고리즘 스터디 블로그

구독자
2
방명록 방문하기
공지 영충이 알고리즘 모두보기

주요 글 목록

  • 17142 연구소 3 17142 연구소 3 1. 활성 바이러스를 m개 고르는 모든경우에 대해 탐색한다.2. 선택된 활성바이러스를 퍼뜨린다.3. 모든 영역을 바이러스로 만드는 최소시간을 찾는다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124#include #include #include #include us.. 공감수 0 댓글수 0 2019. 4. 17.
  • 17140 이차원배열과 연산 17140 이차원배열과 연산 시뮬레이션 문제이다.C++를 이용하는 사람은 벡터와 구조체 정렬자바를 이용하는 사람은 ArrayList와 클래스 정렬을 사용할줄 안다면 쉽게 풀 수 있지않을까 생각한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113.. 공감수 0 댓글수 0 2019. 4. 17.
  • 16235 나무 재테크 16235 나무 재테크 문제에서 주어진 조건대로 구현하면 되는데 조건이 살짝 까다로울 수 있다. 평소 STL를 자주 사용해봤으면, vector나 queue와 sort를 이용하여 비교적 쉽게 풀 수 있을거라고 생각한다. #include #include #include using namespace std; int n, m, k; int a[11][11]; //겨울에 추가되는 양분 저장 int tmp[11][11]; //현재 남아 있는 양분 저장 vector map[11][11]; //(r, c)좌표에 있는 나무들의 나이 저장 int dr[] = { 0,0,1,-1,1,-1,1,-1 }; int dc[] = { 1,-1,0,0,1,1,-1,-1 }; void doSS(int r, int c) { int sz .. 공감수 0 댓글수 0 2018. 10. 22.
  • 16236 아기상어 16236 아기상어 문제에서 주어지는 조건대로 구현 하면 된다. #include #include #include using namespace std; struct Node { int x, y; Node(){} Node(int x,int y):x(x),y(y){} }; struct Next { int x, y, diff; Next(){} Next(int x, int y, int d):x(x),y(y),diff(d){} }; int n, cx, cy, time, sz, cnt; int map[20][20]; int check[20][20]; int dx[] = { -1,0,1,0 }; int dy[] = { 0,-1,0,1 }; Next v[400]; int nIdx; void bfs() { check[cx.. 공감수 0 댓글수 0 2018. 10. 22.
  • 16234 인구 이동 16234 인구 이동 문제에서 주어지는 조건대로 시뮬레이션 해주면 된다. #include #include #include using namespace std; struct Node { int r, c; Node(){} Node(int r,int c) : r(r),c(c){} }; int map[50][50]; int tmp[50][50]; bool check[50][50]; int n, L, R, sum; vector v; int dr[] = { 0, 0, 1 , -1 }; int dc[] = { 1,-1,0,0 }; void dfs(int r, int c) { check[r][c] = true; sum += map[r][c]; v.push_back(Node(r, c)); for (int i = 0; i.. 공감수 1 댓글수 0 2018. 10. 22.
  • 15684 사다리 조작 15684 사다리 조작 백트래킹을 이용해 완전탐색하되 조건을 주어 가지치기 하면서 풀었다. 1. 코드를 간결하게 만들기 위해 사다리를 놓을 수 있는 좌표를 벡터에 모두 넣는다. 2. 연속되지 않도록 사다리를 놓으면서 (dfs함수에서 map[v[idx].first][v[idx].second] = 1) 사다리 조작이 가능한지 확인한다. 3. 조작이 가능하다면 res를 최신화 시켜준다. 4. 백트래킹 시에 카운트값이 3보다 크거나 res값과 같거나 크면 함수를 종료한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172.. 공감수 0 댓글수 0 2018. 9. 7.
  • 2580 스도쿠 2580 스도쿠 백트래킹을 이용하여 완전탐색 하는 문제이다. 1. map입력 받을때 0값인 곳의 좌표를 vector에 푸쉬 한다. 2. 가로 세로 3x3칸에 대해 타당함을 확인하는 isPromising() 함수를 만든다. 3. 완전 탐색 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182#include #include #define P pairusing namespace std; int map[9][9];vector v;bool flag; //타당성 여부 확인bool isP.. 공감수 0 댓글수 0 2018. 4. 21.
  • 15683 감시 15683 감시 1. CCTV정보를 담을 구조체를 만든다. 2. CCTV들을 벡터에 넣는다. 3. CCTV들이 감시할 수 있는 영역에 대하여 완전탐색한다. 나는 check 함수를 이용하여 사각지대 여부를 확인하였다.단순히 bool 형으로 true false 로 설정하면 중복되는 부분이 지워지는 경우가 있어서int형으로 만들고 ++, -- 해주며 사각지대를 찾았다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001.. 공감수 0 댓글수 7 2018. 4. 18.
  • 15686 드래곤 커브 15686 드래곤 커브 시뮬레이션 문제이다.90도 회전하는 규칙을 찾는게 중요한데 나는 무식하게 찾았다. (x,y) 가 기준좌표 일 때 (ax, ay) 를 90도 회전한 좌표구하기기준좌표와 목표좌표의 차 dx, dydx = x - ax;dy = y - ay; 90도 회전된 좌표 nx, nynx = x + (-1)*dyny = y + dx이다. 정사각형 찾을때는 현재좌표/오른쪽/아래/오른대각아래 4꼭지점이 다 있으면 +1 해주었다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081#i.. 공감수 0 댓글수 0 2018. 4. 16.
  • 15686 치킨 배달 15686 치킨 배달 1. 치킨집을 m개 고르는 모든 경우에 대해 백트래킹 한다. 2. 골라진 경우마다 최소값을 구한다. 3. 최소값을 출력한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include #include #include #define INF 987654321#define P pairusing namespace std; int n, m, res;int d[100][14];//각각 지원자들의 고사장과의 거리 저장bool visited[14];vector p; //고사장 위치 저장vector h; //지원자.. 공감수 0 댓글수 3 2018. 4. 16.
  • 1182 부분집합의 합 1182 부분집합의 합 완전탐색해주면 된다! 123456789101112131415161718192021222324252627#include using namespace std; int n, s, res;int a[20]; void dfs(int idx, int sum) { if (sum + a[idx] == s) res++; if (idx == n - 1)return; dfs(idx + 1, sum); dfs(idx + 1, sum + a[idx]);} int main(){ cin >> n >> s; for (int i = 0; i > a[i]; } dfs(0, 0); cout 공감수 0 댓글수 4 2018. 4. 13.
  • 9019 DSLR 9019 DSLR 1. D, S, L, R 기능을 각각 구현한다. 2. 인트형과 스트링형을 담는 구조체를 만든다. 3. bfs탐색을 통해 가장 먼저 목표값을 찾는 string 을 출력한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include #include using namespace std; struct Node { int n; string str; Node(int n,string str) :n(n),str(str) {}}; int t;string res; int.. 공감수 0 댓글수 0 2018. 4. 13.
  • 1018 체스판 다시 칠하기 1018 체스판 다시 칠하기 8x8칸에서 하얀칸으로 시작하는경우/ 검정칸으로 시작하는 경우두개로 나누어 완전탐색 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768#include #include #include #define SZ 8using namespace std; int n, m;int map[50][50]; int solve(int x,int y, int flag) { int ans = 0; if (flag == 0) { for (int i = x; i m; string buf; for (int i = 0; i > .. 공감수 0 댓글수 0 2018. 4. 12.
  • 1520 내리막 길 1520 내리막 길 1. 목적지( n, m ) 이면 1반환 2. 한번도 방문하지 않은곳이면 dfs탐색 3. 방문했던 곳이면 d[x][y] 반환 4. ( 1, 1 ) 부터 시작. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include using namespace std; int n, m;int map[502][502];int d[502][502];int dx[] = { 1,-1,0,0 };int dy[] = { 0,0,1,-1 }; int dfs(int x,int y) { if (x == n && y == m) { return 1; } //(x,y)가 한번도 방문하지 않았을 .. 공감수 0 댓글수 0 2018. 4. 8.
  • 1937 욕심쟁이 판다 1937 욕심쟁이 판다 단순히 500x500 지점에서 각각 탐색하려고 하면 시간초과가 난다(났다).그러므로 메모이제이션을 이용해야만 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include using namespace std; int n, m;int map[502][502];int d[502][502];int dx[] = { 0,0,1,-1 };int dy[] = { 1,-1,0,0 }; void dfs(int x, int y) { d[x][y] = 1; for (int i = 0; i 공감수 0 댓글수 0 2018. 4. 8.
  • 14620 꽃길 14620 꽃길 삼성기출문제중 테트로미노 문제랑 비슷한 문제라고 생각한다. 1. 꽃모양에 대한 filter값을 x, y 각각 만든다. 2. d배열에 해당 좌표에서 꽃모양 만드는 좌표들의 값을 더한값을 저장한다. 3. 꽃모양 3개를 만들었을때 최소값을 출력한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include #include using namespace std; int n, res;int map[10][10];int d[10][10];boo.. 공감수 0 댓글수 0 2018. 4. 5.
  • 1963 소수경로 1963 소수경로 1. 에라토스테네스의 체를 이용하여 1000~9999 사이의 소수를 찾는다. 2. 한 타임당 한자리를 바꿔가며 소수인경우 큐에 넣고 몇번째인지 기록한다. 3. 찾는 숫자에 도착하면 출력한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include #include using namespace std; int n, a, b;bool primes[10001];int visited[10001]; void bfs(int a,int b) { queue q; q.push(a); visited[a] = 1.. 공감수 0 댓글수 0 2018. 4. 2.
  • 12100 2048 (Easy) 12100 2048 (Easy) *핵심 아이디어 : 1.지역변수로 tmp배열을 두어 매순간마다 복사하며 사용하였다. 2.block_move 함수의 구현. *문제풀이 1. 상하좌우 4방향에 대해 움직였을때 처리해줄 block_move 함수 작성.--> block_move 함수의 주석 참고. 2. 모든경우에 대해 완전탐색. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810.. 공감수 0 댓글수 0 2018. 4. 1.
  • 1799 비숍 1799 비숍 개인적으로 정말 어려웠다.처음 N-Queens Problem풀듯이 풀려고 했으나 시간초과가 났고 대각탐색등 다양하게 해봤는데 다 실패했다. 다음방법으로 검정칸에 있는 비숍은 검정칸만 이동가능하고 하얀칸에 있는 비숍은 하얀칸만 이동 가능하므로 맵을 반으로 나눠 각각 백트래킹 하였다. dfs은 하얀칸만 탐색/ dfs2는 검정칸만 탐색 하도록 하였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101.. 공감수 0 댓글수 0 2018. 3. 29.
  • 13549 숨바꼭질 3 13549 숨바꼭질 3 +1, -1 하는 경우와 *2 하는 경우를 나눠서 갱신해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647#include #include #define P pairusing namespace std; int visited[100001];int n, k;int dx[] = {1,-1}; void bfs() { queue q; q.push(n); visited[n] = 1; int next; while (!q.empty()) { int cur = q.front(); q.pop(); for (int i = 0; i visited[cur] + 1) { q.push(next);.. 공감수 0 댓글수 0 2018. 3. 26.
  • 12851 숨바꼭질 2 12851 숨바꼭질 2 d배열 = 최소 몇번만에 도착 가능한지 기록cnt배열 = 최소로 도착하는 경우의 수 기록 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566import java.util.LinkedList;import java.util.Queue;import java.util.Scanner; public class Main { static int n,k; static int d[] = new int[100001]; static int cnt[] = new int[100001]; static final int dx[] = {1, -.. 공감수 0 댓글수 0 2018. 3. 26.
  • 1600 말이 되고픈 원숭이 1600 말이 되고픈 원숭이 14442번 벽 부수고 이동하기2 와 비슷하다고 느껴져 같은 방법으로 풀어보았다. 기본 아이디어: visited[ax][ax][k] -> 나이트의 이동처럼 움직이는 경우를 k번 사용한 최소값 저장 1. 상하좌우 4방향과, 나이트의 이동으로 이동 가능한 8가지 경우에 대해 틀을 만든다. 2. x좌표, y좌표, jump사용 횟수를 기록할 Node 구조체를 만든다. 3. bfs를 통해 (0,0)에서 (n,m) 으로 가는 최소값을 찾는다. 4. bfs에서 k번 반복하며, 각각의 visited맵에 jump번 점프한 최소값을 기록해둔다. 5. k개의 visited 배열에서 오른쪽 맨 아래값중 0이 아니면서 가장 작은값을 출력한다. 1234567891011121314151617181920.. 공감수 0 댓글수 0 2018. 3. 26.
  • 13460 째로탈출 2 13460 째로탈출 2 깔끔한 코드는 도저히 생각이 나지 않아서 경우의 수들에 대해 하드코딩 했다......가장 중요한 아이디어는 rx, ry, bx, by를 매개변수로 받아 지점에 대한 타당성을 검증하는 것인거 같다. 1. 직전에 상하로 움직였으면 이번엔 좌우만 움직여보고, 직전에 좌우로 움직였으면 상하로만 움직인다. 2. 파란공을 먼저 움직여보고 타당하면 빨간공을 움직인다. 3. 빨간공까지 움직였을때 빨간공과 파란공의 위치가 같은경우 인자로 받아왔던 rx,ry,bx,by 값을 비교해 둘중 하나를 한칸 옮겨준다. 4. cnt가 10이하인 모든 방법을 탐색한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444.. 공감수 0 댓글수 0 2018. 3. 25.
  • 14500 테트로미노 14500 테트로미노 나올 수 있는 19가지 모양에 대한 필터를 만든뒤, 모든점을 탐색하며 최대값을 구했다.필터 만들때 중요한점은 기준을 정해놔야 헷갈리지 않는다.나는 맨 아래, 맨 왼쪽을 0으로 기준잡고 필터링 하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include #include using namespace std; int n, m;int map[500][500]; //각각 블록에 대한 필터int x_filter[19][4] ={ {0,1,2,3},{0,0,0,0},{0,0,1,1},{0,1,2,2}, {0,0,0,1},.. 공감수 0 댓글수 0 2018. 3. 25.
  • 4179 불! 4179 불! 1. 불들이 퍼진 최소시간을 visited에 기록한다. 2. 시작점을 1로 놓고 벽까지 갈 수 있는지 탐색한다. 3. 탐색 가능하면 그때의 시간 출력/ 탐색 불가능 하면 IMPOSSIBLE 출력 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495#include #include #include #include #include #define P pairusing namespace std; int r, c, sx, sy;int.. 공감수 0 댓글수 0 2018. 3. 25.
  • 5558 치 ~ 즈 5558 치 ~ 즈 최단거리를 응요해서 푸는 문제이다. 1. 방문기록과 state 정보를 함께 저장할 pair형 visited를 만든다. 2. 다음지점이 '.'일때와 치즈일 때를 나눈다. 3. '.' 일 때, first를 먼저 비교하교 같은경우 second를 비교하여 방문 4. 치즈일 때, state가 기준 이상일 때와 기준 미만일때를 나눠서 방문. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990#include #include #include #in.. 공감수 0 댓글수 0 2018. 3. 24.
  • 1654 랜선 자르기 1654 랜선 자르기 1. low=0, 주어지는 길이들의 최대값을 찾아 high로 놓는다. 2. mid로 나눈값들의 합이 k보다 크거나 같은경우 최대값을 갱신해준다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #define ll long longusing namespace std; ll n, k, res;ll a[10001]; ll max(ll a, ll b) { return (a > b) ? a : b;} bool search(ll mid) { ll ans = 0; for (int i = 0; i = k) ? true : false;} int main() { scanf("%l.. 공감수 0 댓글수 0 2018. 2. 28.
  • 2638 치즈 2638 치즈 1. 가장자리는 무조건 공기라고 문제에서 주어졌으므로, 가장자리에서 시작해 공기부분을 초기화 시킨다. 2. 공기와 두칸이상 맞닿은 부분을 vector에 기록하고 공기로 바꾼다. 3. 남은 치즈의 개수를 센다. 4. 치즈가 다 사라진 시간을 출력한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889#include #include #define P pairusing namespace std; int n, m;int map[100][100];b.. 공감수 0 댓글수 0 2018. 2. 28.
  • 2665 미로만들기 2665 미로만들기 BFS를 배우고 있거나 연습하는 사람에게 좋은 문제인거 같다. 1. pair형으로 두가지 정보를 저장할 d 배열을 만든다. first=뚫은 횟수, second=거리비용 2. 한번도 방문하지 않았거나 뚫은횟수가 더 적은경우 무조건 갱신 3. 이미 방문했고 벽을 뚫은 횟수가 같을경우 거리비용이 더 적은것으로 갱신 4. d[n][n]에 저장되어있는 벽을뚫은 최소 횟수 출력. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384#include #include #d.. 공감수 1 댓글수 0 2018. 2. 28.
  • 2174 로봇 시뮬레이션 2174 로봇 시뮬레이션 주어진 조건대로 구현하기. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586#include #include #define E 1#define S 2#define W 3#define N 4using namespace std; struct Node { int x, y, dir;};int A, B, n, m;int map[102][102];int dy[] = { 0,0,-1,0,1 };int dx[] = { 0,1,0,-1,0 }; //1동 2남.. 공감수 1 댓글수 1 2018. 2. 28.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

    티스토리는 카카오에서 사랑을 담아 만듭니다.

    © Kakao Corp.