본문 바로가기

전체 글108

P18405. 경쟁적 전염 - 문제: https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net 설명 이전에 풀었던 토마토와 빙산과 비슷한 느낌을 받았다. 다만 본인은 문제에 나온 날짜만큼 반복문을 돌려, 총 3중 for문을 마주했는데 그렇게 풀지 않아도 된다. ✔️ 본인 문제 해결 방법 1. 매초마다 for문을 돌면서 방문하지 않았고, 0이 아닌 바이러스들을 queue에 담는다. 2. queue를 비우면서, 방문할 수 있는 지점을 확인한다. 아직 채.. 2023. 5. 4.
[크래프톤 정글] 22일 - 이분 그래프 오늘 한 일💪 - 알고리즘 문제 풀이 1707번: 이분 그래프 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 정말 사소한 이유로 디버깅에 엄청 오래 걸린 문제다... (함께 코드 봐주신 분들 정말 감사합니다.🙇‍♀️) 문제가 있는 코드 from sys import stdin as s from collections import deque s = open("input.txt", "rt") K = int(s.readline()) now_color = 1 # 1: RED, 0: None, -1: FALSE is_s.. 2023. 5. 4.
[크래프톤 정글] 21일 - 그래프 오늘 한 일✍️ - 정보처리기사 실기 시험 - 알고리즘 이론 공부(그래프) 그래프 이번 주차는 문제 풀이를 잘하는 것도 중요하지만, 그래프와 트리를 잘 이해하고 이를 응용해서 문제를 풀이하는 능력이 필요할 것 같다. 특히 이것을 무엇으로 구현하느냐에 따라 성능이 달라지기 때문에 적절한 자료형을 사용하는 것이 중요할 것이라 생각한다. 그래서 당장 문제를 푸는데에 집중하기보다 이론 공부를 함께 하면서 하고 있다. 그래서 내용들을 노션에 정리하면서 하고 있는데 내용이 좀 방대해서 여기서는 대략적인 내용만 작성하고 자세한 내용은 별도의 게시글을 작성하겠다. 그래프 구성 정점(Vertex): 대상이나 개체 간선(Edge): 이들 간의 관계 그래프 구분 유향 그래프(Directed Graph): 그래프의 방향을 가.. 2023. 5. 4.
[크래프톤 정글] 20일 - 탐색 오늘 한 일👊 - 정보처리기사 실기 시험 공부 - graph, tree 공부 범위 정리 - 알고리즘 문제 풀이: 11724 Python 2차원 배열 출력 2차원 배열을 깔끔하게 확인하고 싶다면, * 연산자와 sep 옵션을 이용한다. connection = [[0 for i in range(N)] for j in range(N)] print(*connection, sep='\n') ''' [0, 1, 0, 0, 1, 0] [1, 0, 0, 0, 1, 0] [0, 0, 0, 1, 0, 0] [0, 0, 1, 0, 0, 1] [1, 1, 0, 0, 0, 0] [0, 0, 0, 1, 0, 0] ''' Graph, Tree 이번 주차는 그래프를 공부하다보니, 내용이 무척 방대함이 와닿았다. 그래서 내가 어떤 부분.. 2023. 5. 4.
[크래프톤 정글] 19일 - 트리, PPAP 오늘 한 일👊 - tree 공부 - 알고리즘 문제 풀이 - 알고리즘 문제 오답(2주차 시험) __future__ 문이란? python3에서 쓰이는 문법을 python2에서 쓸 수 있게 해주는 문법이다. 새로운 버전으로 업데이트되지 않았거나, Tensorflow 사용 등 구버전의 언어를 쓰면서 최신 버전 기능을 사용할 때, __future__를 통해 상위 버전 기능을 쓸 수 있다. # python version2 print "hello world" # python version3 print("hello world") Reference https://teknology.tistory.com/5 list의 가장 마지막 위치에 있는 원소를 확인하는 방법 histogram = [1, 2, 3, 4, 5] print.. 2023. 5. 4.
[크래프톤 정글] 15일 오늘 한 일 - 알고리즘 문제 오답 - 알고리즘 문제 풀이(2110, 6549, 11866, 1654, 2740) Review 오늘은 이전에 푼 문제 중 정리가 필요한 것을 오답하고, 새로운 문제를 풀이하였다. P11053. 가장 긴 증가하는 부분 수열 완전 탐색, DP, 이진탐색 3가지 방식으로 모두 풀이했다. 이진탐색으로 했을 때 시간 차이가 크게 나서 신기했다. 문제를 풀다보니, 이진탐색은 특정한 값을 찾기보다는 범위를 좁혀가며 범인을 잡는 것처럼 탐색하는 것 같다. P11053. 가장 긴 증가하는 부분 수열 문제: https://www.acmicpc.net/problem/11053 가장 긴 증가하는 부분 수열 문제, 줄여서 LIS(Logest Increasing Subsequence)라고도 한다... 2023. 5. 4.
P2110. 공유기 설치 문제 링크: https://www.acmicpc.net/problem/2110 설명 이 문제는 어떤 풀이를 써야할지 잡히지 않아 어려움이 있었다. 일단 가장 인접한 두 공유기 사이의 거리를 최대로 라는 말이 이해가 가지 않았다. 이 말은 즉, 공유기 사이의 거리가 최대한 떨어져있도록 설계하라는 말이다. 이분탐색으로 풀려면 어떻게 해야할까? 가장 인접한 두 공유기 사이의 거리를 이분 탐색으로 구하여, 해당 거리에서 설치해야하는 공유기 개수를 만족하는지 확인하는 것이다. 예시를 살펴보자. 예시는 공유기 사이의 거리가 차례로(정렬된 상태에서) 1, 2, 4, 8, 9이다. 이때 최소한의 거리는 1이고 최대는 8이므로 거리의 중앙값은 (1 + 8) // 2로 4가 mid가 된다. 그럼 이 값을 기준으로 현재 집.. 2023. 5. 4.
P2493. 탑 문제: https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 설명 하나의 리스트에 넣고 오른쪽부터 시작하여 비교하면서 빼는 방식으로 하면 시간초과가 발생한다. 처음에 리스트에 넣을 때부터 비교하면서 넣는 방법은 어떨까? 주어진 값은 6-9-5-7-4 이다. stack = [] : 최댓값을 저장할 스택, 이후에 들어오는 값들과 비교한다. result = [] : 결과값을 저장할 스택 일단 신호를 수신받으려면, 최댓값이 크거나 같아야 한다. 스택이 비.. 2023. 5. 4.
P2805. 나무 자르기 - 문제: https://www.acmicpc.net/problem/2805 설명 이 문제를 풀 때 계속 실수한 점은 M 미터의 나무를 잘랐다고 반복을 멈췄다는 것이다. 문제를 읽어보면 이때, **적어도 M미터**의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 **높이의 최댓값**을 구하는 프로그램을 작성하시오. 적어도 M미터, 높이의 최댓값에서 최적값이 따로 있을 수 있기 때문이다. 여기서 최소한 M미터를 챙겨가는 절단기의 최대 높이 K를 구한다는 최적화 문제는 '결정 문제'로 바꾸어 풀 수 있다. 이것을 파라메트릭 서치라고 한다. 자세한 내용 참고: https://sarah950716.tistory.com/16 즉 우리는 나무의 높이 배열이 주어졌을 때, 절단기의 높이가 x인 경우 잘린 나무.. 2023. 5. 4.

티스토리툴바