분류 전체보기(76)
-
[BFS] 백준 1697 숨바꼭질
www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 수행 시간 : 1시간 30분 동생의 위치는 변하지 않고 수빈이의 위치만 변하게 되므로 수빈이의 위치를 받아서 BFS를 돌려주면 되는 문제였다. 다만 아이디어 생각하는데 1시간 이상을 투자했었다. 그리고 범위체크에 신경을 써줘야 예외 케이스에서 오류가 나지 않는다. #include #include using namespace std; bool visited[100001]; int n, ..
2021.03.16 -
[구현] 백준 17144 미세먼지 안녕!
www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 수행 시간: 3시간 골드 5수준의 삼성SW 기출이였던걸로 기억한다. 공기청정기의 위치좌표를 저장해주고 그 좌표를 통해 구현해주면 어렵지 않은 문제였다. #include #include using namespace std; int r, c, t; //r은 세로 c는 가로 t는 경과시간 int room[7][51]; int tmp_room[7][51]; int dx[4] = { 0,0,-1,1 }; int dy[..
2021.03.16 -
[BFS&구현] 백준 16236 아기상어
www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 수행 시간: 3시간 글을 오랜만에 올리는 것 같다.. 요즘 취준때문에 바쁘기도하고 사실 알고리즘은 거의 매일 풀었는데 풀기만하고 올리지를 않아서 오늘 몰아서 올릴 것 같다. 친구와 타임어택으로 푼 골드4 수준의 삼성 SW 역량테스트 문제다. 문제자체는 크게 어려움을 느끼지 못했지만 생각해야될 부분도 많고 조건이 너무 많아서 코드를 짜는데 오래 걸렸다. 특히 if (time > (t + 1)) { time..
2021.03.16 -
[DP&DFS] 백준 1890 점프
www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 수행 시간: 1시간 처음 도전해본 DP 문제! 요즘 친구와 타임어택으로 문제를 풀고 있는데, 수월하게 풀다가 마지막에 제출하는 과정에서 오류가 떠서 친구에게 답을 구했는데, 2의 63승 만큼의 메모리가 필요하므로 DP배열을 int형(4byte이므로 32bit 즉, 2의 32승)이 아닌 long long 형 (8 byte이므로 64bit 즉, 2의 64승) 으로 자료형을 바꿔줘야 했다. #include..
2021.03.08 -
[완전탐색] 백준 1051 숫자 정사각형
www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N*M크기의 직사각형이 있다. 각 칸은 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 또는 www.acmicpc.net 수행 시간: 1시간 (+- 10분) 나만 그런건지도 모르겠는데 브루트포스, 즉 완전탐색이나 그래프 같이 그래프 탐색 문제를 풀때, 알고리즘 아이디어 떠올리기가 가장 힘든거 같다. 이 문제는 실버3의 난이도 인데도 바로 직전 문제보다 안풀렸었던 것 같다. 이 문제의 아이디어는 정사각형의 변의 길이를 1~50 까지 하나씩 늘려가면서 점들을 찾아주는 방법을 사용하였다. 그러다보니 반복문이 3개나 들어가 있다. +..
2021.03.06 -
[구현] 백준 2564 경비원
www.acmicpc.net/problem/2564 2564번: 경비원 첫째 줄에 블록의 가로의 길이와 세로의 길이가 차례로 주어진다. 둘째 줄에 상점의 개수가 주어진다. 블록의 가로의 길이와 세로의 길이, 상점의 개수는 모두 100이하의 자연수이다. 이어 한 줄 www.acmicpc.net 수행 시간 : 50분 실버 1 난이도의 구현 문제였다. 확실히 구현이나 시뮬레이션 문제들은 레벨에 따라 체감난이도가 확 와닫는데 이번 문제도 크게 어렵진 않았다. 다만 규칙이나 이런 것들을 찾아서 코드를 확 줄일 수 있었지만, 타임어택으로 문제를 푸는 과정이므로 생각나는대로 코드를 짜다보니 지저분하고 길어졌다. #include #include #include using namespace std; int r, c, n..
2021.03.06