결국 빛나리라

https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net > 완전탐색 문제 내용 그대로 이해한 바를 코드로 옮기면 다음과 같다. 최소 수인 666부터 시작해서 1씩 더한 수를 문자화한다. 해당 문자가 문제 조건인 '666'을 포함하는 수들이면 lst안에 추가하고 lst 안에 추가된 요소의 개수가 n이면 반복문을 중단한다. * 해당 코드는 말그대로 완전 탐색으로 처음부터 끝까지 모든 수들을 문자화하고 조건문에 넣기 때문에 굉장히 시간 비효율적이다. ▶ ..

https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net > 재귀함수 반복문을 활용해 풀었던 문제인데, 이번에는 재귀 함수로 해당 문제를 다시 풀어보았다. 아래 코드처럼 코드를 작성하여 제출했더니 RecursionError가 떴다. * RecursionError: 재귀와 관련된 에러로 파이썬이 정한 최대 재귀 깊이 보다 그 깊이가 더 깊어질 때 발생하는 에러이다. 백준 채점 서버에서 최대 재귀 깊이는 1,000으로 설정되어있다. * 해당 코드에서 RecursionError가 발생한 이유: fac(5)인 경우를 생각해보자. 5*4*3*2*fac(1)까지 함수..

https://www.acmicpc.net/problem/11651 11651번: 좌표 정렬하기 2 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net > 정렬 백준의 11650번 문제와 거의 동일한 문제로 기존 풀이에서 정렬 기준 key 값만 순서를 바꿔주면 된다.

https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net > dfs 활용 백준의 단지 붙이기 문제 풀이와 거의 유사하다. 가로와 세로(행과 열)을 헷갈리는 것에 유의(인덱싱에러)하고 dfs 함수가 recursion error에 걸리지 않도록 재귀 최대 깊이를 설정하는것에 유의하면 해결할 수 있다.

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net > 플로이드 워셜 전형적인 플로이드 워셜 알고리즘 유형의 문제이다. https://westshine-data-analysis.tistory.com/45?category=843975 최단경로 알고리즘(3)/ 플로이드 워셜 알고리즘 나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 코드 출처: https://github.com/ndb796/python-fo..

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net > 스택 우선 input으로 모든 입력값들을 받은 후 입력값들이 각각 올바른 문자열인지 판단하는 vps 함수를 구현하여 해결했다. 문자열을 하나씩 입력 받기 위한 리스트로 target 변수를 선언한다. 만일 들어오려는 문자열이 '('이면 리스트에 append하고 아니라면 가장 마지막에 들어온 괄호 '('을 리스트에서 빼준다. 그런데 그 과정에서 다음과 같은 문자열은 ..

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net > 이분탐색 M의 최댓값이 20억이므로 이분탐색을 통해 시간복잡도를 줄여야한다. 문제는 전형적인 이분탐색 문제로 다음과 같은 아이디어로 해결할 수 있다. 위의 아이디어를 코드로 구현하면 다음과 같다. 얻을 수 있는 나무길이 합이 target보다 크냐 작냐에 따라 탐색하는 범위를 달리하여 문제를 해결한다,

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net > 다이나믹 프로그래밍 아래 그림과 같은 규칙을 생각하면 풀 수 있었던 문제이다. 규칙을 코드로 작성하면 다음과 같다. + 계단의 개수가 하나인 경우에 if절을 넣어주지 않으면 dp[2]를 구하는 과정에서 인덱스 에러가 나기 때문에 if문을 통해 하나인 경우를 고려해주어야 한다.

https://www.acmicpc.net/problem/11650 11650번: 좌표 정렬하기 첫째 줄에 점의 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 i번점의 위치 xi와 yi가 주어진다. (-100,000 ≤ xi, yi ≤ 100,000) 좌표는 항상 정수이고, 위치가 같은 두 점은 없다. www.acmicpc.net > 정렬 sort 메소드를 사용하고 파라미터인 key를 이용해 첫번째 정렬기준을 튜플에서 0번째 요소로, 두번째 정렬기준을 1번째 요소로 잡아주면 풀 수 있다. 또한 입력값을 받을 때 sys.stdin.readline을 사용해야 시간초과가 나오지 않는다.

https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net > 그리디 알고리즘 각 사람이 기다리는 시간을 더할 때 작은 값부터 더하면 최종 합은 최솟값이 되므로 입력받은 시간 리스트를 정렬한 후 반복문을 사용해 합을 구하면 된다. time은 사람들이 각각 기다리는 시간이고 이를 최종 합인 result에 더해준다.