반응형 Problem Solving/BOJ228 백준 11659번 구간 합 구하기 4 - 스위프트(Swift) 풀이 + 그림 설명 1. 첫 번째 수부터 i번째 수 까지의 합을 저장하는 누적합 배열을 만든다. psum[i] = arr[0] + arr[1] + arr[2] + ... + arr[i] 2. arr[i] ~ arr[j] 의 구간 합은 psum[j] - psum[i - 1]과 같다. 3. i = 0인 경우 예외 처리를 해준다. 1. 첫 번째 수부터 i번째 수 까지의 합을 저장하는 누적합 배열을 만든다. psum[i] = arr[0] + arr[1] + arr[2] + ... + arr[i] 구간 i부터 j까지 반복문을 돌면서 실제로 돌면 M개의 쿼리에 대해 O(N)이 걸리는 작업을 수행하므로 총 O(NM)의 시간 복잡도를 갖는다. 이 방법으로는 N과 M이 각각 최대 10^5이므로 시간초과가 날 것이다. 구간합을 O(1)에 구.. 2022. 1. 19. 백준 7569번 토마토 - 스위프트(Swift) 풀이 + 그림 설명 1. 토마토를 그래프의 정점으로 생각한다. 2. BFS로 하루가 지날 때마다 인접한 토마토들을 하나씩 익혀가는 것을 구현한다. 3. 마지막에 안 익은 토마토가 있는지 확인한다. 1. 토마토를 그래프의 정점으로 생각한다. 들어있지 않은 칸은 무시하고, 토마토들을 그래프의 정점으로 생각한다. 전체 상자를 그래프로 바꾸어줄 것이다. 2. BFS로 하루가 지날 때마다 인접한 토마토들을 하나씩 익혀가는 것을 구현한다. 빨간색은 익은 토마토이고, 초록색은 안 익은 토마토를 나타내었다. 빨간색 정점에 적힌 숫자는 첫 날로부터 며칠 후에 익었는지를 기록한 것이다. 처음부터 3개의 토마토가 익어있는 아래와 같은 상황이라고 하자. 하루가 지나 1일 째가 되면, 바로 옆에 붙어있는 초록색 토마토 3개가 추가로 아래와 같이 .. 2022. 1. 18. 백준 10026번 적록색약 - 스위프트(Swift) 풀이 1. 그리드의 각 칸을 그래프의 정점으로 생각한다. 2. 인접한 칸의 색이 같은 색이면 간선으로 연결한다. 3. 어떤 칸을 시작점으로 DFS/BFS를 하면 해당 칸이 속하는 구역 내의 모든 칸을 방문할 수 있다. 4. 따라서 DFS/BFS의 호출 횟수가 곧 구역의 개수이다. 5. 적록색약인 경우 그리드의 R과 G를 같은 색으로 취급해준다. 1. 그리드의 각 칸을 그래프의 정점으로 생각한다. 그리드 전체를 그래프로 생각할 수 있다. 각 칸을 정점으로 둔다. 2. 인접한 칸의 색이 같은 색이면 간선으로 연결한다. 상하좌우로 인접한 칸이 같은 색이면 같은 구역이므로, 간선으로 연결해준다. 이러면 같은 구역인 정점끼리만 간선으로 연결될 것이다. 3. 어떤 칸을 시작점으로 DFS/BFS를 하면 해당 칸이 속하는 .. 2022. 1. 18. 백준 5430번 AC - 스위프트(Swift) 풀이 + 그림 설명 1. 맨 앞을 가리키는 front, 맨 뒤를 가리키는 end, 역방향 여부를 저장하는 변수 reverse를 둔다. 2. R이 들어오면, swap(front, end)와 reverse.toggle()로 배열을 뒤집는 연산을 구현한다. 3. D가 들어오면 정방향이면 front++ 역방향이면 front--로 맨 앞 삭제를 구현한다. 4. front와 end의 대소 비교 + reverse 여부를 가지고 빈 배열인지 판단한다. 1. 맨 앞을 가리키는 front, 맨 뒤를 가리키는 end, 역방향 여부를 저장하는 변수 reverse를 둔다. 진짜로 배열을 뒤집으면 시간 초과가 날 것이다. 진짜로 배열을 뒤집지 말고, 생각만 뒤집는다. 왼쪽부터 읽던 것을 오른쪽부터 읽는 것처럼 말이다. 이것을 위해 front, en.. 2022. 1. 18. 백준 2667번 단지번호붙이기 - 스위프트(Swift) 풀이 + 그림 설명 1. 각 집을 그래프의 정점으로 생각한다. 2. 어떤 집을 시작점으로 DFS/BFS를 하면 해당 집이 속하는 단지 내의 모든 집을 방문할 수 있다. 3. 따라서 DFS/BFS의 호출 횟수가 곧 단지의 개수이고, 4. DFS/BFS를 돌면서 방문한 정점의 수가 한 단지 내에 속한 집의 수이다. 1. 각 집을 그래프의 정점으로 생각한다. 0인 곳은 갈 수 없으므로 무시하고, 1인 곳을 정점이라고 생각한다. 2. 어떤 집을 시작점으로 DFS/BFS를 하면 해당 집이 속하는 단지 내의 모든 집을 방문할 수 있다. (1, 1)을 시작점으로 그래프를 탐색해주면, 해당 단지 내의 모든 집을 방문할 수 있다. 탐색 방법은 DFS/BFS를 쓰면 된다. 이때 연결되지 않은 (1,4)와 (2,4)가 속한 단지는 방문을 하지.. 2022. 1. 17. 이전 1 ··· 37 38 39 40 41 42 43 ··· 46 다음 반응형
