알고리즘/문제

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 📌 - 처음 접근한 방법 내리막이 나올때마다 그 칸의 값을 다음 내리막 칸의 값에 더해준다 모든 경로를 전부 탐색해서 마지막 칸의 값을 출력 이렇게 브루트포스로 풀었었는데, 바로 메모리 초과가 났다 📌 - 두번째 접근 방법 시간초과와 메모리초과를 동시에 해결하려면 DFS만으로는 풀 수가 없다. DFS나 BFS를 사용하면서 DP개념을 활용해야 이 문제를 해결 할 수 있다. DFS로 경로의 끝까지 ..

https://school.programmers.co.kr/learn/courses/30/lessons/154540 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 📌 - 무인도 여행 - 접근 이 문제는 map의 크기도 100으로 제한되어 있고, 상,하,좌,우를 이용하면서 해당하는 경로의 숫자를 전부 더해주는 방식이라 DFS, BFS 문제라고 생각했고 백준의 안전 영역이나 빙산 문제와 비슷하다고 생각해서 BFS로 풀었다. 0,0부터 N,M까지 전부 탐색하면서 방문체크 방문하지 않은 섬일때 BFS를 이용해서 인접한 섬들의 수를 더해주고 다시 방문체크 인접한 ..

https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 해당 문제는 전에 푼 토마토 문제와 매우 유사하다. 본인이 푼 해결 방식은 이러하다 - 이 문제는 결국 낮은 숫자의 바이러스들부터 큰 숫자의 바이러스들까지 순서대로 퍼지게 만드는 것이 요점인데 순서를 정렬하기 위해 힙큐를 써서 해결을 했다. for 문으로 전체 배열을 돌면서 0이 아닌 바이러스들을 힙큐에 넣는다. 1초마다 BFS로 힙큐를 비우면서 인접한 배열의 정보를..

1️⃣ - 처음 생각한 풀이 3차원 배열을 만들어서 데이터를 넣는다. 전부 방문하면서 1일 경우, 주변 토마토들을 익힌다. 토마토를 익힐 수 없을 때, 반복을 종료하고 년도, 상태를 확인하고 출력한다 이런 식으로 풀이를 생각했었는데, 3차원으로 생각을 하려다보니 계속 복잡해지고 헷갈려서 자꾸 답이 틀려서 다른 방식을 찾아봤다. 2️⃣ - 두 번째 풀이 3차원 배열에서 1을 전부 queue에 담는다. - 담으면서 방문처리 bfs로 queue에 있는 좌표들을 빼면서 근처 좌표들을 queue에 다시 넣고 익히는 과정을 반복한다. - queue에 다음 좌표들을 넣을 때 년도를 같이 넣어준다. 바뀐 배열을 처음부터 비교해서 가장 큰 값 -1을 출력한다 from sys import stdin as s from co..

1️⃣ - 처음 생각한 코드 그래프에 경로를 전부 저장 bfs로 시작지점부터 경로 시작해서 이전 경로까지 거리를 계속 비교해가면서 더 작은 값을 저장 반복해서 마지막 최종 목적지 배열의 값 출력 from sys import stdin as s from collections import deque import heapq s = open('input.txt','rt') N = int(s.readline()) M = int(s.readline()) graph = {} for _ in range(M): start, end , dis = list(map(int,s.readline().split())) graph[start] = graph.get(start,[]) + [(dis,end)] start , end = ..

이 문제는 어려워서 정리 한다기 보다 인접리스트로 그래프를 만드는 것을 처음 접해서 기록 및 정리를 위해 작성한다. https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 처음 인접리스트를 배열로 구현한 코드 from sys import stdin as s s = open('input.txt','rt') n = int(s.readline()) graph = [[] for _ in range(n+1)] def preorder(num): if ..