728x90 Programming Language Training90 Baekjoon Training #2178 #2178 미로 탐색 #deque class를 collections module에서 import from collections import deque N, M = map(int, input().split()) maze = [list(map(int, input())) for _ in range(N)] def bfs(maze, start): queue = deque([start]) #행의 개수 (세로 길이) n = len(maze) #열의 개수 (가로 길이) m = len(maze[0]) #전체 좌표의 distances값을 -1 default값으로 설정 distances = [[-1 for _ in range(m)] for _ in range(n)] distances[start[0]][start[1]] = .. 2023. 1. 10. Baekjoon Training #2563 #2563 n = int(input()) #색종이 수 입력 num_list = [[0] * 100 for _ in range(100)] #0으로 채워진 100 by 100 2차원 배열 생성 for _ in range(n): #색종이 수 만큼 반복 x,y=map(int,input().split()) #색종이의 좌하단 점 입력 #색종이의 좌하단 점으로부터 우상단으로 10 by 10 색종이가 걸치는 좌표의 값을 1로 설정 for i in range(10): for j in range(10): num_list[x+i][y+j] = 1 ans = 0 #결과 값을 0으로 세팅 #열을 기준으로 값이 1인 좌표들을 counting하여 그 수만큼 ans에 더해줌 for a in num_list: ans+=a.count(.. 2023. 1. 7. Baekjoon Training #2738 #2738 백준 문제 풀이에 감이 떨어진것 같아서 간단한 문제로 몸풀기를 하고 문제를 하나더 풀어보고자한다. a, b = map(int, input().split()) list1=[] list2=[] for i in range (a): x=list(map(int, input().split())) list1.append(x) for i in range (a): y=list(map(int, input().split())) list2.append(y) for row in range (a): for col in range (b): print(list1[row][col]+list2[row][col], end=' ') print() 브론즈5 난이도의 간단한 문제라서 가벼운 마음으로 풀려고 했는데 2차원 배열을 자주.. 2023. 1. 5. Baekjoon Training #1912 #1912 n=int(input()) num = list(map(int,input().split())) sum_list=[num[0]] for i in range(len(num) - 1): sum_list.append(max(sum_list[i] + num[i + 1], num[i + 1])) print(max(sum_list)) 처음에는 list에 n개의 숫자들을 담아두고 1개의 합을 새로운 list에 넣고 연속된 2개의 합을 새로운 list에 넣는 과정을 갯수를 증가시키며 반복하여 연속된 n개의 합까지 전부 새로운 list에 넣어서 그중 max값을 찾아서 결과를 찾으려고 했다. 그러나 코드의 효율성이 너무 안좋을 것으로 예상이 가서 새로운 방식을 고민해보았다. 그렇게 고안한 것이 모든 값을 전부 리스.. 2022. 12. 27. Baekjoon Training #1931 #1931 N = int(input()) time_list = [] for i in range(N): start, end = map(int, input().split()) time_list.append([start, end]) time_list.sort(key=lambda a: a[0]) # 시작 시간을 기준으로 오름차순 정렬 time_list.sort(key=lambda a: a[1]) # 끝나는 시간을 기준으로 다시 오름차순 정렬 fin_time = 0 # 회의의 마지막 시간 count = 0 # 회의의 수 for i, j in time_list: if i >= fin_time: # 시작시간이 회의의 마지막 시간보다 크거나 같을경우 count += 1 # counting 진행 fin_time = j .. 2022. 12. 26. Quick sort Quick sort algorithm 퀵정렬은 pivot을 설정하고 설정한 pivot을 기준으로 작은 요소들은 모두 pivot의 왼쪽으로 옮겨지고 pivot보다 큰 요소들은 모두 pivot의 오른쪽으로 옮긴다. pivot을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하고 분할된 부분 리스트에 대하여 recursion을 이용하여 정렬을 반복한다. 이때 quick sort는 unstable sorting process이다. 나누어진 리스트에서도 다시 pivot을 정하고 pivot을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다. 이때도 merge sort와 같이 divide and conquer 과정을 통해 진행이 됨을 알 수 있다. 추가적으로 pivot을 설정하는 다양한 방법이 있는데 pivot.. 2022. 12. 23. Merge sort Merge sort Divide and Conquer식 설계전략을 이용하고 추가적으로 통합하는 Combine과정을 거쳐셔 Merge sort를 진행한다. 이러한 방식을 하향식(top-down) 접근법이라고 한다. Source code 전체 code를 보기전에 psuedo code를 살펴보면 mergesort는 merge함수를 이용하였음을 알 수 있다. 전체 코드 mergesort.cpp #include "ArrayVector.h" #include #include #include #include //난수생성을 위한 library #include //string으로 형변환을 위한 library #include //실행시간 측정을 위한 library using namespace std; //divide and.. 2022. 12. 22. 난수 생성 algorithm Psuedo Random 우선 컴퓨터가 난수를 생성하기 어렵다는 것을 알아야한다. 컴퓨터는 사람과 달리 무의식적인 선택, 또는 우연에 의한 선택을 할 수 없기에 기본적으로 정해진 입력에 따라 정해진 값을 낼 수 밖에 없기 때문이다. 이를 결정적 유한 오토마타(Deterministic Finite Automata)라고 한다. 이는 컴퓨터가 하나의 입력에 대해 무조건 하나의 전이만 가능하기 때문이다. 따라서 컴퓨터는 특정한 방법으로 계산하거나 계속해서 변하는 값을 초기값으로 잡고 계산과정을 거쳐서 사람이 보기에 난수처럼 보이도록 하는 의사 난수(psuedo random)을 이용한다. 흔히 난수표를 만들어두고 그를 이용하여 의사 난수를 생성한다. 그러나 난수표가 정해진 순간 같은 수로 다시 돌아온다는 것이 확.. 2022. 11. 17. C++ 난수 생성 rand함수 #include #include #include int main() { srand(time(NULL)); for (int i = 0; i < 5; i++) { printf("Random Num : %d \n", rand() % 100); } return 0; } rand함수를 이용한 위 코드를 보면 srand, time, rand와 같은 함수들을 볼 수 있다. 우선 위의 코드는 실제 난수를 생성하는 코드가 아니라 난수처럼 보이도록 하는 의사 난수(pseudo random number)를 생성하는 코드이다. srand 함수로 무작위로 정해지는 첫 숫자인 seed를 설정할 수 있다. 위 코드의 경우 time(NULL)을 통해 프로그램을 실행했던 시간 초를 시드값으로 지정햇다. 그리고 rand().. 2022. 11. 17. 이전 1 ··· 3 4 5 6 7 8 9 10 다음 728x90
