학교에서 배운 최대공배수 구하는 방법과유클리드 호제법 알고리즘을 사용해서 코드를 구현하는 방법은 다르다. 나처럼 유클리드 호제법이 뭔데? 라고 생각한 분들을 위해5분 안에 쉽게 이해되도록 설명해보겠다. 최소공배수를 구하는 공식에 최대공약수가 들어가므로최대공약수 먼저 알아보겠다.  ※ 유클리드 호제법 - 최대 공약수 유클리드 호제법은 두 자연수의 최대 공약수를 구하는 알고리즘이다.먼저 MOD 연산을 알고 있어야 하는데 MOD는 두 수의 나머지를 구하는 연산이다.예를 들어 파이썬에서 나머지를 구하는 연산은 % 이며, 10 % 6 = 4 가 나온다. 유클리드 호제법으로 108과 138의 최대공약수를 구해보겠다.이해하기 쉽게 그림으로 풀어봤다.  1. 큰 수를 작은 수로 MOD 연산 실행2. 전 단계에서의 작은..

https://www.acmicpc.net/problem/1934 백준 1934번 최소공배수 문제를 풀려면 먼저유클리드 호제법 최대공약수에 대해 알아야 한다. 유클리드 호제법에 대한 세세한 내용은 알고리즘 카테고리에 기록해 놨다.  문제   풀이 자연수 A와 B가 입력되었을 때 최소공배수의 공식은 "A*B / 최대공약수"이다.아래 그림은 두 번째 케이스의 gcd(6, 10)을 구하는 방법이다.  큰 수를 작은 수로 나누는 MOD 연산을 한 후,전 단계에서의 작은 수와 결과값 나머지를 다시 MOD 연산을 한다.재귀 함수로 결과값이 0이 될 때까지 반복 수행한 후,나머지가 0이 되는 순간의 작은 수가 두 수 A, B의 최대 공약수이다. 1934번 문제는 최소 공배수를 구하는 문제이다.앞서 최소 공배수의 공식..

https://www.acmicpc.net/problem/1850 프로그래밍 알고리즘으로 최대공약수를 구하는 방법이학교에서 배운 소인수 분해와 달라서 처음엔 이게 무슨 소린가 했다. 개념만 알면 MOD 연산으로 아주 쉽게 풀리는 문제였다. 유클리드 호제법 최대공약수에 대한 내용은 알고리즘 카테고리에서 자세히 다루겠다.  문제   풀이 입력 값들의 최대 공약수는 최대공약수 길이를 나타낸다.예를 들어 3과 9의 최대공약수 3은 111, 111111111의 최대공약수 111의 길이이다.  코드 import sysinput = sys.stdin.readlinea, b = map(int, input().split())def gcd(x, y): if y == 0: # y가 0이면 x가 최대공약수 ..

https://www.acmicpc.net/problem/1012 백준 1012번 유기농 배추 문제 - 너비 우선 탐색(breadth-first search)으로 풀었다.  문제   설명 문제가 길지만 간단히 말하면 섬의 개수를 구하는 문제이다.1이 상,하,좌,우로 붙어있고 0으로 둘러 싸여있으면 하나의 섬이다. 코드는 그래프를 완전 탐색해서 1이 나오면 BFS를 실행한다.BFS 내에서 섬 전체를 훑어가며 1에서 0으로 바꿔준다.너비 우선 탐색에 대해 알고 있으면 쉽게 풀리는 문제이지만혹시 이해가 안간다면 더 쉬운 백준 BFS 문제 2178번 미로 탐색을 추천한다.  [백준] 2178번 미로 탐색 / 파이썬 python 너비 우선 탐색(bfs) 구현https://www.acmicpc.net/problem..

https://www.acmicpc.net/problem/1931 그리디(greedy), 탐욕 알고리즘은 현재 가장 최선의 선택을 하는 알고리즘이다.제약 조건에 벗어나지만 않으면 되어서 "항상 최적의 해를 보장하지 않는다" 라는아주 마음에 안 드는(?) 단점이 있다. 사실 내가 그리디 알고리즘을 별로 선호하지 않는데..그래도 문제는 풀어야겠지 에효 백준 1931번 회의실 배정 문제는 그리디 알고리즘을 사용하면 된다.  문제  설명 회의를 가장 많이 진행하기 위해서는 회의의 끝나는 시간이 중요 키포인트다. 회의 시작 시간과 끝나는 시간이 같을 수 있다고 문제에 주어졌는데,예를 들어 (11, 11), (10, 11) 2개의 회의가 있다면 2개 모두 진행이 가능하지만(11, 11)이 먼저 입력되면 나중에 나온..

안녕하세요!:) 가족끼리 나트랑 여행을 다녀왔는데묵었던 숙소가 정말 좋았어서추천드리고자 포스팅 올려요. 조식이 맛있어야하고수영장이 깊고, 다양한 액티비티를즐길 수 있는 숙소를 원했는데기대에 부응하는 곳이었어요. 바로 아미아나리조트입니다! 먼저 나트랑 아미아나리조트의조식부터 소개할게요.  메뉴가 다양했고특히 반미 샌드위치가취향 저격이었어요. 수영장과 바다 뷰를 보며조식을 즐길 수 있고한국인 입맛에 맞는음식이 꽤 많았습니다. 아미아나리조트는 나트랑의조식 맛있는 숙소로 유명해요.ㅎㅎㅎㅎ  리조트 규모가 커서산책하기 좋았어요. 바다 바로 옆에 있고시크릿 비치도 보유하고 있어서스노쿨링할때 편해요.   여기가 아미아나리조트시크릿비치입니다! 스노쿨링을 하는데물고기가 생각보다 많아서구경하며 즐기기 좋아요. 아침에 미리..

https://www.acmicpc.net/problem/2178 백준 2178번 미로 탐색 간단한 너비 우선 탐색(bfs)으로 구현이 가능한 문제였다. 너비 우선 탐색(breadth-first search) 알고리즘 특징은 그래프의 완전 탐색 방법 중 하나로,가까운 노드를 먼저 방문한다. 스택, 재귀를 사용하는 깊이 우선 탐색(depth-first search)과 다르게 너비 우선 탐색은선입선출(First In First Out) 방식이므로 큐를 사용해서 구현한다.  문제    설명 출발점 (0, 0)에서 상,하,좌,우를 봤을 때, 1이 있으면 현재 내가 있는 값 + 1 을 해준다.  도착점 (N-1, M-1)에 도달했을 때 그 값을 출력해 주면 끝. 코드가 짧고 어렵지 않으므로 바로 소스를 보며 이해..

https://www.acmicpc.net/problem/1753 백준 1753번 최단경로 문제는 다익스트라 알고리즘을 사용했다. 참고로 다익스트라 알고리즘은 출발 노드에서 모든 노드 간의 최단 거리를 구하며 엣지는 양수이어야 한다. 문제  설명  다음은 1753번 문제에 대한 풀이 순서이다. 1) 최단 거리 리스트 D[N]은 1차원 리스트로 출발 노드는 0, 그 외는 모두 무한대로 초기화한다. 2) D[N]에서 현재 값이 가장 작은 노드를 골라서 연결된 다른 노드의 값을 없데이트 한다.최단 거리 업데이트는 min(현재 노드 최단 거리 값 + 가중치, 다음 노드 최단 거리 값) 으로 비교한다. 3) 방문 리스트 visited[]를 만들어서 재방문 하지 않고 모든 노드가 선택될 때까지 반복한다. 글만 보면..

http://https://www.acmicpc.net/problem/1717  백준 1717번 집합의 표현은 유니온 파인드(union find) 알고리즘을 확실히 알게 해주는 문제였다. 문제  설명 문제 1717번 예제로 유니온 파인드에 대해 설명하자면, 1)  대표 노드를 저장하는 1차원 리스트가 필요하며 처음에는 연결되어 있지 않으므로자신의 인덱스 값으로 초기화한다.  2) 2개의 노드 각각의 대표 노드를 찾아 union 연산으로 연결한다.예를 들어 두 번째 줄 입력을 받아서 0일 때 union(1,3) 을 해주면 arr[3] = 1로 값이 변경된다.이때, 작은 값을 대표 노드로 본다. 유니온 파인드 알고리즘에서 유의할 것은 입력 6번째 줄 union(3,7) 인 경우다.5번째 줄까지 모두 진행되었..

안녕하세요:) 코타키나발루는 말레이시아 사바주에 위치해 있으며비행기로 대략 5시간 반정도 걸립니다.  시차는 우리나라보다 1시간 느려요.한국이 3시라면 코타키나발루는 2시입니다. 코타키나발루는 코로나 검사가 필요 없습니다.공항에서 확인 안 해요. 그냥 가시면 됩니다. 다음은 말레이시아 코타키나발루 콘센트 모양이에요.  맨 밑에 구멍 세 개 보이시나요? 230V 3구 모양으로 대부분 이렇게 생겼습니다.  이마트나 다이소에서 멀티어댑터를 구매하면 됩니다.  환전소는 곳곳에 많이 있어요. 한국 돈 약 300원이 1링깃이에요. 한국돈으로 환전소에서 환전이 가능하므로 5만원권을 챙겨가시면 됩니다.  공항에 유심 파는 곳이 세 군데가 있어요. 미리 유심을 사지 않아도 여기서 싸게 구매할 수 있습니다.  일주일 동안..