본문 바로가기

개발

 (99)
[BOJ] 구슬 탈출 2_13460 이 문제는 풀지 못하여 여러 블로그들을 참고하여 답지를 보며 풀었다. 풀이 방법 1. init() - R, B를 찾아 큐에 넣어주는 함수. 2. move - 해당 방향으로 벽에 부딪히거나, O이 나올 때 까지 움직여준다. 그리고 움직인 거리를 cnt로 세어 좌표와 함께 반환해 준다. ( * 여기서 cnt를 같이 구하여 반환하는 이유는 만약 빨간 공과 파란 공이 겹쳐졌을 때, 둘 중 더 많이 움직인 공이 다른 공 위에 있어야 한다. 때문에 cnt를 계산하여 더 큰 값을 가지는 것이 다른 공 위에 있는 상태로 만들기 위해서 이다. - 이 부분이 가장 어려운 부분 중 하나가 아닐까 싶다.) 3. solve() - 1, 2함수를 활용하여 문제를 푸는 함수이다. 궁금증 1. 뭔가 이렇게 하면 너무 많은 경우의 수..
[BOJ] 리모콘_1107 처음 접근 방식 이 문제를 처음 접근했을 때는, 입력받은 수를 문자열로 나눠서 여러 경우의 수를 고려해 주려고 했었다. 하지만 그러한 방식을 생각했을 때, 고려해 줘야 할 상황이 너무 많았고 결국 해결할 수 없었다. 그래서 여러 블로그들을 찾아 보았고, 이 문제는 브루트 포스라는 방법으로 푸는 문제라고 한다. 브루트 포스는 간단하게 말하자면 그냥 전수 조사와 같은 것이다. 모든 경우를 저언부 다 찾아주는 것이다. 풀이 방법 문제를 풀기 위해 생각할 때, 먼저 크게 두 가지를 생각해야 한다. 1. 처음부터 +, -로 계산한 것이 최소일 때. 2. 숫자 버튼으로 이동하여 +,-를 통해 구한 값이 최소일 때. 1번은 너무 간단하다. 처음 시작 값이 100번이라고 했으니 num = abs(100 - n)으로 구..
이진 탐색(Binary Search)란? 알고리즘 문제를 풀다 보면, 배열과 같은 list에서 특정 값을 구하는 문제를 자주 발견할 수 있다. 이러한 여러 데이터들이 있는 list에서 한 데이터를 Search하는 과정은 크게 두가지가 있다. 1. 순차 탐색(linear search): list의 데이터를 순차적으로 찾는 방식. ( 시간 복잡도: O(n) ) 2. 이진 탐색(binary search): list의 데이터를 반씩 나누며 찾는 방식. ( 시간 복잡도: O(log n) ) * 단, 반드시 정렬된 상태에서 탐색해야 한다. 가장 단순해 보이는 순차 탐색을 매번 사용하면 좋겠지만, 알고리즘 문제를 순차 탐색으로 풀다 보면 시간 초과가 나는 경우가 대다수이다. 그렇다면 이진 탐색에 대해 더 알아보도록 하겠다. 이진 탐색이란? 정렬된 데이터가 ..
[BOJ] 트리의 지름_1167 위 문제는 피지컬적인 부분보다 구현 방식을 생각해내지 못했다. 하지만 여러 다른 블로그들을 참고했을 때, 많은 분들이 생각해 내지 못한 것 같다.(아마 익혀야 하는 유형 중 하나인걸까,, 해결 방식은 다음과 같다. 1. 임의의 노드에서 출발하여 가장 긴 길이의 노드를 구한다. 2. 구한 노드 값에서 출발하여 같은 방식으로 가장 긴 길이를 구한다.(이것이 트리의 지름이 된다.) 트리가 있을 떄 가장 긴 부분을 구한 후, 그 노드에서 출발하여 가장 긴 길이를 구하면 그것이 지름이 된다. 이것을 생각해내는 것이 이 문제의 핵심이였다 (근데,, 왜 이게 지름인지는,,, 아직 정확하게 모르겠다. 그냥 뭔가 그럴 것 같긴 한데,, ㅡㅅㅡ) dfs2설명 우선 start, sum을 매개변수로 받았다. sum은 임의의 ..
[BOJ] 계단 오르기_2579 해당 문제는 DP를 이용해서 풀었다. dp[4] 이상부터는 dp[i] = max(dp[i - 2] + data[i], dp[i - 3] + data[i] + data[i - 1])코드로 dp값을 구할 수 있다. 그렇다면 왜 저 코드가 최대값을 의미하는가? 나는 dp를 풀 때, 문제를 보고 직접 써보며 규칙을 찾아내려고 하는 편이다. 그래서 찾은 규칙: 4번째부터는 해당 값이 최대가 되려면, 4보다 두칸 적은 계단까지의 최대값(dp[2])와 data[4] or 4보다 3칸 적은 계단까지의 최대값(dp[1])과 data3+data4를 더한 후 이 두개 중 최대값이 dp[4]값이 된다. 이 문제를 풀 때 dp[i-1]+data[i]와 같은 식으로 풀려고 했으나 그럼 dp[i-1]이 두칸 연속으로 얻은 값인지 ..
[BOJ] 1로 만들기_1463 위 문제는 전형적인 DP문제이다. 우선 문제를 리뷰하기 전에 DP의 탑다운 방식과 바텀업 방식의 차이에 대해 짚고 넘어가자. 동적 계획법이란? 큰 문제를 작은 문제들로 나누어 푸는 것을 일컫는 말이다. 동적 프로그래밍 방법 작은 문제로 나누어 해결할 떄, 중복된 값을 구하지 않고 메모제이션 하는 것이다. 메모제이션을 하는 방식과, 그렇지 않은 방식에 대해 설명하겠다. F는 피보나치 함수이다. 메모제이션을 하지 않고, 탑 다운 방식으로 피보나치 수열을 구한다면 작은 단위의 값을 반복해서 여러번 계산해야 한다. 이를 바텀업 방식으로 해결할 수 있다. 위와 같이 작은 단위의 값을 배열에 저장하여, 해당 값이 필요할 떄 작은 단위를 반복하여 계산하지 않게 된다. 1로 만들기 문제도 이러한 방식으로 해결할 수 있..
[BOJ] 단어 정렬_1181 이 문제는 내가 몰랐던 파이썬 문법으로 해결할 수 있었다. data.sort(key = lambda x: (x[1], x[0])) 을 하면 x[1]을 기준으로 정렬할 떄, 우선순위가 같은 것이 있다면 x[0]으로 비교해서 정렬하는 것이다. 그리고 word[0]에는 그냥 문자열을 넣었는데, data.sort(key = lambda x: (x[1], x[0]))에서 x[0]을 통해 파이썬에서 알아서 정렬해준다.
백준 빙산 2573 해당 문제의 정답 코드이다. 더보기 from _collections import deque import copy n, m = map(int, input().split()) dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] data = [list(map(int, input().split())) for _ in range(n)] # 얼음아 녹아라. def melting(): data_copy = copy.deepcopy(data) for i in range(n): for j in range(m): if data_copy[i][j] != 0: for z in range(4): nx, ny = i + dx[z], j + dy[z] if 0

티스토리툴바