www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net N * M칸의 map을 입력받고 BFS를 돌려준다. 1. (0,0)부터 시작하므로 q에 (0,0)을 넣고 BFS 시작 2. i가 0부터 3까지 돌면서 nx = x + dx[i], ny = y + dy[i]를 통해 현재 좌표의 상하좌우를 모두 '넓게' 탐색한다. 3. 만약 (nx,ny)를 방문한적이 없고 map[nx][ny]가 1이면 q에 넣고 dist[nx][ny]에 dist[x][y] + 1을 저장하고 (nx,ny)에 방문했다는 표시를 한다..
www.acmicpc.net/problem/1260 기초적인 그래프 탐색 문제이다. (그 동안 배우지 않고 어려워보여서 손을 안대고 있었는데, 막상 강의를 듣고 스터디도 하면서 문제를 많이 풀어보니 할 만한 것 같다.) 그래프 탐색방법에는 크게 2가지가 있다. 바로 DFS(깊이 우선 탐색)와 BFS(너비 우선 탐색)이다. DFS(Depth First Search) - 깊이 우선 탐색이란, 쉽게 말해 한 정점을 정해 끝까지 파고들어가는 방법이다. - 모든 노드를 방문하고자 할 때 이 방법을 쓴다. - 자기 자신을 호출하는 재귀방식을 사용한다. - 시간 복잡도 = O(V + E) (V: 정점의 수, E: 간선의 수) 단점 - BFS에 비해 조금 느리다. - DFS는 해를 구하면 탐색이 종료되므로, 구한 해가..
https://www.acmicpc.net/problem/2630 2630번: 색종이 만들기 첫째 줄에는 전체 종이의 한 변의 길이 N이 주어져 있다. N은 2, 4, 8, 16, 32, 64, 128 중 하나이다. 색종이의 각 가로줄의 정사각형칸들의 색이 윗줄부터 차례로 둘째 줄부터 마지막 줄까지 주어진다. 하얀색으로 칠해진 칸은 0, 파란색으로 칠해진 칸은 1로 주어지며, 각 숫자 사이에는 빈칸이 하나씩 있다. www.acmicpc.net * 분할 정복이란? - 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 분할 정복에도 여러가지 종류가 있지만, 이 문제는 쿼드트리(quad-tree)를 통해 풀어 보았다. (https://www.acmicpc.net/problem/1992 ..
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/2108 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 어렵진 않지만 소문제 4개로 나누어져 있고 정리할게 많아서 정리해본다. import sys, collections input = sys.stdin.readline numList = [] T = int(input()) for _ in range(T): n = int(input()) numList.append(n) numList.sort() print(round(sum(numList)/T)) print(numList[int(T/2)])..
https://www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입력으로 받아 그룹 단어의 개수를 출력하는 프로그램을 작성하시오. www.acmicpc.net 딱히 어려운 문제는 아니지만, 잡기술(?)하나를 설명하기 위해 정리를 해본다. import sys input = sys.stdin.readline n = int(input()) cnt = 0 def..
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번째..
모르는 사이에 조금씩 조금씩..
