![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/bgwLfH/btqG9BMiiMs/lB54wmONZZJQf9o7Bjoip0/img.png)
[BOJ 1966(S3) 리뷰] 시뮬레이션 문제다. 설명에 나온대로 프린터 큐가 존재하고 큐에 있는 각각의 작업마다 중요도가 있다. 큐의 맨앞 작업부터 하나씩 내보내야 하는데 만약 뒤에서 기다리고 있는 작업 중 현재의 작업보다 중요도가 높은 작업이 있다면 현재의 작업을 맨 뒤로 보내고 중요도가 높은 작업먼저 수행해야 한다. 이 때 M번 작업이 몇번만에 수행이되는지를 출력해야 한다. 가장 먼저 떠올렸던 구현은 큐가 빌때까지 반복문을 돌며 계속해서 뒤에있는 큐중 중요도가 있는작업이 있는지 확인하고 있다면 현재 큐를 뒤로 보내는 작업이다. 이 작업은 시간복잡도 O(n^2)에 수행된다. N이 100이하이므로 이 코드도 충분히 통과가 가능하지만, 나는 O(n)에 구현하기 위하여 우선순위큐를 이용했다. 우선순위큐를..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/HcspJ/btqG6CFkEfD/K5vyeKEhmcxs1DYZAADwIk/img.png)
[BOJ 17140(G4) 리뷰] 풀면서 이게 시간내에 통과될까? 라는 생각을 몇번했는지 모르겠다. 구현방법은 바로 떠올랐는데 어떻게 하면 효율적으로 처리할수 있을지가 문제였다. 아무리 고민해도 더 좋은 코드가 떠오르지 않아 그냥 처음 생각한 방법대로 했는데 TC가 약해서인지 통과되었다. 이 문제는 R연산과 C연산을 통해 이루어진다. R연산을 하면 각 행마다의 숫자와 등장횟수를 오름차순으로 변경해주면 된다. 예를들어 1 1 2 라는 행이 있으면 1이 2번등장 2가 1번등장했으므로 -> 2 1 1 2 로 변경된다. 1 2 1 2 1 3 3 3 3 라는 행렬이 있으면 1 2 2 1 0 0 1 1 2 1 3 1 3 3 0 0 0 0 으로 변경된다. 가장 큰 행을 기준으로 나머지값은 0으로 채워주는 작업도 필요..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/6N46h/btqG6BS9m2N/Wh5fmZD3ZbQ6rTHdKE9SMk/img.png)
입력 첫째 줄에 R, C, T (6 ≤ R, C ≤ 50, 1 ≤ T ≤ 1,000) 가 주어진다. 둘째 줄부터 R개의 줄에 Ar,c (-1 ≤ Ar,c ≤ 1,000)가 주어진다. 공기청정기가 설치된 곳은 Ar,c가 -1이고, 나머지 값은 미세먼지의 양이다. -1은 2번 위아래로 붙어져 있고, 가장 윗 행, 아랫 행과 두 칸이상 떨어져 있다. 출력 첫째 줄에 T초가 지난 후 구사과 방에 남아있는 미세먼지의 양을 출력한다. [BOJ 17144(G5) 리뷰] 골드5문제인데 왤케 어렵냐 .. 설명만 봤을땐 정말 간단해 보이는데 은근 구현하는게 까다로웠다. 문제를 풀때 주의해야 할 점은 미세먼지가 퍼질때 확산이 한번에 처리되어야 한다는점이다. 한번에 처리되지 않는다면 이전 칸에서 확산된 미세먼지가 다음 칸의 ..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/E1QGE/btqG4BlQ5nM/00TpRQdvtWSSkIVU001jDK/img.png)
[BOJ 17142(G4) 리뷰] 지난 연구소, 연구소 2 문제에 이어 다른버전의 문제이다. 근데 연구소 2 문제와 코드 한줄차이라 올릴까 말까 고민했다. 문제 설명을 잘 보면 지난 연구소 2와 동일한 조건인데, 기존에 바이러스였던 위치는 새로 바이러스가 퍼지는것이 아니므로 퍼지는 시간을 계산할때 포함시키지 않는다는 소리다. 그렇기에 아래처럼 방문한 곳이 기존의 바이러스 위치라면 거리값을 return 할때 포함하지 않도록 했다. 너무 간단해서 뭔가 놓친게 있나 싶어 문제를 다시 읽어봤는데 별 다른 문제점을 못찾길래 제출했더니 정답이 나왔다. (솔직히 정답나올지 몰랐음 이왜맞??..) #include #include #include #include #include using namespace std; #d..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/bK3Zvb/btqG2HzT3od/w5M6wHgGxcqFBqOlZHvMMk/img.png)
[BOJ 17141(G5) 리뷰] 지난번 풀었던 연구소 문제의 다른 버전이다. 저번엔 백트래킹으로 풀었지만 이번엔 next_permutation 함수를 이용했다. 지난번에는 벽을 세워 바이러스를 막아야했다면 이번엔 바이러스를 퍼지게할 위치를 고른다음 가장 빨리 바이러스가 퍼지는 위치에서 바이러스가 퍼지는 시간의 최소값을 출력해야한다. 그냥 주어진 시뮬레이션대로 구현하면 되는거라 별도의 디버깅없이 한번에 구현하고 바로 정답처리가 되었다. 1.먼저 next_permutation함수를 이용해서 총 K개의 바이러스 중 M개의 바이러스를 선택하여 벡터에 담는다. 2.선택된 바이러스의 좌표값을 기준으로 BFS를 수행하여 최대 DIST배열을 통해 최대 거리를 측정한다. 3.바이러스가 끝까지 퍼지지 않았다면 그 값은 ..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/ty5Nm/btqG7RHmoj5/GleHZBPiZ8sL0UFul25if0/img.png)
입력 첫째 줄에 공간의 크기 N(2 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 공간의 상태가 주어진다. 공간의 상태는 0, 1, 2, 3, 4, 5, 6, 9로 이루어져 있고, 아래와 같은 의미를 가진다. 0: 빈 칸 1, 2, 3, 4, 5, 6: 칸에 있는 물고기의 크기 9: 아기 상어의 위치 아기 상어는 공간에 한 마리 있다. 출력 첫째 줄에 아기 상어가 엄마 상어에게 도움을 요청하지 않고 물고기를 잡아먹을 수 있는 시간을 출력한다. [BOJ 16236(G5) 리뷰] 골드5문제라 간단한 BFS일줄 알았는데 은근 조건이 까다로워서 푸는데 애를 먹었다. BFS를통해 아기 상어가 먹을 수 있는 물고기의 거리를 재고, 가장 가까운 먹이를 먹어야 한다. 먹이를 먹을수록 아기 상어의 크기는 점점 ..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/lwmSl/btqG5LBibKT/gmSLlYKLtQXpwhgFset4xk/img.png)
[BOJ 16234(G5) 리뷰] 풀고 나면 굉장히 간단한 문제인데, 풀기 전에는 왜이렇게 어려운지 모르겠다. 처음에 문제 이해하는게 좀 힘들었는데 문제를 잘 살펴보니 전형적인 BFS문제이다. BFS를 통해 국경선이 열리는 조건에 대해 확인을 한 후 만족하는 그룹을 하나의 연합으로 보면 된다. 처음에는 먼저 BFS를 수행하여 각 국가마다 연합 INDEX를 부여하고 연합INDEX를 토대로 BFS를 다시 수행하여 값을 바꿔주려고 했는데 굉장히 비효율적인 작업임을 알아챘다. 그래서 벡터를 만들어 처음 BFS를 수행할때 각 연합INDEX에 바뀌게 될 값을 저장하고, 반복문을 통하여 연합INDEX에 맞게 저장된 값으로 바꿔주는 작업을 수행했다. 결과적으로 다음과 같다. 1.numbering (각 국가에 대해 국경..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/bPKjIz/btqGQb8ZBUP/zFak8kit4Pr4Tb78VnMs31/img.png)
[BOJ 3190(G5) 리뷰] snake 게임을 해본적이 있을것이다. 뱀을 조종하여 사과를 먹게되면 뱀의 길이가 점점 늘어난다. 뱀이 벽에 부딪히거나 자기 몸에 부딪힌다면 게임은 끝나게 된다. 이 문제는 snake게임의 규칙을 그대로 따른다. 맵이 주어지고 사과의 위치가 주어진다. 뱀은 주어진 명령대로 이동을하다가 사과를 만나면 길이가 늘어난다. 주어진 명령에 따라 게임을 수행했을 때 몇초후에 게임이 종료되는지를 구하는 문제이다. 일단 명령은 큐로받았다. 뱀을 이동시키기전에 큐의 front를 확인하여 현재 소요된 시간과 명령시간을 비교하여 명령에 맞게 방향을 바꿔주도록 했다. 그다음 시간이 지나면서 뱀을 이동시키고, 사과를 먹으면 길이를 늘려주면된다. 이 때 길이를 늘려주는 작업이 조금 헷갈렸다. 처음..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/0DL31/btqGXnN3sFj/CEu9rD84yqbcjh1abzInDk/img.png)
[BOJ 14891(S1) 리뷰] 톱니바퀴 문제. 입력으로 톱니바퀴의 번호와 방향이 주어진다. 톱니바퀴가 돌때 양 옆에있는 톱니바퀴와 맞닿아 있는 부분이 서로 다른 극이라면 옆에 있는 톱니바퀴도 회전하게 된다. 만약 옆에있는 톱니바퀴가 회전하며 또 다른 톱니바퀴와 다른 극 이라면 그 톱니바퀴도 회전해야 한다. 주의해야할 점은 톱니바퀴를 회전시키기 전에 미리 양 옆에 있는 톱니바퀴와 확인을 해준 후 회전시켜야 한다. 회전하는 톱니바퀴 각각에 대해 양 옆의 톱니바퀴를 확인해줘야하므로 재귀함수를 사용했고 이미 회전한 톱니바퀴는 다시 회전하지 않도록 하기 위해 isUsed배열을 사용했다. 처음엔 구현이 막막했는데 그냥 각각의 톱니바퀴에 대해 일일히 index로 접근해 확인하는 방법을 택했다. #include #..
![](http://i1.daumcdn.net/thumb/C148x148/?fname=https://blog.kakaocdn.net/dn/9mzxt/btqGK429ts5/iS0LgkMRY3tdKnqgyOjuDk/img.png)
[BOJ 11559(G5) 리뷰] 뿌요뿌요 문제다. 같은색의 뿌요가 4개인접해있으면 그 뿌요들은 터지며 없어진다. (애니팡과 비슷) 뿌요가 터지면 위에있는 뿌요들은 아래로 모두 내려오게 되며 아래로 내려왔을때 4개이상 인접해있는 뿌요가 있다면 또 터지게 된다. 이 때 연속적으로 몇번의 차례동안 뿌요가 터지는지 계산하는 문제이다. 애니팡을 해봤으면 하나를 터트렸을때 터진자리에 새로운 캐릭터가 채워지면서 연쇄적으로 터지는걸 경험한적이 있을것이다. 그걸 생각하며 구현하면 된다. 같은색의 뿌요를 찾는 BFS와 뿌요가 터진 후 뿌요들을 아래로 내려주는 함수를 구현하면 된다. #include #include #include #include #include #include #include #include #inclu..
- Total
- Today
- Yesterday
- nestjs
- 구현
- 동적계획법
- 스레드
- node.js
- 중앙대학교
- 컴퓨터 통신
- nodeJS
- BFS
- 벨만포드
- 시뮬레이션
- 재귀
- java
- dfs
- nest.js
- 백준
- typeORM
- 투포인터
- 세그먼트 트리
- boj
- 예외처리
- 그리디
- ReactNative
- 알고리즘
- 자바
- 컴퓨터 구조
- 백트래킹
- Computer Architecture
- 그래프
- 자바스크립트
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |