목록알고리즘/파이썬 (11)

수학과의 좌충우돌 프로그래밍

1로 만들기 (BAEKJOON - 1463번)

안녕하세요 강민성입니다. 오늘은 오랜만에 알고리즘 문제를 들고 와봤습니다. 겨울방학 동안 백준 사이트에 있는 문제를 풀어보고자 하는데 좋은 문제가 있으면 많이 포스팅 하도록 하겠습니다. 오늘 소개할 문제는 1463번 '1로 만들기' 라는 문제 입니다. 문제부터 보도록 하겠습니다. 문제는 생각보다 간단합니다. 3가지 연산만 골고루 써서 1을 만들어 주면 되는 것이죠. 그래서 문제없이 코드를 작성하였습니다. 123456789101112131415X = int(input()) count = 0while X!=1: print(X) if X % 3 == 0: X //=3 count += 1 elif X % 2 == 0: X //= 2 count += 1 else: X -= 1 count += 1print(coun..

알고리즘/파이썬 2018. 12. 31. 06:00
유클리드 알고리즘과 확장된 유클리드 알고리즘

안녕하세요 강민성입니다. 오늘은 유클리드 알고리즘과 그 확장에 대해서 알아보도록 하겠습니다. 유클리드 알고리즘이란? 먼저 유클리드 알고리즘이란 유클리드 호제법이라고도 하며 두 수에 대해서 최대공약수를 구하는 방법입니다. 두 수가 일반적인 방법으로 최대 공약수를 구하기 너무 커졌을 때 이 유클리드 알고리즘을 사용하면 보다 쉽게 구할 수 있습니다. 이제 유클리드 알고리즘을 살펴보면 두 수 a,b에 대해서(a>b), a = q * b + r 라 하면 q 는 몫, r은 나머지가 됩니다. 이 때, gcd(a,b) = gcd(b,r) 이 성립하고 이와 같은 과정을 계속 거쳐 나머지가 0이 되었을 때 나누는 수가 a,b의 최대공약수에 만족하게 됩니다. 예시를 통해서 알아볼까요? 240꽈 46의 최대공약수를 구한다고 ..

알고리즘/파이썬 2018. 12. 1. 21:54
숫자게임(프로그래머스-level3)

안녕하세요 강민성입니다. 이번에 풀 문제는 2018서머코딩 알고리즘 문제 중 하나 입니다. 대회에서 나오는 문제들을 보면 매번 저런 문제를 어떻게 만들어내는지 그저 신기할 따름입니다. 문제를 이해하고 코드를 짜는 것도 적지 않은 시간이 걸리곤 하는데... 요즘 주변에 취업원서 넣고 코딩테스트 보러 가는 사람들이 많아서 그런지 알고리즘의 중요성을 새삼 다시 깨닫습니다. 1차에서 떨어지는 경우도 비일비재 하더라고요. 그러면 문제 보도록 하겠습니다. [ 문제 ] xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 자연수를 하나씩 부여받습니다. 각 사원은 딱 한 번씩..

알고리즘/파이썬 2018. 9. 16. 01:02
땅따먹기(프로그래머스-level2)

안녕하세요 여러분 알고리즘 외에도 여러가지를 공부하다보니 하루에 한 개씩 포스팅을 하겠다던 계획을 지키기가 많이 어렵네요 ㅠㅠ 곧 알고리즘 외에도 웹프로그래밍, 인공지능 등 유익한 정보로 찾아뵙도록 하겠습니다. 오늘 알아볼 내용은 '땅따먹기' 입니다. 제목만으로는 무슨 문제가 유추가 안될텐데요, 문제는 다음과 같습니다. [ 문제 ] 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 || ..

알고리즘/파이썬 2018. 8. 7. 20:03
올바른 괄호의 갯수(프로그래머스-level4)

안녕하세요 강민성입니다. 이번에는 처음으로 level4 에 도전했는데요, 관련된 개념을 한 번 본 적이 있어서 level 4 치고는 쉽게 풀 수 있었습니다. 그러면 문제 부터 보시겠습니다. [ 문제 ] 올바른 괄호란 (())나 ()와 같이 올바르게 모두 닫힌 괄호를 의미합니다. )(나 ())() 와 같은 괄호는 올바르지 않은 괄호가 됩니다. 괄호 쌍의 개수 n이 주어질 때, n개의 괄호 쌍으로 만들 수 있는 모든 가능한 괄호 문자열의 갯수를 반환하는 함수 solution을 완성해 주세요. 제한사항 괄호 쌍의 개수 N : 1 ≤ n ≤ 14, N은 정수 입출력 예 n result 2 2 3 5 입출력 예 설명 입출력 예 #1 2개의 괄호쌍으로 [ (()), ()() ]의 2가지를 만들 수 있습니다. 입출력..

알고리즘/파이썬 2018. 8. 1. 13:41
하노이의 탑(프로그래머스-level3)

안녕하세요 강민성입니다. 프로그래머스에서 문제를 풀다보면 다음과 같은 문구를 보실 수 있을 겁니다. # 알고리즘 연습 문제가 개편 되었습니다. 이로 인해 함수 구성이 변경되어, 과거의 코드는 동작하지 않을 수 있습니다. 말 그대로 18년 5월 정도 부터 문제들이 약간씩 바뀌고 문제가 같더라도 테스트 케이스가 더 복잡해지고 정교해져서 옛날 풀이도 정답이 아닐 수 있습니다. 다른 블로그에 포스팅 된 글이나 프로그래머스 내에서 다른 사람의 풀이를 보실 때 참고하시길 바랍니다. 저는 개편된 후의 풀이임을 알립니다. 오늘 소개해드릴 문제는 제목에서 알 수 있듯이 하노이의 탑입니다. 아마 어디서 한 번 쯤은 들어보셨을 거라고 생각을 해요. 저도 고등학교 때 교과서에 나와서 접했던 기억이 있는데 이렇게 코드로 구현해..

알고리즘/파이썬 2018. 7. 30. 21:08