티스토리

나는 오늘,
검색하기

블로그 홈

나는 오늘,

jayrightthere.tistory.com/m

#알고리즘 #개발 #프로그래밍#IT개발자#JAVA#C++

구독자
3
방명록 방문하기
공지 코드 관련 참고 사항 모두보기

주요 글 목록

  • [BOJ] 14226. 이모티콘 * BFS로 완전 탐색한다. * 큐에 모든 연산을 한 결과(now) 와 clipboard에 저장된 값(buffer), 연산 횟수(cnt)를 저장해나가면서 now == s가 되면 그 때의 cnt가 최소값이 된다. * now의 값이 변화되는 연산을 실행할 때 (이모티콘 삭제, 버퍼에 있는 값 붙여넣기) 범위를 제한해야 한다. (제한하지 않으면 오버플로우 발생 가능) * bfs의 기본인 방문 체크를 하면서 탐색한다. #include #include #include #define INF 987654321 using namespace std; //boj 이모티콘 https://www.acmicpc.net/problem/14226 typedef pair pp; typedef pair ipp; bool dp[1001.. 공감수 0 댓글수 0 2020. 5. 3.
  • [BOJ] 1976. 여행 가자 * 서로소 집합(union find)를 이용한다. * 연결되어 있는 도시들은 양방향으로 연결되고, 여행 경로는 중복이 가능하기 때문에(=최단경로가 아님) m개의 도시들이 같은 집합에 속해있는지만 확인하면 된다. #include #include #include #include #define MAXX 3001 using namespace std; // BOJ 여행가자 https://www.acmicpc.net/problem/1976 int n, m; int parent[MAXX]; int find(int a) { if (parent[a] == -1) return a; return find(parent[a]); } void unionFind(int a, int b) { int pa = find(a); int .. 공감수 0 댓글수 0 2020. 4. 30.
  • [BOJ] 16957. 체스판 위의 공 * 체스칸 위의 적힌 값은 변동이 없기 때문에 공의 위치에 따라 이동할 방향이 정해져있다. * 이 특징을 이용해서, 좌표마다 움직이는 방향을 저장하고 (dir[][]) 해당 위치에 오면 저장된 방향으로 이동하도록 한다. * 공을 이동시킬 때는 해당 좌표에 있는 공을 모두 가지고 이동한다. #include #include #include #define INF 300001 using namespace std; //BOJ https://www.acmicpc.net/problem/16957 int r, c; int map[501][501]; int ball[501][501]; int dir[501][501]; bool visited[501][501]; int dx[9] = {-1, -1, -1, 0, 0, 0,.. 공감수 0 댓글수 0 2020. 4. 25.
  • [BOJ] 17298. 오큰수 * 스택을 사용한다. * 나중에 들어오는 수가 오큰수가 정해지기 때문에 스택을 이용해서 가장 최근 넣은 값과 (top) 현재 값을 비교한다. 이전 값보다 더 큰 수가 들어오면 => 이전 값 수의 오큰수는 현재 값이다. * 더 큰 수가 없으면 -1이다. #include #include #include #define MAXX 1000001 using namespace std; typedef pair pp; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; int res[MAXX]; int num[MAXX]; stack st; for (int i = 0; i < n; i++) res[i] = -1; for (int i = 0; i .. 공감수 0 댓글수 0 2020. 4. 25.
  • [BOJ] 4378. 트ㅏㅊ; * 주어진 문자열을 키보드 상에서 한 칸 씩 왼쪽으로 간 결과로 치환해야 하기 때문에 키보드를 그대로 배열에 저장한다. * 문자열을 탐색하면서 문자가 탐색되면 그 인덱스 -1의 결과를 출력한다. * 인풋은 여러 줄을 나눠서 들어오고, 중간에 공백이 있을 수 있으므로 getline()으로 입력받는다. #include #include using namespace std; //boj https://www.acmicpc.net/problem/4378 int main() { ios_base::sync_with_stdio(0); cin.tie(0); string keyBoard[4] = {"`1234567890-=", "QWERTYUIOP[]\\", "ASDFGHJKL;\'", "ZXCVBNM,./"}; strin.. 공감수 0 댓글수 0 2020. 4. 25.
  • [BOJ] 9019. DSLR * 경로를 남기고, 역추적한다. * visited[i] = j 는 i가 되기 전의 숫자가 j임을 표시한다. op[i] = i가 되기 위한 연산을 저장한다. * a = 시작점 일 때, visited[a] = -2로 저장한다. (이 표식을 발견하면 역추적을 중지한다.) * a가 b가 되었을 때, 역추적을 하면서 벡터에 사용한 연산들을 저장한다. * a가 b가 아니라면, D ,S, L, R 연산을 진행하면서 만들어진 숫자들을 모두 큐에 넣는다. 중복 탐색을 방지하기 위해 이미 한 번 생성된 숫자는 더 이상 탐색하지 안흔ㄴ다. * 이 문제는 L, R 연산을 효율적으로 작성하는 게 중요하다. deque, string 등은 시간이 초과된다. L : d2 d3 d4 d1 이므로 가장 마지막 숫자를 추출한다. (n =.. 공감수 0 댓글수 0 2020. 4. 25.
  • [BOJ] 17085. 십자가 2개 놓기 * 십자가를 놓을 수 있는 최대 길이를 chk[][] 에 미리 저장을 해 놓는다. * 십자가는 한 좌표를 중심으로 상 하 좌 우 인접한 칸으로 퍼져나간다. * 이 특성을 이용해서 chk에는 몇 번이나 뻗어나갔는지를 저장한다. * dfs(int cnt, ll res) 에는 2개의 십자가를 놓았으면 최대값을 비교하여 갱신한다. (종료조건) *(0,0) ~ (n,m)까지 검사하면서 chk[][]가 1이상일 때 (== map[][] 가 # 일때) 주변을 검사하면서 십자가가 겹쳐서 생성되지 않는지 검사한다. *무조건 한 십자가가 크다고 정답이 되는 것은 아니기 때문에 십자가의 크기가 chk[][] 의 값보다 작더라도 dfs()를 호출해서 다른 십자가도 놓을 수 있도록 한다. (line 81) * visited는 .. 공감수 0 댓글수 0 2020. 4. 20.
  • [BOJ] 16939. 2X2X2 큐브 https://www.acmicpc.net/problem/16939 * 큐브를 회전할 때 같이 바뀌는 인덱스들을 rotateIdx[][] 에 저장해둔다. * 한 번만 회전하는 경우 나올 수 있는 경우의 수가 6개 이고 한 번 회전할 때 바뀌는 인덱스는 8개 이므로 6*8 로 생성했다. *큐브의 현재 상태를 저장하는 것이 중요하다. * rotate()에는 큐브를 회전하고 check()를 통해 회전한 결과가 옳은지 확인한다. * deque를 사용해서 정방향으로 돌릴 때는 뒤에 값을 넣어주고, 역방향으로 돌릴 때는 앞에 값을 넣어준다. deque의 결과는 다시 큐에 넣고, check()에서 결과를 확인한다. #include #include #include #include using namespace std; .. 공감수 0 댓글수 0 2020. 4. 20.
  • [BOJ] 16932. 모양 만들기 * dfs를 이용하여 1로 이루어진 그룹을 라벨링한다. (그룹에 몇 개의 1이 있는지 labelCnt[]에 저장한다) * 현재 좌표의 값이 1이고, 상 하 좌 우 인접한 값이 0인 좌표를 중심으로 탐색을 한다. 인접한 좌표에 0이 있다면 이 값을 1로 바꾸고 다른 그룹들과 합쳐질 수 있다. -> 이를 가능하게 하려면, 0인 좌표의 인접한 칸에 다른 그룹이 있어야 한다. * 만약, 0인 좌표가 다른 그룹과 인접해 있다면 (연합 그룹을 형성하는 1의 개수와 현재 그룹의 개수 +1 )의 최대값이 정답이 된다. * 주의해야 할 점은, 0이 같은 그룹으로 이루어진 1들로 둘러싸여져있을 수 있기 때문에 중복으로 더해주는 것을 방지해야 한다. (set에 그룹의 라벨을 넣어주어서 중복으로 세지 않도록 하였다. ) 1 .. 공감수 0 댓글수 0 2020. 4. 20.
  • [BOJ] 17822. 원판 돌리기 * rotate에서는 x의 배수인 원판들을 시계/반시계 방향으로 k번 회전한다. * deque를 사용해서 시계방향은 한 원판에서 가장 뒤에 있는 요소를 가장 앞에 삽입한다. (pop_back -> push_front) 반시계방향은 가장 앞에 있는 요소를 가장 뒤에 삽입한다. (pop_front->push_back) * deque에 저장된 값들을 다시 map에 넣는다. * removeNums()에서는 인접한 숫자들을 지운다. 만약, 전체 원판을 통틀어 지울 수가 없다면 평균값에 따라 원판의 값을 조절한다. * 각 좌표에서 상 하 좌 우를 살펴봤을 때 같은 수가 있으면 큐에 넣어준다. 만약, 전체 원판을 봤을 때 큐에 아무런 값도 없다면 지울 값이 없다는 것이다. * *평균값을 double로 구해줘야 한다... 공감수 0 댓글수 0 2020. 4. 19.
  • [BOJ] 16918. 봄버맨 * bombTime[] 폭탄이 설치되는 시간을 저장한다. * 처음 1초 동안 봄버맨은 아무것도 하지 않는다. -> n == 1일 때 입력받은 폭탄을 그대로 출력해야 한다. * 1초 동안 폭탄이 없는 곳에 폭탄을 설치한다. (이때 설치하는 폭탄은 first (처음 폭탄이 터지는 시간) + 2 시간에 터진다. ) * 1초 프로세스 도중에 sec == n이 되면 실행을 멈춘다. * 폭탄을 터트린다. (bomb(터질 폭탄 -> 이 시간에 터질 폭탄만 터트린다)) -> 1초 소요 * 폭탄은 터질 때 주변의 폭탄들을 같이 터트리기 때문에 자신과 같은 숫자를 가진 폭탄은 터트리지 않는다. * 주변의 폭탄을 터트린 후에 현재 터져야 할 폭탄들을 터트려준다. (62 ~ 72 line) #include #include u.. 공감수 0 댓글수 0 2020. 4. 17.
  • [BOJ] 9328. 열쇠 * BFS로 완전 탐색을 한다. * 열쇠 상태를 계속 저장한다. (keystate) * 상근이는 빌딩 밖을 자유럽게 돌아다닐 수 있기 때문에 맵의 바깥쪽은 전부 '.'으로 만들어준다. *(0,0)부터 탐색을 시작한다. - 문을 만나면 지금 가지고 있는 키로 열 수 있는지 확인한다. 열 수 있다면 빈공간('.')으로 만들어준다. - 문서를 만나면 훔칠 수 있는 문서의 개수인 (res)를 1만큼 증가시키고 빈공간('.')으로 만들어준다. - 열쇠를 만나면 keystate를 비트마스킹을 이용하여 값을 변경해주고 빈 공간으로 만들어준다. - 여기서 중요한 것은 열쇠를 만났을 때 지금 까지 방문했던 좌표 중에 이제는 열 수 있는 문이 있을 수도 있기 때문에 visited 배열을 초기화한다. (초기화하는 방법 말고.. 공감수 0 댓글수 0 2020. 4. 16.
  • [BOJ] 14391. 종이조각 * (0,0) ~ (n-1, m-1) 까지 완전 탐색하면서 백트래킹으로 전수조사를 한다. * 방문 표시 된 좌표는 가로로 숫자를 만드는 부분이고, 방문 표시가 안 된 부분은 세로로 숫자를 만드는 부분이다. T T T T 이렇게 방문표시가 되어있다면 이렇게 방문 표시가 된 부분은 가로로 직사각형을 만들고. 아닌 부분들은 세로로 직사각형을 만든다. * 이어지는 숫자를 string으로 만들어서 sum에 누적합을 해 준다. #include #include #include using namespace std; int n, m; char map[5][5]; int dx[2] = {1, 0}, dy[2] = {0, 1}; bool visited[5][5]; int ans = 0; bool chk[5][5]; int .. 공감수 0 댓글수 0 2020. 4. 16.
  • [BOJ] 1600. 말이 되고픈 원숭이 * 최단 거리가 정답이 아닐 수도 있다. * 1 3 5 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 처럼 도착 지점이 장애물로 막혀져있는 경우 0 0 0 x 0 0 0 x 0 1 0 0 0 1 0 x로 표시되어있는 지점까지 원숭이로 이동한 후 말의 이동을 하는 방법이 도착할 수 있는 최선의 방법이다. * 큐에는 4가지 값이 들어간다. {움직인 횟수, 말로 움직인 횟수, 좌표} 말로 움직인 횟수가 k보다 작을때까지만 말로 움직인 좌표를 큐에 넣을 수 있다. 원숭이로 움직인 횟수는 항상 넣는다. (최단 경로 != 정답) *코드가 깔끔하지 않다. *dx / dy => 상하좌우 cdx / cdy => 대각선 #include #include #include #define INF 987654321 usin.. 공감수 0 댓글수 0 2020. 4. 7.
  • [BOJ] 9470. Strahler 순서 + TC * 위상정렬을 이용 * 큐에서 방문하는 노드로 들어오는 가진 강의 순서가 가장 큰 값을 maxCost[] 에 저장한다. (이 값은 항상 최대값만 저장) * cost[]에는 가장 큰 값을 maxx라고 가정한다면 maxx가 1번 들어오면 maxx값을 그대로 저장하고 2번이상 들어오면 maxx+1 을 저장한다. * maxCost와 cost를 따로 두어야 한다. 같은 배열에 저장한다면 maxCost[] 의 값이 변경되면서 정답이 달라지기 때문이다. 간단하게 예를 든다면 3 4 2 4 1 4 이렇게 간선이 주어져있다고 가정하자. 1,2,3 번 노드는 강/호수 또는 바다와 인접한 노드이므로 1의 값을 가진다. 4번이 Strahler순서가 되는 값을 가질 텐데, indegree[4] = 3이다. 처음 1의 인접리스트.. 공감수 0 댓글수 0 2020. 4. 1.
  • [BOJ] 1280. 나무심기 *세그먼트 트리를 사용한다. *현재 나무의 좌표가 [pos]라고 가정한다. pos가 나온 시점보다 앞에 심어진 나무 중 pos보다 좌표의 크기가 큰 좌표의 합 = sumUpper 개수 = a pos가 나온 시점보다 앞에 심어진 나무 중 pos보다 좌표의 크기가 작은 좌표의 합 = sumLower 개수 = b 3 2 0 4 1 이렇게 다섯 개의 나무가 심어질 것이다. 3의 관점에서 sumUpper = 0/ sumLower = 0 / a = 0 / b = 0 => cost = 0 2의 관점에서 sumUpper = 3 / sumLower = 0 / a = 1 / b = 0 => 좌표 사이의 거리를 구하는 것이기 때문에 sumUpper - pos*a를 해줘야 한다. (각 좌표에서 기준 좌표를 빼주는 것과 같다).. 공감수 0 댓글수 0 2020. 3. 30.
  • [BOJ] 2636. 치즈 * 치즈가 없는 좌표(0)에서 탐색할 수 있는 곳에 (상하좌우) 치즈가 있는 좌표(1)가 있다면 -> 이번 타임에 녹는 치즈이다. * 큐를 돌고 있는 상황에서 치즈를 바로 없애버리면 (1-> 0) 한 타임에 모든 치즈가 녹아버린다. * 위 상황을 방지하기 위해 이번 타임에 녹은 치즈는 map에 -1로 표시한다. * 치즈의 개수를 셀 때 -1인 좌표를 0으로 바꾼다. (벡터에 넣어주고 그 좌표들만 0으로 바꿔줘도 되지만, 어차피 치즈 개수 셀 때 모든 맵의 좌표를 탐색하기 때문에 이 때 바꿔주는 것으로 했다.) * 치즈가 모두 녹아 없을 때까지 (check() == True) 반복한다. * 치즈가 모두 녹기 한 시간 전에 있는 치즈의 개수를 세야 하기 때문에 howmanyCheese()를 만들었다. 더 효.. 공감수 0 댓글수 0 2020. 3. 29.
  • [BOJ] 18808. 스티커 붙이기 *단순 시뮬레이션 *스티커가 회전한 결과를 미리 저장한다. sticker[100][4][10][10] 0: 0도 1: 90도 2: 180도 3:270도 *스티커가 순서대로가 아니라 조합을 구하는 건 줄 알고 시간초과를 걱정했는데 다행히 순서대로 붙이는 것이다. 스티커를 순서대로 불러오면서 4방향을 모두 본다. check() 에서는 지금 범위에 스티커를 붙일 수 있는지 없는지를 확인하고, 붙일 수 있으면 넣는다. 여러 곳을 붙일 수 있으면 가장 위쪽을 선택하는 것이기 때문에 그리디하게 해결할 수 있다. *스티커의 높이와 너비는 차지하는 칸과 동일하지 않기 때문에 sizes라는 백터배열에 저장한 후 가져왔다. *코드가 많이 더럽다. 시뮬레이션 문제이니, 풀이 방법만 참고하시길.. 더보기 #include #i.. 공감수 0 댓글수 0 2020. 3. 25.
  • [BOJ] 18809. Gaaaaaaaaaarden * 배양액들의 조합을 구해서 배치한다. * 큐를 [초록색 배양액, 빨간색 배양액] 으로 두 개를 사용하는데 depth와 좌표 정보를 넣었다. depth는 처음에 문제를 잘 못 이해해서 예시를 보고 추가했다. G 1 or 2 R 이렇게 되어있을 때만 가운데 좌표에 꽃이 필 수 있다. 동시에 도달했을 때의 정보를 넣어줘야 하는데 그 정보를 depth로 기록했다. *depth를 기록했다면 이 정보를 빠르게 찾아내야 하는데, 이 정보는 dp[][] 배열에 기록해서 빨간색 배양액이 다음에 갈 곳에 이미 초록색 배양액이 있다. -> dp[nx][ny] 가 depth + 1 이면 초록색 배양액이 방금 전에 도달한 곳이다라는 정보를 찾아낼 수 있다. -> 꽃을 틔운다. *50*50 인데 조합까지 해서 그런지 시간이 꽤.. 공감수 0 댓글수 0 2020. 3. 25.
  • [BOJ] 10799. 쇠막대기 (C) *스택 자료구조 구현 연습을 위해 C로 풀이 *() 는 레이저이므로 레이저가 나올 때마다 스택에 있는 [(] 의 개수만큼 더해준다. (쇠막대기가 잘라지니까) *[(]는 스택에 푸시 (레이저는 푸시 안함) *[)]는 스택에서 팝하는데 이때, sum++ 을 해줘야 한다. ((()())) 이렇게 있다면 보기 편하게 레이저를 *로 치환한다. ( (* *) ) 이렇게 될 것이다. 그럼 막대는 ( (* *) ) --- -> - - - ------ -> -- -- -- 이렇게 되는 데 레이저를 만날 때마다 스택에 있는 개수만큼 막대의 개수가 증가하게 된다. 막대의 끝을 의미하는 [)]가 나올 때는 나누어진 막대의 가장 오른쪽 개수를 세야 하기 때문에 sum++을 해준다. #include #include #includ.. 공감수 1 댓글수 0 2020. 3. 24.
  • [BOJ] 1158. 요세푸스 문제 (C) *큐 구현 연습을 위해 C로 품. #include #include #include //큐 구현하기 #define MAXX 5001 struct Queue { int num[MAXX]; int front, back; }; int isEmpty(struct Queue *q) { if (q->back == q->front) return 1; return 0; } int isFull(struct Queue *q) { int tmp = (q->back+1)%MAXX; if (tmp == q->front) { //back+1 을 MAXX로 나눈 값이 front와 같으면 //가득 차 있다. return 1; } return 0; } void push(struct Queue *q, int data) { if (isFu.. 공감수 0 댓글수 0 2020. 3. 24.
  • [BOJ] 2151. 거울설치 + TC *거울이 [\] [/] 이 두 방향으로 있다고 생각하고 풀어야 한다. 처음에는 45도이기 때문에 [/] 만 생각하고 풀었다가 아니라는 것을 알게 됐다. *처음 [#] 좌표에서 출발해서 4방향 모두 큐에 넣는다. *각 방향으로 한 칸 앞으로 전진한 좌표가 거울이면 방향을 바꾸어서 큐에 넣고, 방향을 바꾸지 않는 상태로도 큐에 넣는다. 이 좌표에 거울을 설치하지 않는 경우도 생각한다. 3 ... *!# #!! 이 예시를 보면 (1, 3)에서 출발해서 (3,1)로 가야하는데 남쪽 방향으로 (3,3)의 거울로 간 후, 방향을 한 번 바꾸면 바로 (3,1)에 접근가능하다. #include #include #include #include #include #define INF 987654321 using namesp.. 공감수 0 댓글수 0 2020. 3. 18.
  • [BOJ] 9376. 탈옥 *세 지점에서 bfs를 실행한다. 상근이(0,0) / 죄수 2명 *상근이는 건물 밖을 마음대로 나다닐 수 있기 때문에 맵의 크기를 0,0~h+1, w+1으로 잡아줘야 한다. *상근이를 포함한 각 죄수들이 건물 밖으로 향하는데 여는 문의 개수를 dist[][]에 저장한다. *각 죄수들이 문을 열고 나가도록 코드를 작성하지만 실제로는 상근이가 두 죄수를 데리고 가기 때문에 세 명 다 문을 열 수 있는 가능성을 없애줘야 한다. (정답으로 요구한 것은 최소값이기 때문에) #include #include #include #include #include /* BOJ 9476.탈옥 */ using namespace std; int h, w; char map[102][102]; typedef pair pp; typed.. 공감수 0 댓글수 0 2020. 3. 18.
  • [BOJ] 12094. 2048(Hard) *2048(easy)와 풀이단계는 비슷하지만, 가지치기를 해줘야 한다. (최대 횟수가 2배로 늘었기 때문에) -가지치기 1) 변경된 맵이 변경되기 이전의 맵과 동일한 경우 -> 이 방향으로는 더 이상 나아가지 않는다. 2) 맵에서 최대값을 찾을때, 최대값은 2승씩 커진다. (cnt==10 이라면 가장 최대값은 1024가 될 것이다. ) 이 특징을 이용해서 현재 depth에서 최대값에 도달할 수 있는 지 확인한다. (즉, 한 번 10번까지 변경된 맵에서 최대값을 추출한 후 maxBlock[10] = 1024 / maxBlock[9] = 512 .... 이런 식으로 미리 저장을 해 놓는다.) *실제 최대값은 1024가 아닐 수 있다. 3) 현재 맵에서 구한 최대값이 현재 depth(==cnt)에서 나와야 하.. 공감수 0 댓글수 0 2020. 3. 18.
  • [BOJ] 16638. 괄호 추가하기2 *괄호 추가하기1에서 연산자 우선순위만 추가 (계산 단계 하나만 추가됐다) *숫자 자리수를 계산하기 번거로와서 string으로 처리함 2019/10/08 - [BOJ/C++] - [BOJ] 괄호추가하기 [BOJ] 괄호추가하기 문제 길이가 N인 수식이 있다. 수식은 0보다 크거나 같고, 9보다 작거나 같은 정수와 연산자(+, -, ×)로 이루어져 있다. 연산자 우선순위는 모두 동일하기 때문에, 수식을 계산할 때는 왼쪽에서부터 순서대.. jayrightthere.tistory.com *단계 1) 괄호 추가 (addd) - added[i] = true 인 부분은 괄호에 속하는 숫자들이다. - 괄호 안에 연산자는 하나만 들어갈 수 있기 때문에 연산자를 기준으로 i와 i+2를 검사한다. 2) added[i] ==.. 공감수 0 댓글수 0 2020. 3. 17.
  • [BOJ] 16988. Baaaaaaaaaduk2 (Easy) *조합을 이용하여 2개의 빈칸 좌표에 내 돌(1)을 놓은 후, 죽일 수 있는 상대 돌의 최대값을 계산한다. *죽일 수 있는 상대 돌 그룹은 내 돌(1)로 둘러싸여져 있어야 한다. 하지만 그것을 증명하는 것보다는 돌 그룹의 상하좌우에 빈칸(0)이 있으면 그 돌 그룹은 죽을 수 없다고 간주하는 것이 더 구현하기 쉽다. #include #include #include #include using namespace std; int n, m, ans = 0; int map[21][21]; typedef pair pp; vector emt, enemy; int emtCnt = 0; bool visited[500], chk[21][21]; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1.. 공감수 0 댓글수 0 2020. 3. 16.
  • [BOJ] 10711. 모래성 *가장자리는 항상 모래가 있는 부분이기 때문에 1,1 ~ h-1,w-1 의 부분 중 8방향을 살펴봤을 때 '.' 인 부분이 자기 자신보다 많은 경우만 큐에 넣는다. 즉, 큐에는 이제 사라질 좌표들만 넣는다. *큐에는 파도에 휩쓸려 사라질 부분들만 넣어지기 때문에 이 부분을 기준으로 주변에 있는 성들을 탐색하면 된다. *더 이상 큐에 넣을게 없으면 (= 없어질 게 없으면) 종료 #include #include #include using namespace std; int h, w; char map[1001][1001]; bool visited[1001][1001]; int age[1001][1001]; typedef pair pp; typedef pair ppp; int dx[8] = { -1, -1, -1.. 공감수 0 댓글수 0 2020. 3. 15.
  • [BOJ] 5557. 1학년 *dp[][] 에는 현재 인덱스에서 나온 결과에 따라 경우의 수를 저장한다. 8 3 2 4 8 7 2 4 0 8 8 dp[0][8] = 1 1. 8+3 == 11 로 0과 20 사이의 수이므로 dp[1][11] = 1 2. 8-3 == 5 dp[1][5] = 1 이런 식으로 경우의 수를 표시해야 한다. *하지만 이 경우가 마지막에 부등호가 성립되어야 하기 때문에 부등호가 나와야 하는 직전의 인덱스 (n-1)까지 간 후에 숫자들을 저장하고 있는 num[n-1]의 값과 현재까지 계산한 값이 같다면 1을 반환 / 같지 않다면 0을 반환한다. #include #include #include using namespace std; typedef unsigned long long ll; int n; int num[1.. 공감수 0 댓글수 0 2020. 3. 14.
  • [BOJ] 3709. 레이저빔은 어디로 *(0,0)인 경우만 잘 파악하면 된다. -우향우 거울이 있는 곳으로 이전과 같은 방향으로 또 가게 되는 경우 (무한루프에 빠짐) -갈 수 있는 경로를 다 가봤는데 맵을 떠나지 못하는 경우(queue를 다 돌았는데 보드 밖으로 못 나간 경우) *visited는 방문 표시를 하는 배열로, 3차원으로 기록한다. (좌표, 방향) -> 우향우 거울이 있는 곳으로 이전과 같은 방향으로 다시 들어오면 (0,0)을 반환한다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; int n; int map[52][52]; bool visited[52][52][4]; int dx[4] = { -1,1,0,0 }, d.. 공감수 0 댓글수 0 2020. 3. 13.
  • [BOJ] 1520. 내리막길 *dfs와 dp를 이용하여 풀이 *도착 지점(m-1, n-1)부터 시작해서 (0,0)에 도착하면 1을 리턴하여 갈 수 있는 경로임을 저장한다. *만약, 이미 한 번 지나온 곳을 다시 가게 되면 중복 탐색을 할 필요가 없기 때문에 저장된 값을 리턴해준다. *모두 탐색했을 때 dp[m-1][n-1]에 저장된 값이 정답이다. *길을 중복 탐색하지 않아야 TLE를 피할 수 있다. #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int m, n, ans = 0; int map[501][501]; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }; int dp[501][501]; bool.. 공감수 0 댓글수 0 2020. 3. 13.
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

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

    © Kakao Corp.