Python으로 푸는 LeetCode 877. Stone Game

LeetCode 877. 문제는 Dynamic Programming 에 관한 문제이다. 문제를 푸는 방법에 대해서는 Solution에 자세히 나와있지만 포스팅 하며 알게 된 내용들을 정리하고 나중에 다시 이 문제를 찾아볼 때 빠르게 이해할 수 있도록 이 글을 작성한다.··· array에 숫자들이 들어있고, Alex와 Lee가 맨 앞과 맨 뒤 중에 원하는 위치의 숫자를 번갈아 가면서 뽑는다. Alex가 항상 먼저 뽑는다고 했을 때, Alex가 항상 이기는 경우 True를 반환하도록 한다.LeetCode에서 문제보기Dynamic Programming으로 풀기Alex와 Lee가 게임을 마치려면 piles에서 숫자를 꺼내는 각각의 작은 작업들을 번갈아 수행해야하고, 이러한 반복 작업은 DP를 활용한 재귀로 구현..
온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 2. 24. 23:30

Python으로 푸는 SW Expert Academy 1868. 파핑파핑 지뢰찾기

1868. 는 주변에 지뢰가 없는 경우 연쇄적으로 터지는 지뢰찾기 게임을 구현하는 문제이다.삼성 SW Expert Academy 문제 리스트 보러 가기github에서 코드 보기문제 조건- 2차배열에서 지뢰가 어디에 있는지 표시('*')되어 있다. - 지뢰가 없는 칸을 클릭하면, 가로,세로,대각선의 8개의 위치에서 지뢰가 몇 개인지 숫자가 표시된다.- 클릭한 칸의 주변 지뢰의 수가 0이라면, 연쇄적으로 주변의 칸까지 터질 수 있다. (그 주변 칸의 주변 지뢰수가 0이라면 또다시 이 작업을 연쇄적으로 반복한다)- 지뢰가 있는 칸을 제외한 다른 모든 칸의 숫자들이 표시되려면 최소 몇 번의 클릭을 해야하는지 구하여야 한다. 문제 이해하기 : 클릭하는 위치 , * : 폭탄 위치기본 예시로 주어진 두가지 테스트 케..
온라인 코딩 테스트 문제 풀이/삼성 SW Expert 문제 풀이 2019. 2. 23. 23:30

Python으로 푸는 SW Expert Academy 2819. 격자판의 숫자 이어 붙이기

SW Expert Academy 2819. 문제는 격자판의 원소를 총 6번 이동하면서, 각 칸에 적힌 숫자를 차례대로 이어 붙여 만들 수 있는 7자리의 수의 갯수를 구하여야 한다.삼성 SW Expert Academy에서 푼 문제 리스트 보기github에서 코드 보기문제 조건격자판을 벗어나선 안된다.한번 거쳤던 격자칸을 다시 거쳐도 되며, 0으로 시작하는 수를 만들 수도 있다.+ 제자리 걸음을 해선 안된다.+ 만들어진 숫자가 중복 되어선 안된다.문제 풀이완전 탐색 방법으로 문제를 풀어야 한다. 격자판의 16개의 원소 각각을 시작점으로 하여 6번을 이동했을 때 나올 수 있는 모든 경우를 탐색해야 한다.단, 나올 수 있는 7자리 숫자의 모든 경우의 수를 탐색하면서도 그게 기존에 나온 숫자인지도 확인해야 한다...
온라인 코딩 테스트 문제 풀이/삼성 SW Expert 문제 풀이 2019. 2. 22. 23:30

Python으로 푸는 조합과 순열

arr = ['a', 'a', 'b', 'c'] 순열 (permutation) : 원소의 값이 같더라도 순서가 다르면 서로 다른 원소로 취급하며, 원소의 순서( [ ('a','b'), ('b','a) ] )가 다르면 서로 다른 경우의 수입니다.순열 결과 : [('a', 'a'), ('a', 'b'), ('a', 'c'), ('a', 'a'), ('a', 'b'), ('a', 'c'), ('b', 'a'), ('b', 'a'), ('b', 'c'), ('c', 'a'), ('c', 'a'), ('c', 'b')]ss 조합 (combination) : 원소들을 조합하여 만들 수 있는 경우의 수이며,원소들의 값이 같으면 서로 같은 경우의 수입니다.조합 결과 : [('a', 'a'), ('a', 'b'), ('..
온라인 코딩 테스트 문제 풀이/문제 풀이 전략 2019. 2. 21. 23:00

Python으로 푸는 백준 14502. 연구소

백준 14502. 연구소바이러스 유출을 막기 위해 연구소에 벽을 세우려고 할때, 3개의 벽을 세워서 가장 많은 안전구역을 확보할 수 있는 경우그 최대값을 반환하는 코드를 짜야한다.백준 문제 보러가기백준에서 푼 문제 리스트 보러가기github에서 코드 보기문제 조건예제 3번 케이스에서 벽을 세우는 경우는 다음과 같다. 8 82 2 2 2 2 2 2 22 2 2 2 2 2 2 22 2 2 2 2 2 2 22 2 2 2 2 2 2 22 2 2 2 2 2 2 21 2 2 2 2 2 2 20 1 2 2 2 2 2 20 0 1 2 2 2 2 2문제 풀이 문제는 모든 경우의 수를 탐색해야 한다. 안전구역에 벽을 어디에 세울지를 짜야만 문제를 풀 수 있다. 이 문제는 조합으로도 풀 수 있는 문제이므로, itertool..
온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 2. 20. 23:30

Python으로 푸는 SW Expert Academy 1240. 단순 2진 암호코드

SW Expert Academy 1240. 단순 2진 암호코드 문제에서는 0과 1로 구성된 영상물에 삽입된 암호 코드를 추출하여 암호 코드가 정상적인 암호코드인지 판별하는 코드를 구현해야 한다.삼성 SW Expert Academy에서 푼 문제 리스트 보기github에서 코드 보기문제 조건- “(홀수 자리의 합 x 3) + 짝수 자리의 합 + 검증 코드” 가 10의 배수가 되어야 한다.문제 풀이처음에는 문제 자체가 이해가 가지 않을 수도 있다. 주어진 그림이 이해가 잘 되지 않기 때문인데 그것만 이해하면 쉽게 문제를 풀 수 있다. 그래서 난이도가 D2인듯.먼저 input 값에서 암호 코드를 추출해 내야 한다. 필요없는 0들로 둘러쌓인 값들 중에서 0으로 시작하고 1로 끝나는 56자리의 암호 코드를 추출해 ..
온라인 코딩 테스트 문제 풀이/삼성 SW Expert 문제 풀이 2019. 2. 19. 23:30

Python으로 푸는 SW Expert Academy 1961. 숫자 배열 회전

SW Expert Academy 1961. 숫자 배열 회전문제에서는 N * N 행렬이 주어질 때, 시계 방향으로 90도, 180도, 270도 회전한 모양을 출력해야 한다.삼성 SW Expert Academy에서 푼 문제 리스트 보기github에서 코드 보기 문제 풀이문제 자체는 어렵지 않다. 파이썬의 zip 함수를 사용한다면 문제를 쉽게 풀 수 있다.matrix = [[ 1, 2, 3],[ 4, 5, 6], [7, 8, 9]] matrix에 zip 함수를 사용해보면 다음과 같이 튜플 형태로 반환된다. 각 줄별로 index가 같은 값들을 가져와 새로운 배열을 만들어 준다. zip_matrix = list(zip(*matrix))print(zip_matrix )[(1, 4, 7), (2, 5, 8), (3,..
온라인 코딩 테스트 문제 풀이/삼성 SW Expert 문제 풀이 2019. 2. 18. 23:30

Python으로 푸는 SW Expert Academy 4613. 러시아 국기 같은 깃발

SW Expert Academy 4613. 러시아 국기 같은 깃발 문제는 러시아 국기 같은 깃발을 만들기 위해서 입력받은 문자열을 활용하여새로 칠해야 하는 칸의 개수의 최솟값을 구해야 한다.SW Expert Academy에서 푼 문제 리스트 보기github에서 코드 보기 문제에서 제시한 조건- 색깔의 순서는 흰색 - 파란색 - 빨간색으로 정해져 있다.- 색깔은 반드시 한번 이상 칠해져야 한다. 그래야 러시아 국기 같은 국기가 되기 때문이다.풀이 방법가장 위와 아래는 반드시 흰색과 빨간색으로 칠해야 한다. 그러므로 2줄 ~ (n -1)줄 부분에 어떤 색을 칠해야 할지를 고민하면 된다. 2줄 ~ (n -1)줄 부분에는 반드시 파란색 줄이 한 줄 이상 들어가면서도 색의 순서를 고려하여 가장 효율적으로 각 줄의..
온라인 코딩 테스트 문제 풀이/삼성 SW Expert 문제 풀이 2019. 2. 17. 23:30

Python으로 푸는 SW Expert Academy 4615. 재미있는 오셀로 게임

SW Expert Academy [2차원 배열 탐색 연습문제] 4615. 재미있는 오셀로 게임문제에서는 오셀로라는 게임의 규칙에 따라 흑,백의 돌을 놓고플레이어가 돌을 모두 두었을 때, 게임판에 올려진 흑,백의 돌의 개수를 각각 출력해야 한다.이 문제는 백준 15671. 오델로와 유사한 문제기 때문에, 이 문제를 푼다면 백준의 문제도 풀 수가 있다.만약 SW Expert Academy 4615. 재미있는 오셀로 게임을 푸는데 테스트 케이스를 모두 통과하지 못한다면게임판을 6*6 크기로 한정한 백준의 오델로 문제를 먼저 풀어보자.삼성 SW Expert Academy에서 푼 문제 리스트 보기백준 15671. 오델로 풀이 보러 가기github에서 코드 보기문제에서 제시한 조건자신이 놓을 돌과 자신의 돌 사이에..
온라인 코딩 테스트 문제 풀이/삼성 SW Expert 문제 풀이 2019. 2. 16. 23:30

python으로 푸는 백준 15671. 오델로

백준 15671. 오델로 문제는 SW Expert Academy 4615. 재미있는 오셀로 게임과 매우 유사한 문제이다. 만약 SW Expert Academy 4615. 재미있는 오셀로 게임을 푸는데 테스트 케이스를 모두 통과하지 못한다면게임판을 6*6 크기로 한정한 백준의 오델로 문제를 먼저 풀어보자.백준 덕분에 테스트 케이스도 한개가 더 느니까 테스트도 좀더 수월하다.이 문제는 오셀로 규칙을 적용해서 흑,백의 돌을 두었을 때 맨 마지막 돌들이 어떻게 놓여져있는지와 승패를 출력하는 문제이다.SW Expert Academy 4615. 재미있는 오셀로 게임 문제 풀이 보기백준에서 문제 보기백준에서 푼 문제 리스트 보기github에서 코드 보기문제에서 제시한 조건문제를 푸는데 에러가 난다면 아래의 조건을 다..
온라인 코딩 테스트 문제 풀이/백준 문제 풀이 2019. 2. 15. 23:30

Python 내장 함수의 시간 복잡도

Python 컨테이너 메소드의 시간 복잡도(time complexity)는 어떻게 될까? 알고리즘을 풀면서 컨테이너를 조작하기 위해 기본 메소드들을 많이 활용하게 되었고, 메소드의 시간 복잡도가 궁금해졌다.경우에 따라서 어떤 메소드를 사용하느냐가 알고리즘의 시간 복잡도를 크게 좌지우지 할때가 있다. 물론 문제를 푸느냐 못푸느냐는 대부분 내 알고리즘이 문제이고, 메소드가 문제를 해결하는데 큰 영향을 미치는 경우는 드물다.그럼에도 궁금한 부분은 바로바로 정리해두는게 좋을 것 같아,이 포스팅에서는 python의 컨테이너별로 메소드의 시간 복잡도를 정리하려고 한다.시간 복잡도는 아래의 표와 같이 표기하고 읽는다. 아래로 내려갈 수록 시간이 오래 걸림을 뜻한다.시간 복잡도에 관한 자료는 Python 위키 문서에서..
Python/python 파헤치기 2019. 2. 14. 23:30

Python으로 푸는 LeetCode 1. Two Sum

LeetCode 1. Two Sum이 문제는 주어진 배열에 있는 두개의 원소를 더해 target 값을 항상 만들 수 있을 때그 두개의 원소의 index 값을 반환하도록 코드를 짜야 한다.LeetCode에서 문제 보기LeetCode에서 푼 문제 리스트 보기github에서 코드 보기예시로 문제 이해하기 nums = [2, 7, 11, 15] target = 9 nums[0] + nums[1] = 2 + 7 = 9# output : [0, 1]Related TopicArray, Hash Table문제 풀이input의 List는 정렬되어 있지 않으므로 먼저 정렬을 한다.첫번째 값부터 검사를 시작한다. 첫번째 값이 target 값을 만들기 위해서는 뒤에 반드시 (target - 첫번째 값)이 들어 있어야 한다.(..
온라인 코딩 테스트 문제 풀이/LeetCode 문제 풀이 2019. 2. 13. 23:30