조이의 개발 성장 다이어리

99클럽 코테스터디 8일차 TIL - 백준 9996

문제: 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%에서 틀렸다는 결과가..

99클럽 코테스터디 7일차 TIL - 백준 10799, 코드시그널 코딩테스트 준비

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. 레이저인 경우 ..

99클럽 코테스터디 6일차 TIL - 백준 4963, 백준 1012

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..

오늘은 Python으로 문자열 다루는 법을 익히기 위해 문자열 관련 문제를 풀었다.문제출처: https://www.acmicpc.net/workbook/view/72761. 문제: https://www.acmicpc.net/problem/11720✅ 풀이import sysinput = sys.stdin.readlinen = int(input())num = input().rstrip()print(sum(list(map(int, num)))) 💡 해당 문제를 통해 배운 문법/스킬- map(int, str): 문자열의 문자를 하나하나 int로 매핑- list(map ~~): 매핑한 결과를 배열화2. 문제: https://www.acmicpc.net/problem/11365✅ 풀이import sysinput ..

오늘은 최단 거리 알고리즘에 대해 공부하며 관련 문제를 풀었다.코딩테스트에서 나오는 대표적인 알고리즘은 "다익스트라", "벨만포드" 알고리즘이다.1. 문제: https://www.acmicpc.net/problem/1753다익스트라 알고리즘- 하나의 시작 노드에서 다른 모든 노드까지의 최단 경로를 찾는 알고리즘- 가중치가 양의 정수로만 이루어져있을 때 사용 가능한 알고리즘- 우선순위 큐(Heap) 사용하여, 가장 비용이 적은 경로를 먼저 탐색 ✅ 풀이import sysimport heapqinput = sys.stdin.readlineINF = int(1e9)v, e = map(int, input().split()) # 정점의 갯수 v, 간선의 갯수 estart = int(input())graph = ..

문제: 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..