본문 바로가기

전체 글229

[백준] 1753번 최단경로(python) https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 1. 난이도 골드4 (🥇) 2. 내가 작성한 코드 import heapq import sys input = sys.stdin.readline INF = int(1e9) v,e = map(int,input().rstrip().split()) #v는 정점, e는 간선 start = int(input().rstrip()) #시작 정점 번호 distance = [IN.. 2023. 2. 24.
❗문제 메모 - 그래프❗ 해결한 문제의 양이 증가하면서 좋은 문제를 양치기만 하고 끝내면 안 될 것 같다는 생각이 들었다. 이 게시물에 푼 문제들에 대한 간단한 기록을 남겨보고자 한다. ## 노란색 복습 필요 x ## 초록색 복습 필요 o ## 빨간색 복습 진행 했으나 아직도 어려움 ## 보라색 개중요 ## 회색 잘 풀었는데 다시 보면 좋을 듯? 깊이 우선 탐색 / 넓이 우선 탐색 백준 2468번 안전영역 (실버1) / 2667번 단지번호 붙이기(실버1) 문제를 풀며 단지번호 붙이기와 유사하네? 라는 생각이 들었다. 우선 안전영역 문제는 비가 점점 차오른다고 가정했을 때, 각자 떨어져 있는 안전영역의 개수를 세고 -> 비가 점점 차오르던 각각 시기의 안전영역 개수 중 가장 큰 값을 return 하는 문제이다. 단지번호 붙이기는 .. 2023. 2. 23.
[백준] 2206번 벽 부수고 이동하기(python) https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 1. 난이도 골드3 (🥇) 아 진짜 넘나리 어려웠는데 막상 이해하니 해볼만 한 것 같다. 3차원 list를 이용해서 벽을 부순적이 있는 지 없는 지를 확인해주면 된다. 2. 코드 분석 1. n,m, maps는 다른 문제와 동일하게 입력을 받는다. 2. 방문 여부를 확인하기 위해 visit 리스트를 만든다. 이때, 같은 행과 열의 크기를 가진 2층짜리 3차원 리스트를 만든다.. 2023. 2. 23.
[백준] 1874번 스택수열(python) https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 1. 난이도 실버2 (🥈) 도대체 이게 무슨 문제인가 한참을 고민하다가 풀었다. 결론적으로 말하자면 stack을 적절하게 이용해서 input 의 순서와 같은 수열을 만들어 내는 것이다! 예제 입력 1을 보면 4-3-6-8-7-5-2-1 순서로 입력되는데, stack에서 pop한 값이 이 순서대로 나오면 된다. 2. .. 2023. 2. 23.
[백준] 4963번 섬의 개수(python) https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 1. 난이도 실버2 (🥈) 2. 내가 작성한 코드 from collections import deque import sys input = sys.stdin.readline def bfs(k): queue.append(k) visit[k[0]][k[1]] = 1 dx = [1, 1, 0, -1, -1, -1, 0, 1] dy = [0, 1, 1, 1, 0, -1, -1, -1] while qu.. 2023. 2. 22.
[백준] 11724번 연결 요소의 개수(python) https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 1. 난이도 실버2 (🥈) 2. 내가 작성한 코드 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline n, m = map(int, input().rstrip().split()) graph = [[] for _ in range(n+1)] for _ in range(m):.. 2023. 2. 20.
[프로그래머스] Level2 무인도 여행(python) https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 내가 작성한 코드 from collections import deque def bfs(i,maps,visit): cnt = int(maps[i[0]][i[1]]) #첫 방문 위치의 식량 visit[i[0]][i[1]] = 1 queue = deque() queue.append(i) dx = [-1,1,0,0] dy = [0,0,-1,1] while queue: x,y = queue.popl.. 2023. 2. 20.
[프로그래머스] Level2 숫자의 표현(python) https://school.programmers.co.kr/learn/courses/30/lessons/12924 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1. 내가 작성한 코드 def solution(n): num = 1 #시작점 answer = 0 #표현 가능한 횟수 while num = n: if result == n: answer += 1 num+=1 break return answer while문을 먼저 돌리고 for문을 돌렸는데, 더 간단하게 구현할 수 있다. 2. 수정 코드 def solution(n): answer = 0 for i i.. 2023. 2. 19.
[백준] 13023번 ABCDE(python) https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 1. 내가 작성한 코드(틀림) import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline def dfs(v): for i in relation[v]: if visit[i] == 0: visit[i] = visit[v] + 1 dfs(i) n,m = map(int, input().rstrip().split()) #n=친구수 m=관계수 relation = [[] for _ in range(n)] for i in range(m): a,b = map.. 2023. 2. 19.

티스토리툴바