본문 바로가기
반응형

Problem Solving/BOJ228

백준 17298번 오큰수 - C++(cpp) 풀이 + 그림 설명 1. 오른쪽부터 왼쪽으로 가면서 오큰수를 구할 것이다. 2. 스택에는 앞으로 오큰수가 될 수 있는 수들만 들어있게 유지한다. 3. 어떤 수 x를 고려하는 시점에서의 스택 top이 x의 오큰수이다. 1. 오른쪽부터 왼쪽으로 가면서 오큰수를 구할 것이다. 오른쪽부터 왼쪽으로 가면서 오큰수를 구할 것이다. 즉 NGE(N), NGE(N-1), ..., NGE(2), NGE(1) 순으로 구할 것이다. 2. 스택에는 앞으로 오큰수가 될 수 있는 수들만 들어있게 유지한다. 스택을 사용한다. 스택에는 앞으로 어떤 수의 오큰수가 될 수 있는 수들만 들어있게 유지해준다. 주어진 수열을 높이가 있는 막대라고 생각해보자. 먼저 가장 오른쪽에 있는 7의 오큰수인 NGE(4)를 구해보자. 스택이 비어있으므로 7의 오큰수는 없다... 2022. 2. 17.
백준 3055번 탈출 - C++(cpp) 풀이 1. 물의 확장을 BFS로 시뮬레이션해서 각 빈칸에 물이 몇 분에 도착하는지 기록한다. 2. 고슴도치의 이동을 BFS로 시뮬레이션한다. 물이 도착하기 전에 이동할 수 있는 곳으로만 계속 이동한다. 3. 2번 과정에서 비버의 굴에 도착하면 그 시간을 출력한다. 1. 물의 확장을 BFS로 시뮬레이션해서 각 빈칸에 물이 몇 분에 도착하는지 기록한다. 물이 매 분 인접한 한 칸으로 확장되므로 너비우선탐색(BFS)로 시뮬레이션 할 수 있다. BFS에서의 depth가 곧 해당 칸에 물이 도착하기까지 걸리는 시간이다. 2. 고슴도치의 이동을 BFS로 시뮬레이션한다. 물이 도착하기 전에 이동할 수 있는 곳으로만 계속 이동한다. 고슴도치도 매 분 인접한 한 칸으로 이동하므로 BFS로 시뮬레이션할 수 있다. 인접한 칸으로.. 2022. 2. 17.
백준 2580번 스도쿠 - C++(cpp) 풀이 1. 백트래킹으로 빈자리를 차례로 채워나간다. 2. 최초 해답을 찾은 이후에는 더 이상 탐색할 필요가 없으므로 모든 탐색을 리턴으로 종료한다. 1. 백트래킹으로 빈자리를 차례로 채워나간다. 백트래킹 문제이다. 빈칸을 차례로 채워나갈 것이다. 아래 코드에서는 왼쪽 위부터 차례로 채웠다. 어떤 빈칸을 채울 때에는 1~9 중 빈칸에 들어갈 수 있는 수들을 전부 넣어본다. 빈칸에 들어갈 수 있는 수는 같은 행, 열, 블록에 있지 않아야 한다. 2. 최초 해답을 찾은 이후에는 더 이상 탐색할 필요가 없으므로 모든 탐색을 리턴으로 종료한다. 모든 칸을 다 채웠다면 해답을 찾은 것이다. 해답을 찾았는지 여부를 bool 전역 변수로 두고, 해답을 찾으면 이 변수에 기록한다. 이후 모든 탐색은 하지 않아도 되므로, 빈칸.. 2022. 2. 16.
백준 11505번 구간 곱 구하기 - C++(cpp) 풀이 1. 펜윅트리를 이용해서 업데이트와 누적곱을 연산을 구현한다. 2. 또 다른 펜윅트리를 이용해서 대상 구간 내에 0이 있는지 체크한다. 1. 펜윅트리를 이용해서 업데이트와 누적곱을 연산을 구현한다. 계속 변화하는 수열에서 구간곱을 구해야한다. 세그먼트트리 또는 펜윅트리를 사용한다. 아래 코드에서는 펜윅트리를 사용하였다. 구간곱 펜윅트리 구현은 아래와 같이 하였다. 초기 트리 배열의 값을 0이 아닌 1로 초기화한다. 나눗셈은 페르마의 소정리를 이용해 역원을 곱해주는 것으로 처리한다. b번째 수를 c로 업데이트 하는 연산은, 원래 값이 x라고 하면 b번째 수를 x로 나눈 뒤, 다시 c를 곱해주는 연산을 해주면 된다. 이때 x로 나누는 연산을 x의 모듈러 역원을 곱해주는 것으로 처리해준다. 어차피 출력해야 하.. 2022. 2. 16.
백준 5014번 스타트링크 - C++(cpp) 풀이 1. 각 층을 그래프의 정점으로 생각한다. 2. U버튼이나 D버튼으로 이동할 수 있는 층은 가중치 1짜리 방향 간선으로 연결한다. 3. BFS를 사용해 S번 정점에서 시작해 G번 정점으로 가는 최단 거리를 구한다. 1. 각 층을 그래프의 정점으로 생각한다. 최단거리 문제이므로 그래프로 바꾸어 생각해줄 것이다. 2. U버튼이나 D버튼으로 이동할 수 있는 층은 가중치 1짜리 방향 간선으로 연결한다. 엘리베이터를 통해 이동할 수 있는 층은 방향 간선으로 연결해줄 것이다. 버튼을 1번 눌러 이동할 수 있으므로 가중치 1짜리 방향 간선으로 연결해준다. N층에서 N+U층으로 가는 방향 간선과 N-D층으로 가는 방향 간선을 추가해주면 된다. 이때 N+U와 N-D가 1이상 F이하여야 한다. 3. BFS를 사용해 S번 .. 2022. 2. 15.
반응형

티스토리툴바