조이의 개발 성장 다이어리

문제: https://www.acmicpc.net/problem/2437해당 문제는 풀다가 도저히 이해가 안가서 풀이를 보고 이해해보고자 했다 🥲알고리즘 분류를 보니, 그리디 알고리즘을 활용하여 푸는 문제라고 하는데 왜 이게 그리디 알고리즘인지는 아래에서 알아보도록 하자.우선 이 문제를 푸는 방법이다. https://aerocode.net/392 이분의 풀이를 참고했는데, 해당 풀이를 이해한 바는 다음과 같다. 1) "추들을 가지고 측정할 수 있다" = "추를 활용하여 ~ 범위 내의 무게를 측정할 수 있다" 라는 의미로 이해한다. --> 측정할 수 있는 범위를 수직선으로 그려보기2) 무게가 작은 추를 활용하여 측정할 수 있는 무게를 점점 늘려가야하므로, 추들을 오름차순으로 정렬 후 차례대로 올려본다. ..

문제: https://www.acmicpc.net/problem/9996이 문제는 처음에 한번에 못풀었고, 반례를 보고 이해한 다음에 두번째 풀이끝에 성공했다.문제를 풀 때 반례를 가능한한 많이 고려해야하고, 또 반례를 떠올리는 법을 반복적으로 연습해야 한다고 느꼈다. ❌ 첫번째 풀이 - 틀린 풀이n = int(input())expression = input().split("*")start = expression[0]end = expression[1]for _ in range(n): word = input() if word.startswith(start) and word.endswith(end): print("DA") else: print("NE") 해당 풀이는 65%에서 틀렸다는 결과가..

1. 문제: https://www.acmicpc.net/problem/10799이 문제는 인접한 쌍이 레이저, 여는 괄호와 닫는 괄호로 쇠막대기의 왼쪽과 오른쪽 끝의 쌍을 이룬다는 점에서 "스택"을 떠올렸다.그러나 규칙을 찾는 데 어려움을 겪고 제한 시간내에 풀지는 못했다 🥲 따라서 다른 사람의 풀이를 보고 이해한 바를 다시금 정리하고 문제를 풀어보았다. ✅ 풀이  이 규칙대로 코드를 짜면 다음과 같다.pipelines = input()stack = []answer = 0for idx, p in enumerate(pipelines): if p == "(": # 1 stack.append("(") else: if pipelines[idx-1] == "(": # 2. 레이저인 경우 ..

1. 문제: https://www.acmicpc.net/problem/4963해당 문제는 그래프 탐색을 이용하여 영역을 세는 문제다. 단 조금 특이한 점은 "대각선"으로 연결되어있는 사각형도 섬의 영역으로 친다는 점이라서 영역으로 봐야하는 범위가 늘어난다. ✅ 풀이import syssys.setrecursionlimit(10**6) #recursion error를 위해 limit 늘리기input = sys.stdin.readlinedx = [-1, 1, 0, 0, -1, -1, 1, 1]dy = [0, 0, -1, 1, -1, 1, -1, 1]def dfs(x, y): visited[x][y] = True for i in range(8): nx = x + dx[i] ny = y + d..

문제: https://www.acmicpc.net/problem/2559해당 문제는 슬라이딩 윈도우 개념을 활용하여 풀 수 있는 문제이다.슬라이딩 윈도우는 배열에서 하나의 틀(부분 배열)을 일정한 크기 만큼 이동시키며 문제를 풀이하는 알고리즘이다.문제의 예제 2를 참고하여 원리를 보면 다음 그림과 같다. 위와 같이 배열 안에서 분홍색의 고정된 크기만큼 이동하며 각 경우의 합을 세게 되는데, 한칸씩 이동할때마다 이전의 값을 삭제하되 이후의 값을 더하는 방식으로 시간복잡도를 줄이는 방식이다. 이 문제는 "연속적인 며칠 동안의 온도의 합이 가장 큰 값" 을 확인하는 문제이고, "연속적인"에서 고정된 크기 내의 원소들의 합을 구해야한다는 점과 배열의 원소 갯수인 N이 최대가 100,000 이하(=10^5)라는 ..

1. 문제: https://www.acmicpc.net/problem/1260그래프 탐색에 대한 복습 겸 DFS와 BFS 관련 문제를 풀이해보았다. ✅ 인접행렬 활용 풀이import sysfrom collections import dequeinput = sys.stdin.readlinen, m, v = map(int, input().split()) # 정점의 갯수, 간선의 갯수, 시작지점graph = [[0] * (n+1) for _ in range(n+1)]visited = [False] * (n+1)for i in range(m): start, end = map(int, input().split()) graph[start][end] = 1 # 양방향 연결 graph[end][start] = ..

문제: https://school.programmers.co.kr/learn/courses/30/lessons/161990✅ 풀이def solution(wallpaper): board_x_length = len(wallpaper) board_y_length = len(wallpaper[0]) answer = [51, 51, 0, 0] # 길이의 범위가 50까지이므로 최소값 비교 위한 초기값을 51로 설정 for x in range(board_x_length): for y in range(board_y_length): if wallpaper[x][y] == "#": answer[0] = min(answer[0]..

1. 문제: https://www.acmicpc.net/problem/14495✅ 첫번째 풀이n = int(input())arr = [1] * (n+3)if 1 - 초반에 n-1, n-3 인덱스의 예외사항에 걸리고 싶지 않아 n+3 크기의 초기값 1인 배열을 초기화했다.- 그리고 문제에 f(1) = f(2) = f(3) = 1이므로 이 경우에 1을 print하고, 아닌 경우에 해당 수열 공식을 따르는 것으로 처리했다. 하지만 다른 사람의 코드를 보면서 알게된 사실은 ! python의 range가 범위를 벗어나면 for문이 실행되지 않는다는 점이었다.즉, 위와 같이 1로 초기화했으면 if else문 분기처리하지 않아도 된다. ✅ 두번째 풀이n = int(input())arr = [1] * (n+3)for ..

문제: https://www.acmicpc.net/problem/1929오늘 공부한 내용 - 소수 알고리즘, 에라토스테네스의 체 소수란, 1과 자기 자신만을 약수로 가지는 수를 의미한다.이를 활용하여 일반적인 소수 구하는 알고리즘을 짜보면 다음과 같다. 소수 판별 알고리즘 def isPrimeNumber(x): for i in range(2, x): if x%i == 0: return False return True 그러나 해당 알고리즘을 사용하면 시간초과가 발생한다. m, n = map(int, input().split())arr = [i for i in range(m, n+1)]def isPrimeNumber(x): for i in range(2, x): if x%i == 0..