phanre의 tistory

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 간단한 BFS 문제 시작 점의 좌표를 큐에 저장한 뒤 주변 좌표를 탐색한다. 이때 조건은 좌표가 N, M을 벗어나지 않는지 && 이동할 수 있는 칸인지 && 방문한 적 없는지 이 세가지만 확인하면 된다. 세 조건을 충족한다면 큐에 넣고 visit을 1로 변경해준다 반복이 종료된다면 N, M번째 좌표를 출력해주자 import sys from collections import deque input = sys.stdin.readlin..

https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 우선순위 큐를 이용하는 그리디 문제. 주유소를 가까운 거리가 앞으로 가도록 소팅한다. 이후 현재 위치에서 남아있는 연료를 더해 최대한 갈 수 있는 지점을 설정한다. 최대한 갈 수 있는 지점까지 맥스 힙에 heappush하고 heappop을 이용하여 가능한 주유소 중 가장 연료가 많은 주유소에 들른다. 들른 주유소까지의 거리만큼 연료를 빼고 주유소에 저장된 연료..

1. 셀레니움 설치 우선 pip 명령어 혹은 conda 명령어를 이용해 셀레니움을 설치한다. pip install selenium conda install selenium 혹은 Pycharm을 이용한다면 Preference - Project - Python Interpreter 에서 + 아이콘을 눌러 selenium을 추가해준다. 2. 크롬 버전에 맞는 크롬드라이버 설치 크롬 버전 확인 방법 점 세개 클릭 - 도움말 - Chrom 정보 크롬 버전 확인 완료 이제 크롬드라이버 다운 사이트에 들어가서 크롬 버전에 맞는 크롬드라이버 버전을 다운하면 된다. https://chromedriver.chromium.org/downloads ChromeDriver - WebDriver for Chrome - Downl..

https://www.acmicpc.net/problem/3109 3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 남의 가스를 훔친다는 비양심적인 그리디 문제 DFS로 우선 탐색할 지점만 잘 생각한다면 쉬운 문제이다. 맨 위에서 시작할 경우 건물을 피해 위쪽을 먼저 탐색하고 반대의 경우에는 아래쪽을 먼저 탐색하면 된다. 처음에는 가스관에 도달하면 경로를 저장했는데 그렇게 하니 시간초과가 됐다. 어떻게 시간을 줄일까 생각해보니 어차피 어떠한 지점에 간 후 가스관에 도달하지 못하면 그 경로는 안가도 되니 이동할 때마다 경로를 저..

https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 간단한 두 포인터 문제이다. 첫 포인터 위치를 0번째, 1번째 인덱스로 잡은 후 var 변수를 이용하여 알파벳 종류 수를 센다. 이후 check 배열에 각각 인덱스마다 알파벳이 나올 때 마다 값을 증가시켜 갯수를 세며 temp를 증가시킨다. 우측 포인터를 증가시키다가 알파벳 종류가 n을 넘어가는 경우 우측 포인터를 멈추고 좌측 포인터가 가리키는 인덱스의 check 값이 0이 될 때 까지 좌측 포인터를 증가..

https://www.acmicpc.net/problem/23254 23254번: 나는 기말고사형 인간이야 192시간 동안 1번 과목을 35시간, 2번 과목을 43시간, 3번 과목을 30시간, 4번 과목을 17시간, 5번 과목을 37시간, 6번 과목을 30시간동안 공부하면 1, 2, 3, 4, 6번 과목은 100점, 5번 과목은 77점, 7번 과목은 www.acmicpc.net 우선순위 큐 이용하는 그리디 문제. 1시간 공부하면 점수가 x점 늘어나는 것을 인덱스별로 저장하기 위해 plus 배열을 생성한다. 높은 효율의 문제에 공부를 무한정으로 해도 100점을 초과 할 수 없으므로 100에서 현재 점수를 뺀 점수가 오르는 수치보다 작다면 plus배열의 자신의 값을 100 - 현재점수로 변경한다. 이후 오르..

https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 단순 브루트포스 문제. 1번 원소를 더한 후 2~n번 원소를 더하는 함수를 호출하고 그 함수에서는 3~n번 원소를 더하는 함수를 호출한다. 이 과정을 1~n번 원소 모두 실행하면 답이 나온다 누적 합을 이용하여 중간에 프루닝 하는 방법을 이용하려 했으나 n이 충분히 작아 시간초과가 나지 않을 것 같아 모든 원소를 탐색하였다. def Back(sum, index)..

https://www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 태그는 위상 정렬으로 되어있지만 위상정렬을 사용할 필요 없는 문제. 처음에 등수 받을때 자신 밑에 몇명이 있는지 deg 배열에 저장한 후 상대적 순위가 바뀌었을 때 등수가 높은 사람은 deg 감소, 낮은 사람은 deg 증가시켜 deg 배열에 중복되는 숫자가 있는 경우 IMPOSSIBLE 출력. 변동된 상대적인 순위를 모두 입력받으므로 순위를 알수 없는 경우는 신경쓰지 않아도 된다. impo..