백준 1948 - 임계경로 시간 제한 2초, 메모리 제한 512MB # 조건 월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다. 어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라. 출발 도시는..

백준 20183 - 골목 대장 호석 - 효율성2 시간 제한 5초, 메모리 제한 512MB # 조건 소싯적 호석이는 골목 대장의 삶을 살았다. 호석이가 살던 마을은 N 개의 교차로와 M 개의 골목이 있었다. 교차로의 번호는 1번부터 N 번까지로 표현한다. 골목은 서로 다른 두 교차로를 양방향으로 이어주며 임의의 두 교차로를 잇는 골목은 최대 한 개만 존재한다. 분신술을 쓰는 호석이는 모든 골목에 자신의 분신을 두었고, 골목마다 통과하는 사람에게 수금할 것이다. 수금하는 요금은 골목마다 다를 수 있다. 당신은 A 번 교차로에서 B 번 교차로까지 C 원을 가지고 가려고 한다. 호석이의 횡포를 보며 짜증은 나지만, 분신술을 이겨낼 방법이 없어서 돈을 내고 가려고 한다. 하지만 이왕 지나갈 거면, 최소한의 수치심..

지난 주에 너무 못풀어서 낮은 점수를 받게 되어 이번 주.. 알고리즘 감각을 조금 끌어올렸습니다!! 시즌 최고 점수를 받으면서 뿌듯한 일주일을 시작할 수 있을거 같아요 :) 이번에는 +1 -1과 같은 고난이도의 알고리즘 문제에서 틀렸습니다를 받았지만.. 문제를 꼼꼼히 안 읽어서 출력 요구 사항을 틀리고 있었다는 사실을 종료 5분전에 알게 되었습니다.. 더 높은 점수를 받을 수 있었지만 다음 부터는 같은 실수를 하지 말자는 교훈으로 이번 주 테스트는 종료!! 삼성전자 발표가 얼마 안남은거 같아 코딩테스트 대비 구현 문제를 풀었습니다. https://www.codetree.ai/cote/13/problems/max-area-of-positive-rectangle/description 코드트리 | 코딩테스트 ..

백준 1445 - 일요일 아침의 데이트 시간 제한 2초, 메모리 제한 128MB # 조건 일요일 아침에 형택이는 Maroon5의 Sunday Morning이란 노래를 들으면서 여자친구와의 로맨틱한 여행을 떠나기로 했다. 형택이는 이것저것 환상에 빠져있다가, 계획을 세우는데 실패했다. 따라서, 주위에 있는 숲을 같이 탐험하기로 했다. 깊은 숲속에는 정말 아름다운 꽃이 하나있다. 형택이는 여자친구의 마음을 감동시키기 위해서, 꽃을 보여주면서 자신의 마음을 전해주려고 급하게 계획했다. 불행하게도, 사람들이 숲에다 쓰레기를 버려서 형택이의 계획은 정말 망가지기 직전이다. 형택이는 그동안 여자친구와 사귀면서 2가지 깨달은 것이 있는데, 한 가지는 쓰레기를 통과해서 지나가는 것을 정말 싫어하는 것이고, 쓰레기를 따..

백준 22857 - 가장 긴 짝수 연속한 부분 수열(small) 시간 제한 1초, 메모리 제한 1024MB # 조건 길이가 $N$인 수열 $S$가 있다. 수열 $S$는 1 이상인 정수로 이루어져 있다. 수열 $S$에서 원하는 위치에 있는 수를 골라 최대 $K$번 삭제를 할 수 있다. 예를 들어, 수열 $S$가 다음과 같이 구성되어 있다고 가정하자. 수열 S : 1 2 3 4 5 6 7 8 수열 $S$에서 4번째에 있는 4를 지운다고 하면 아래와 같다. 수열 S : 1 2 3 5 6 7 8 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자. 입력 수열 S의 길이 N와 삭제할 수 있는 최대 횟수인 K가 공백으로 구분되어 주어진다. 두 번..

지난 주.. 서류가 너무 많이 떠서 알고리즘은 물론 블로그 챌린지 작성도 까먹었습니다 ㅠ 2주동안 알고리즘에 조금 소홀한 결과 지난 테스트보다 낮은 점수를 받게 되었어요 역시.. 하루 2문제씩 꾸준히 하는게 중요한 것 같아요 이번엔 dp 문제를 다익스트라로 구현하다가 틀렸습니다를 받고 실패..! 그래서 코드트리에 있는 dp문제를 풀면서 실력을 가다듬었습니다 https://www.codetree.ai/training-field/search/problems/a-sequence-by-adding-the-previous-two-numbers-2/submissions?page=1&pageSize=20&tags=DP 코드트리 | 코딩테스트 준비를 위한 알고리즘 정석 국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보..

백준 1240 - 노드사이의 거리 시간 제한 2초, 메모리 제한 128MB # 조건 N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. 입력 첫째 줄에 노드의 개수 N과 거리를 알고 싶은 노드 쌍의 개수 M이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 $M$개의 노드 쌍이 한 줄에 한 쌍씩 입력된다. 출력 M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다. 제한 $2≤N≤1,000$ $1≤M≤1,000$ 트리 상에 연결된 두 점과 거리는 $10,000$ 이하인 자연수이다. 트리 노드의 번호는 $1$부터 $N$까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다. #..

백준 2553 - 마지막 팩토리얼 수 시간 제한 0.3초(추가 시간 없음), 메모리 제한 128MB # 조건 N!의 값을 계산한 후에, 0이 아닌 가장 낮은 자리 수를 구하시오. 예를 들어, 4! = 24이기 때문에, 0이 아닌 가장 낮은 자리 수는 4이다. 또, 5!은 120이기 때문에, 0이 아닌 가장 낮은 자리 수는 2이다. 입력 첫째 줄에 N이 주어진다. N은 20,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 N!의 0이 아닌 마지막 자리수를 출력한다. # 접근 방법 N!을 math.factorial 또는 반복문을 통하여 구해준다. 이후 문자열로 변경하여 뒤에서부터 탐색하며 0이 아닌 값을 출력하고 종료해준다. import sys sys.stdin = open('input.txt&#..

백준 1158_요세푸스 문제 시간 제한 2초, 메모리 제한 256MB # 조건 요세푸스 문제는 다음과 같다. 1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K(