코드트리 - 핀볼게임 풀이시간 25분 # 접근 방법 dx, dy 테크닉이 중요한 문제이다. 1번과 2번 벽을 만났을 때 어떻게 진행시키는지가 중요하다. di, dj = [1, 0, -1, 0], [0, 1, 0, -1]로 설정해주며 1번을 만난 경우와 2번을 만난 경우를 각각 회전하는 딕셔너리를 만들어준다. first = {0:3, 1:2, 2:1, 3:0} second = {0:1, 1:0, 2:3, 3:2} 0행에서 진행, 0번째 열 기준 진행, N-1번째 행 기준 진행, N-1번째 열 기준 진행을 해주면 된다. 주의할 점은, 들어가는 시간과 나오는 시간을 포함해주어야 한다는 것과 시작 위치마다 핀볼의 시작 진행 방향이 다르다는 것이다. 들어갈 때부터 카운트를 해주고 이동하는 것을 편하게 하기 위하여..

백준 4358 - 생태학 시간 제한 1초, 메모리 제한 256MB # 조건 생태학에서 나무의 분포도를 측정하는 것은 중요하다. 그러므로 당신은 미국 전역의 나무들이 주어졌을 떄, 각 종이 전체에서 몇 %를 차지하는지 구하는 프로그램을 만들어야 한다. 입력 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어진다. 출력 주어진 각 종의 이름을 사전순으로 출력하고, 그 종이 차지하는 비율을 백분율로 소수점 4째자리까지 반올림해 함께 출력한다. # 접근 방법 문제 자체는 쉬운 난이도였다. 입력받는 나무들을 dicttionary에 이름마다 +=1 을 해주고,..

코드트리 - 최적의 십자 모양 폭발 # 접근 방법 완전 탐색을 활용한 시뮬레이션 문제이다. 0, 0부터 N-1, N-1까지 모든 폭탄을 터트린 후, 조건에 맞는지 검사해주면 된다. 항상 느끼는 것이지만, 모든 문제를 풀 때 각 기능을 함수로 나누는 것이 디버깅에도 유리하고 코드를 읽을 때도 잘 읽히는 것 같다. bomb함수 폭탄을 터트리며 터진 곳을 저장해주었다. 시작 위치는 height에 우선적 저장을 해주었는데, 1칸만 터지는 경우 세로로만 복사해주면 되기 때문이다. 시간을 가장 많이 소비한 곳은 폭탄을 터트린 후 격자에 중력을 작용시키는 부분이었다. gravity 함수 가로로 터지는 부분은 최대 1칸이므로 터진 곳을 저장 세로로 터지는 곳은 저장 후 정렬을 통하여 가장 위의 칸과 가장 아래 칸을 변..

코드트리 - 최단 Run Length 인코딩 # 접근 방법 문자열을 비손실 압축 방식으로, 오른쪽으로 shift를 통하여 최소 길이로 만드는 문제이다. 평소에 많이 접해보지 않은 문제이지만 아이디어를 떠올리는 것이 어렵지 않았다. 오른쪽 shift를 통해서 현재보다 짧은 길이로 만들기 위해서는, 가장 먼저 나온 문자열과 가장 마지막에 나온 문자열이 같아야 된다. 우선, 주어진 문자열을 순회하며 비손실 압축을 해준다. 이후 길이가 2인 경우 => 모든 문자열이 1개로 이루어진 경우는 바로 2를 출력해준다. 그렇지 않다면, 뒤에서 2번째 문자와 가장 첫 문자를 비교해준 후, 같다면 개수를 합쳐준다. import sys input = sys.stdin.readline words = input().strip()..

백준 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가 공백으로 구분되어 주어진다. 두 번..