본문 바로가기

👨‍💻📱✍️🎢314

LeetCode 344 - Reverse String (Easy) 문제 LeetCode - 344번 풀이 과정 in place 한 방법으로 배열을 뒤집는 연산을 수행하는 문제입니다. 왼쪽 끝 과 오른쪽 끝 을 가리키는 두 개의 포인터를 활용해서 뒤집기 연산을 수행하면 됩니다. 코드 /** * @param {character[]} s * @return {void} Do not return anything, modify s in-place instead. */ var reverseString = function (s) { let lo = 0; let hi = s.length - 1; while (lo < hi) { [s[hi], s[lo]] = [s[lo], s[hi]]; lo += 1; hi -= 1; } return s; }; 2021. 4. 5.
BOJ 15732 - 도토리 숨기기 문제 백준 온라인 저지 - 15732번 풀이 과정 일정한 간격으로 도토리가 놓여있다고 했을 때 특정 순서의 도토리가 들어있는 상자의 위치를 찾는 문제입니다. 만약 주어진 규칙들을 모두 수행해보고 도토리의 위치를 찾는 브루트 포스 를 수행한다면 최악의 경우 O(NK) 이기 때문에 시간 초과가 발생합니다. 대신에 상한과 하한을 설정한 뒤 이분 탐색 을 활용해서 마지막 도토리가 있는 상자의 위치를 찾도록 하겠습니다. 각각의 위치에서 해당 지점이 마지막 도토리라는 사실을 어떻게 판단할 수 있을까요? 이는 바로 각 규칙을 모두 순회하면서 특정 지점 x 보다 앞에 있는 도토리의 개수를 세어주면 됩니다. 각 규칙의 시작 위치를 init , 간격을 step , 기준 지점을 x 라고 한다면 다음과 같은 부등식이 성립합니.. 2021. 3. 18.
BOJ 2178 - 미로 탐색 문제 백준 온라인 저지 - 2178번 풀이 과정 시작 지점에서 (N, M) 의 목표 지점에 도달하기 위한 최단 경로를 계산하는 BFS 문제입니다. 별다른 추가 조건 없이 기본적인 BFS 알고리즘을 구현해주면 됩니다. 코드 import sys from collections import deque N, M = list(map(int, sys.stdin.readline().split())) board = [list(map(int, sys.stdin.readline().strip())) for _ in range(N)] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] def bfs(x, y): q = deque() visit = [[0]*M for _ in range(N)] q.append(.. 2021. 3. 18.
BOJ 6593 - 상범 빌딩 문제 백준 온라인 저지 - 6593번 풀이 과정 시작 지점에서 목표 지점에 도달하기 위한 최단 거리를 구하는 BFS 문제입니다. 빌딩이 3차원이기 때문에 상태공간을 다음과 같이 정의해줍니다. visit[z][x][y] = z 층의 (x, y) 지점에 방문했는지 유무를 저장 여기서 z 축 을 첫번째 인덱스로 지정한 것은 구현상의 편의를 위한 것입니다. 각 지점들을 방문할 때 동서남북 및 위층, 아래층 까지 같이 탐색을 수행하며 도달 여부를 판단해주면 됩니다. 코드 import sys from collections import deque L, R, C = 0, 0, 0 building = [] dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] dz = [1, -1] def bfs(start.. 2021. 3. 18.
BOJ 16397 - 탈출 문제 백준 온라인 저지 - 16397번 풀이 과정 BFS 를 통해 목표 숫자에 도달하기 위한 최소 버튼 횟수를 구하는 문제입니다. 각각의 버튼을 누를 수 있는 조건이 주어져 있으므로 이를 기준으로 탐색을 수행하면됩니다. 숫자에 대한 연산(맨 앞자리 감소)은 Python의 슬라이싱을 활용하면 쉽게 구현할 수 있습니다. 코드 import sys from collections import deque N, T, G = list(map(int, sys.stdin.readline().split())) INF = 100000 def bfs(start): q = deque() visit = [0 for _ in range(INF)] q.append((start, 0)) visit[start] = 1 while q: h.. 2021. 3. 18.
BOJ 2563 - 색종이 문제 백준 온라인 저지 - 2563번 풀이 과정 색종이의 좌표값을 이용해서 겹친 부분의 넓이를 구하는 구현 문제입니다. 색종이를 놓을 도화지를 board 로 정의하고 각각의 색종이로 인해 덮인 부분을 1로 표기하면 겹치는 부분을 포함한 넓이를 쉽게 구할 수 있습니다. 코드 import sys N = int(input()) papers = [] for _ in range(N): papers.append(list(map(int, sys.stdin.readline().split()))) def solution(): board = [[0]*100 for _ in range(100)] # 색종이 채우기 for r, c in papers: for row in range(r, r+10): for col in rang.. 2021. 3. 18.

티스토리툴바