https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 처음에 접근할 때는 666 왼쪽 오른쪽에 순차적으로 숫자를 넣으면 되지 않을까 라는 생각을 했는데, 생각보다 로직이 좀 까다로웠다. 666 -> 1666 -> 2666 이지만, 5666 -> 6661 -> 6662 순이고, 6669 -> 7666 으로 가야하기때문에,,, 물론 문제 조건에 범위가 10000까지라고 적혀있어서 한 번의 경우만 체크해도 괜찮았지만, 자릿수가 계속 커질 수록 따로 빼서..

https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 스택을 이용한 괄호문제. 스택의 종류가 하나라서 개수만 확인하면 돼서 꽤 쉽다. ( 일 경우, 스택에 추가하고, )의 경우에 스택에서 pop하는 형식으로 짜고, 0개일때 pop하는경우랑, 마지막 문자까지 읽었는데 스택에 남아있는 경우에는 NO를, 마지막까지 읽었고 스택이 0인 경우엔 YES를 출력한다. 해답코드 T = int(input()) for _ in range..

https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 $-1$ 출력한다. www.acmicpc.net x1, y1,.r1이 나오면 원이라고 생각하자. 두 원의 거리에 따른 원의 관계를 코드로 구현하는 문제였다. 틀린 코드 import math T = int(input()) for _ in range(T): x1, y1, r1, x2, y2, r2 = map(int, input().split()) # dist1 = 두 점의 직선 거리 (두 원의 중심간 거리) dist1 = math.sqrt((x1-x2)**2 + (y1-y2)**2) # dist2 ..

https://www.acmicpc.net/problem/19637 19637번: IF문 좀 대신 써줘 첫 번째 줄에는 칭호의 개수 N (1 ≤ N ≤ 105)과 칭호를 출력해야 하는 캐릭터들의 개수 M (1 ≤ M ≤ 105)이 빈칸을 사이에 두고 주어진다. (1 ≤ N, M ≤ 105) 두 번째 줄부터 N개의 줄에 각 칭 www.acmicpc.net 이진 탐색 문제다. 주어지는 N과 M이 둘 다 10^5 까지의 범위기 때문에, if문으로 전부 비교하게 되면 10^10으로 1초의 시간제한을 벗어나게 된다. 처음에 문제에 접근할 때는, 이진탐색으로 칭호를 기준으로 이진탐색하면서 ~칭호 이하의 개수만큼 ~칭호를 출력, 그 초과, 다음 이하의 개수만큼 ~칭호를 출력 하려고 생각했는데, 거꾸로 생각하면 더 편..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 숫자를 세기만 하면 되는 문제인 줄 알았는데, 숫자의 범위가 꽤나 크고, 입력의 개수도 꽤 많았다. 잘한점: 1. 연산량이 많을 것 같아서 해시맵인 dict자료구조를 이용할 생각을 했음. 문제를 못 푼 요인: 1. 처음에는 count연산을 했는데, count를 하면 한 번 count할 때마다 O(N)의 시간 복잡도로 돌기 때문에, N 번 센다면 O(N^2)의 시..

DP? DP는 우리나라말로 동적계획법이라 하며, 한번에 풀기 어려운 문제를 잘게 쪼개서 (divide) 하나하나 풀어나가며 전체 문제를 푸는 (conquer) 방식이다. 우리가 일반적으로 엥? 재귀랑 다른게 뭔데! 라고 한다면 DP는 결과를 기록해서 똑같은 계산을 하지 않음으로 시간을 아낀다는 것이다. 피보나치 수열 피보나치 수열은 다음 값이 이번 값과 이전 값의 합으로 표현되는 수열이다. 식으로 나타내면 F( n) = F(n-1) + F(n-2) 로 표현할 수 있는데, F(5)를 계산하기 위한 과정을 보면, F(5)를 계산하기 위해서 F(3)은 두번 계산되고 F(2)는 3번이 계산되는 것을 볼 수 있다. 5라는 숫자가 작아서 몇 번 안 되는것 처럼 보이겠지만, 시간복잡도는 O(2^n)의 시간 복잡도를 ..

플로이드? 다익스트라 알고리즘이 한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘이라면, 플로이드는 어떤 정점에서 다른 정점까지의 최단거리를 모두 구하는 알고리즘이다. 코드로 보도록 하자. INF = int(1e9) n = int(input()) m = int(input()) graph = [[INF] * (n+1) for i in range(n+1)] # 자기 자신으로 가는 노드는 거리가 0 이라고 가정 for i in range(1,n+1): graph[i][i] = 0 # 그래프 입력받기 for _ in range(m): a, b, c = map(int, input().split()) if c < graph[a][b]: graph[a][b] = c # 거리의 최솟값 구하기 for k in ra..

다익스트라? 엄청난 분이시다... 다익스트라 알고리즘을 개발해서 최단경로 문제도 연구하시고 세마포어도 이 분께서 처음 연구하셨다고..! 그럼 간단하게 다익스트라 알고리즘에 대해서 알아보자. 다음과 같은 그래프가 있다고 하면, s에서 다른 노드로 가는 최단거리를 구하려면 1. 바로 갈 수 있는 노드는 그 거리를 저장하고, ( t = 10, y = 5 ) 직접 이어지지 않았다면 거리를 무한으로 저장한다. 2. 갈 수 있는 가장 가까운 노드(y)에서 다른 노드까지 직접 가는 거리를 더해서 만약 작다면 갱신해준다.(t = 10 -> 8 ) 3. 또 s에서 (다른 노드를 거치든 안 거치든) 가장 가까운 노드 (z = 7 , t = 8이므로 z )에서 다른 노드간 거리를 합해서 최단 거리를 갱신한다 4. 반복해서 ..

파라메트릭 서치 기법 이진탐색을 이용해 최적화 문제를 풀 수 있다. 어떤 조건에서 가장 최적의 해를 구할 수 있을 지를 이진탐색을 통해서 해결하는 방식을 파라메트릭 서치 기법이라고 한다. 어떤 조건을 가지고 계속 왼쪽 오른쪽 값을 조절하면서 조건에 가장 최적화 된 답을 찾는 것이다. 끝나는 조건이나 왼쪽오른쪽 값을 바꾸는 조건을 문제에서 잘 확인해서 적용해야해서, 이 조건을 유의해서 풀어야 한다. 백준 2512 예산 https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 w..