본문 바로가기

알고리즘135

[Python] 백준 14502번 : 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 💡 문제 풀이 그래프 탐색 + 브루트 포스 문제이다. 벽을 단 3개만 설치해서 얻을 수 있는 최선의 경우를 찾아야 한다. 완전 탐색을 통해서 3개를 설치했을 때 발생하는 모든 경우를 따지고, bfs를 사용해서 주어진 경우를 따져서 안전 구역의 개수를 따져주면 된다. 주의해야 할 점은 깊은 복사를 사용하지 않으면 원본이 훼손된다는 점이다! ✔️ 느낀 점 이렇게 따지는 경우를 어떻게 해야 할지 몰랐는데 단순하게 .. 2023. 2. 22.
[Python] 소프티어 : 마이크로서버 https://softeer.ai/practice/info.do?idx=1&eid=628&sw_prbl_sbms_sn=157452 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💡 문제 풀이 투포인터(?) 문제이다. 요청의 크기가 300 ~ 900이고 서버는 900을 넘어가면 안 되기 때문에 결국 3가지 경우로 나뉜다. 한 서비스가 600을 넘어가는 경우. 다른 서비스를 추가할 수 없어서 서버 하나를 준다. 300짜리 서비스가 3개 들어오는 경우. 그 외 두 서비스가 900이하의 메모리를 잡아먹는 경우 따라서 투 포인터를 따라가면서 계산해주면 된다. ✔️ 느낀 점 처음에 deque를 이용해서 조건문으로 해결하려고 했다. 하지만 25점짜리 풀이었고 오답을 절대로 찾을 .. 2023. 2. 21.
[Python] 소프티어 : 거리 합 구하기 https://softeer.ai/practice/info.do?idx=1&eid=635&sw_prbl_sbms_sn=157103 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💡 문제 풀이 그래프 탐색 문제이다. 해결하지 못했다. ✔️ 느낀 점 보자마자 플로이드-워샬이 생각나서 접근했지만 시간초과로 실패 (O(n^3)), DFS로 접근했는데 중간 계산 로직을 구현하지 못해서 실패, 다익스트라로 접근했는데 개선된 버전을 사용해도 시간초과로 실패 (O(E^2logE)) DFS가 두 번 들어가면 풀린다고 하는데 솔직히 좋은 문제인지는 잘 모르겠다. 💻 코드 import sys input = sys.stdin.readline INF = int(1e9) n = int(inp.. 2023. 2. 20.
[Python] 소프티어 : 이미지 프로세싱 https://softeer.ai/practice/info.do?idx=1&eid=627&sw_prbl_sbms_sn=156768 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💡 문제 풀이 아주 가벼운 그래프 탐색 문제이다 (BFS) BFS로 풀었고 DFS도 가능하다. ✔️ 느낀 점 많이 그래프 탐색을 풀어봤다면 어렵지 않은 문제이다. 💻 코드 import sys input = sys.stdin.readline moves = [(1,0), (0,1), (-1,0), (0,-1)] h, w = map(int, input().split()) board = [list(map(int, input().split())) for _ in range(h)] q = int(inpu.. 2023. 2. 20.
[Python] 프로그래머스 : 기둥과 보 설치 https://school.programmers.co.kr/learn/courses/30/lessons/60061 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 💡 문제 풀이 구현 문제이다. 제거하거나 삭제했을 때 정상적으로 잘 연결되어 있는지 확인하면 된다. 주어진 조건만 잘 맞추면 된다. ✔️ 느낀 점 시간이 충분히 주어졌고, 입력은 1000을 안 넘어서 시간이 충분한데 너무 어렵게 구현하려다가 시간을 많이 잡아먹었다. 충분히 쉽게 풀 수 있었는데 아직 테크닉이 많이 부족한 것 같다. 💻 코드 def check(answer): for x, y, a i.. 2023. 2. 19.
[Python] 소프티어 : 로드 밸런서 트래픽 예측 https://softeer.ai/practice/info.do?idx=1&eid=629&sw_prbl_sbms_sn=156249 Softeer 연습문제를 담을 Set을 선택해주세요. 취소 확인 softeer.ai 💡 문제 풀이 구현 문제이다. 노드에 접근하는 순서가 존재하고 존재에 맞춰서 요청을 처리해 주면 된다. 1000건의 요청이 들어왔고, 루트 밸런서에 3, 5, 6번 밸런서가 연결되어 있으면 각 밸런서에 공통적으로 1000 // 3건 만큼 요청을 수행할 것이고 순서대로 진행되야 하니 1000 % 3 만큼 각 노드에 순서대로 1만큼 추가해 주면 된다. ✔️ 느낀 점 문제가 이해 안 가서 오래 걸렸고 중간에 순서가 있다는 걸 알아채지 못해서 시간을 많이 소비하였다. 그냥 재귀적으로 풀면 무조건 시간.. 2023. 2. 19.

티스토리툴바