백준
1.[백준] 불 (5427), 불! (4179)
전형적인 BFS(너비 우선 탐색)의 문제이다. 상근이는 불이 있는 쪽으로 가지 못하지만 불이 다가 오기 전 먼저 외각쪽으로 다가가면 탈출한다. 따라서 상근이의 위치를 먼저 큐에 넣어주고 BFS를 돌린다. pypy로 제출 위의 불과 비슷한 문제다. 차이점이 있다면 위의 문제는 상근이를 먼저 큐에 넣었지만, 여기선 불을 먼저 넣어야 통과가 된다.
2.[백준] 부분합 (1806)
투 포인터의 대표적인 예제이다. 투 포인터 알고리즘은 리스트가 있을 때 start, end 2개의 포인터가 모두 0부터 시작한다. 조건에 해당하지 않으면 end + 1 해주고, 해당 되면 start + 1 하며 원하는 값을 구하는 알고리즘이다. 시간 복잡도는 O(N)
3.[백준] 캐슬 디펜스 (17135)
https://www.acmicpc.net/problem/17135 브루트 포스 문제이다. 해골 병사가 col칸 중 3 곳의 위치에 배치할 수 있어서 순열(permutations)을 이용하여 풀었다. moveEnemy함수, attackEnemy함수, checkZero함수를 만들었으며, 각 함수는 결과를 곧바로 반영하면 문제가 생기기에 위치를 모두 구한뒤 ...
4.[백준] 연구소 2 (17141)
https://www.acmicpc.net/problem/17141 전형적인 BFS문제에 combination을 섞은 문제이다. 바이러스(2)가 존재하는 칸들의 좌표를 모두 구하고, m 값의 만큼 조합을 구하여 각 해당하는 조합에 대해 BFS를 돌려 최대 시간을 구하고, 그 중 최소 시간을 출력하면 된다.
5.[백준] 소수의 연속합 (1644)
https://www.acmicpc.net/problem/1644 먼저 n이하의 소수를 구한 뒤, 그 다음 연속합을 구하는 문제이다. 메모리 조건이 빡빡할 것 같아 에라스토네세의 체를 이용하기로 했다. 또한 연속합이니 투 포인터로 구현하면 될 것 같았다. 글을 쓰다 보니 solve 함수를 왜 구현했지? 라는 생각이 든다. while 조건문에서 바로바로 ...
6.[백준] RGB거리 2 (17404)
https://www.acmicpc.net/problem/17404 RGB 거리의 확장 형이다. 달라진게 있다면 마지막 집의 색과 1번 집의 색은 같으면 안되는게 추가 되었다. 많은 고민을 하다가 1번째 집의 색이 R일때 G일때 B일때 경우의 수를 따지기로 했다.
7.[백준] 컨베이어 벨트 위의 로봇 (20055)
https://www.acmicpc.net/problem/20055 삼성역량 SW 역량 기출 문제이다. 처음에 문제 해석하는데 헷갈려서 시간이 조금 소모되었다. "컨테이너벨트"와 "로봇"이 모두 rotate(1) 한다. 만약, 해당 로봇의 다음 칸의 컨테이너 벨트 값이 1이상이면 해당 값을 -= 1 하고 로봇의 위치도 옮겨준다. 컨테이너벨트의 0번째 값이...
8.[백준] 세 용액 (2473)
https://www.acmicpc.net/problem/2473 이 문제를 보고 완전 탐색인가? -> 5000 Combinaion 3 너무 큼 x 투 포인터로 접근 투 포인터에 이분 탐색을 써볼까? 하여 투 포인터 구현후 이분 탐색을 진행하였지만 투 포인터의 조건 자체가 잘못 되어 구현 실패. 다른 사람의 코드를 참고하니 애초에 끝에 있는 인자를 고정시...
9.[백준] 아맞다 우산 (17244)
https://www.acmicpc.net/problem/17244 정말 친절한 문제이다. 보자마자 BFS로 접근해야겠다는 생각을 했다. 물건의 개수가 최대 5개이므로 permutation을 써야겠다는 생각을 했지만 각 순열에 따라 BFS를 진행하면 시간초과가 날 것 같아 다른 방법으로 접근했다. 미리 BFS를 돌려, 각 지점에서(Start, X, En...
10.[백준] 벽 부수고 이동하기 4 (16946)
https://www.acmicpc.net/problem/16946 옛날에 시도 했을 때는 뭐야 쉬운 BFS네 하고 풀었지만 당연하게도 시간초과가 떴다. 그 때 어떤 방식으로 풀었는지 공부했었고 이제서야 풀게 되었다. 맵에서 인접한 0 그룹들을 방문처리하여 indexing 및 0의 개수를 저장하는 data 리스트를 만든다. 이후, 맵을 copy하여 복...
11.[백준] 마법사 상어와 복제 (23290)
https://www.acmicpc.net/problem/23290 골1 정도의 시뮬레이션 문제이다. 디버깅 2회 정도 때문에 3시간 정도 문제 풀이가 걸렸다. 문제에서 요구하는 바는 다음과 같다 복제 물고기 이동 상어 이동 잡아먹은 냄새 제거 복제 업데이트 2, 3번에서 요구하는 조건들이 까다로워 시간이 조금 걸릴만한 문제이다. 필자는 상어가 방문한...