www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 이런 유형의 문제를 처음 보면 '이게 왜 BFS문제지?' 라는 의문이 든다. S층에서 G층으로 가는데 U칸 위로가거나 D칸 아래로 가야하므로 1. 처음에 visited[S]를 방문 처리를 해주고 q에 S를 넣는다. 2. q에서 pop한 뒤 x + U에 해당하는 칸에 방문한 적 있는지 확인하고 없으면 버튼을 누른 횟수를 1 증가시킨다. 3. 2번과 마찬가지로 x - D에 해당하는 칸에 방문한 적 있는지 확인하고 없으면 버튼을..
www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 이제는 무난한(?) BFS문제이다. 단지 3차원배열을 사용해 조금 귀찮을 뿐이다. 1. Test Case마다 m(빌딩상태), time(이동시간), visited(방문여부) 배열을 초기화해주고 m을 입력받는다. 2. m을 전체돌면서 'S'가 있는 칸의 좌표를 sz, sx, sy에 저장하고, 'E'가 있는 칸의 좌표를 ez, ex, ey에 저장한다. 3. bfs를 돌리면서 다음 칸으로 갈때마다 시간을 1씩 더해주고 큐에..
www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 이번엔 DFS로 푼 문제이다. dfs함수: m[x][y] = 0을 해줌으로써 방문했다는 표시를 해준다. 전에 올린 문제와 비슷하게 nx, ny에 x + dx[i], y + dy[i]를 넣고 탐색한다. BFS는 nx, ny를 방문하지 않았을 경우, (nx,ny)를 deque에 넣고 방문처리를 해줬는데 DFS는 재귀방식으로 dfs함수를 또 호출한다. 매개변수로 cnt+1을 넘겨줌으로써 현재 단지에 속하는 집의 수를 ..
www.acmicpc.net/problem/1260 기초적인 그래프 탐색 문제이다. (그 동안 배우지 않고 어려워보여서 손을 안대고 있었는데, 막상 강의를 듣고 스터디도 하면서 문제를 많이 풀어보니 할 만한 것 같다.) 그래프 탐색방법에는 크게 2가지가 있다. 바로 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)이다. DFS(Depth First Search) - 깊이 우선 탐색이란, 쉽게 말해 한 정점을 정해 끝까지 파고들어가는 방법이다. - 모든 노드를 방문하고자 할 때 이 방법을 쓴다. - 자기 자신을 호출하는 재귀방식을 사용한다. - 시간 복잡도 = O(V + E) (V: 정점의 수, E: 간선의 수) 단점 - BFS에 비해 조금 느리다. - DFS는 해를 구하면 탐색이 종료되므로, 구한 해가..
https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,00 www.acmicpc.net 주어진 배열에 대해 입력받은 숫자의 갯수를 세야 하는 문제이다. 단순한 이분 탐색으로는 그 숫자의 위치는 찾을 수 있을지 몰라도..
https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다. www.acmicpc.net 이분 탐색문제이다(함정이 있는) import sys input = sys.stdin.readline N,M = map(int,input().split()) L = [] for _ in range(N): L.append(int(inp..
https://www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를,둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net * 유클리드 호제법이란? - 즉, a,b의 최대공약수는 b,r의 최대공약수와 같다는 것이다. n,m = map(int,input().split()) def Eucliden(a, b): while(b != 0): r = a % b a = b b = r return a print(Eucliden(n,m)) print(n*m // (Eucliden(n,m))) - 따라서 b가 0이 아닌 동안 b를 a에 넣고 a를 b로 나눈 나머지를 b에 넣는 과정을 반복했다. - 9번째..
https://www.acmicpc.net/problem/5430 5430번: AC 문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다. www.acmicpc.net import sys,collections input = sys.stdin.readline t = int(input()) for _ in ra..
모르는 사이에 조금씩 조금씩..
