쥬코딩

예제 4-1. 상하좌우 내풀이 n = int(input()) x = 1 y = 1 move = list(map(str, input().split())) i = 0 for i in range(len(move)): if move[i] == 'R' and y 1: y-=1 elif move[i] == 'D' and x 1: x-=1 print("{} {}".format(x, y)) 답안예시 # N을 입력받기 n = int(input()) x,y = 1,1 plans = input().split() # L,R,U,D에 따른 이동 방향 dx = [0,0,-1,1] dy = [-1..

알고리즘 2023. 2. 23. 11:29

실전문제 1. 큰 수의 법칙 내 풀이 n, m, k = map(int, input().split()) data = list(map(int, input().split())) data.sort() first = data[n-1]; second = data[n-2]; result = 0; while m>0: for i in range (k): result += first m-=1 result += second m-=1 print(result) 모범답안 문제 푸는 아이디어 : 반복되는 수열 반복되는 수열의 길이 = k + 1 수열이 반복되는 횟수 = m / (k + 1) -> m 이 나누어 떨어지지 않는 경우도 고려해야한다. m이 나누어 떨어지지 않는 경우에는 m을 k+1로 나눈 나머지만큼 가장 큰 수가 추가로..

알고리즘 2023. 2. 21. 13:25

이 문제는 dfs방식을 이용해서 풀었다. #define _CRT_SECURE_NO_WARNINGS #include char graph[25][25]; int house[625] = { 0, }; int sorted[625]; int dfs(int i, int j, int n, int cnt) { //한번 집이 있는 것(1)을 확인했다면 0으로 바꾸어주기 graph[i][j] = 0; //하나의 단지에 있는 집의 개수 세기 house[cnt]++; //좌우 위아래로 집이 있으면 같은 단지이기 때문에 재귀로 dfs호출 if (i - 1 >= 0 && graph[i - 1][j] == '1') dfs(i - 1, j, n, cnt); if (i + 1 < n && graph[i + 1][j] == '1') d..

알고리즘 2022. 7. 2. 12:55

해쉬테이블은 저장할 key 값은 달라도 hash function을 수행한 결과값은 동일할 수 있다. 이를 충돌(collision)이라고 부른다. 충돌을 해결하기 위한 방법에는 체인을 이용하거나 오픈 어드레싱 등을 이용할 수 있다. double hashing은 선형 프로빙의 문제를 부분적으로는 해결해준다. 아래의 글에서 선형프로빙의 단점(문제점)을 확인할 수 있다. 2021.12.21 - [알고리즘] - [알고리즘] 해쉬 테이블(hash table) - 선형 프로빙(linear probing) 더블 해슁은 두개의 hash function을 사용하는 것이다. 하나는 처음에 key를 저장할 index를 찾기 위한 것이고, 나머지 하나는 충돌 발생 시 저장할 index를 찾기 위한 것이다. 충돌 발생 시 저장할..

알고리즘 2022. 6. 24. 13:13

해쉬테이블은 저장할 key 값은 달라도 hash function을 수행한 결과값은 동일할 수 있다. 이를 충돌(collision)이라고 부른다. 충돌을 해결하기 위한 방법에는 체인을 이용하거나 오픈 어드레싱 등을 이용할 수 있다. 쿼드라틱 프로빙은 선형 프로빙의 문제를 부분적으로는 해결해준다. 아래의 글에서 선형프로빙의 단점(문제점)을 확인할 수 있다. 2021.12.21 - [알고리즘] - [알고리즘] 해쉬 테이블(hash table) - 선형 프로빙(linear probing) [알고리즘] 해쉬 테이블(hash table) - 선형 프로빙(linear probing) 오늘은 오픈 어드레싱 중에서 선형 프로빙(linear probing)에 대해 알아보겠습니다. 해쉬테이블은 저장할 key 값은 달라도 h..

알고리즘 2022. 6. 24. 13:04

해쉬테이블은 저장할 key 값은 달라도 hash function을 수행한 결과값은 동일할 수 있다. 이를 충돌(collision)이라고 부른다. 충돌을 해결하기 위한 방법에는 체인을 이용하거나 오픈 어드레싱 등을 이용할 수 있다. 체인을 이용하는 방법은 충돌이 발생한 지점에 포인터로 링크드리스트와 같이 연결하는 것이다. 아래는 오버플로 체이닝의 예이다.

알고리즘 2022. 6. 16. 20:40

오늘은 넓이 우선탐색에 대해 알아보겠습니다. 넓이 우선탐색은 거리를 기준으로 하는 탐색 방법이라 할 수 있습니다. 즉, 시작점으로부터 거리가 같은 노드를 먼저 탐색하는 방법입니다. 아래 그래프를 기준으로 설명하겠습니다. 거리가 동일할 때는 작은 숫자부터 탐색한다고 가정하면 시작점이 0일때 BFS 방식을 사용하면, 0->1->4->2->3 순서로 그래프를 탐색하게 됩니다. 0과 인접한 1과 4를 먼저 탐색하게 됩니다. 0과 인접한 것은 이제 없기 때문에 1과 인접한 것 중 이전에 탐색하지 않았던 노드인 2와 3을 탐색하게 됩니다. 1과 인접한 것은 이제 없고 4와 인접한 것 중 이전에 탐색하지 않았던 노드는 없기 때문에 탐색을 종료합니다. 위의 그래프를 인접 행렬 방식으로 나타내면 다음과 같습니다. 탐색한..

알고리즘 2021. 12. 27. 17:27

오늘은 오픈 어드레싱 중에서 선형 프로빙(linear probing)에 대해 알아보겠습니다. 해쉬테이블은 저장할 key 값은 달라도 hash function을 수행한 결과값은 동일할 수 있습니다. 이를 충돌(collision)이라고 부릅니다. 충돌을 해결하기 위한 방법에는 체인을 이용하거나 오픈 어드레싱 등을 이용할 수 있습니다. 오픈 어드레싱은 충돌을 피하기 위해 key를 해쉬 테이블에 직접 저장하는 방법입니다. 오픈 어드레싱에는 선형 프로빙(linear probing), 이차식 프로빙(quadratic probing), 이중 해싱(double hashing)이 있습니다. 그 중에서 선형 프로빙(linear probing)은 hash function을 수행한 결과값은 동일할 경우 뒤로 한 칸씩 미루면서..

알고리즘 2021. 12. 21. 20:52