Julie의 개발 기록

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/258707공식 해설 : https://tech.kakao.com/posts/610 문제 설명세모를 쌓아 만든 산모양 타일이 있다.각 산에는 머리(△)가 있을 수도 있고 없을 수도 있다.tops[i] = 0 이면 i번째 산은 머리(△)가 없고, tops[i] = 1 이면 i번째 산에 머리(△)가 있는 것이다.위 그림같은 경우 n = 3, tops = [1, 1, 0, 1] 로 입력값이 주어진다.  이 타일을 마름모 모양 타일과 정삼각모양 타일 두가지로 덮는 경우의 수를 구하면 된다. 각 타일은 회전할 수 있다. 해법처음엔 재귀로 완전탐색을 해볼까 했는데, 각 방법이 유일하다는걸 증명하려면 지도..

문제 바로가기 : https://www.acmicpc.net/problem/2665 그림과 같은 N x N 미로가 있다. 빈방은 흰색(1), 벽은 검은색(0)이다.(0, 0)에서 시작해서 (n-1, n-1)로 가기 위해 최소 몇개의 벽을 뚫어야하는지 구하는 문제이다.한 변의 길이 N은 1 이상 50이하이고, 실행 제한시간은 1초이다.  처음에는 모든 경우의 수를 모두 돌아보되, 가능성이 없는 경로는 빠르게 쳐내기 위해 DFS로 빠르게 최소비용을 구하고자했었다.쓸데없이 경로를 꼭 알아야한다고 생각을 했던것...그렇지만 우리 문제는 어떤 경로를 사용했는지가 중요한 문제가 아니라서, BFS로 미로를 돌며 (0, 0)에서 임의의 (x, y)로 가려면 얼마의 비용이 드는지 구하는 것으로 방향을 틀었다. 전체 구현..

함수형 프로그래밍을 공부하다보면 map, filter, reduce, foreach 등을 사용하여 의도가 명확하게 드러나도록 코드를 작성하는 시도를 하게된다. 파이썬에도 이러한 접근을 돕기위한 빌트인 라이브러리가 존재한다. 그런데 반환값이 특이하다.map(변환람다, 원본리스트) # 람다를 적용한 변환 결과를 map 형태로 반환filter(변환람다, 원본리스트) # 람다 결과가 True인 것만 뽑아서 filter 형태로 반환zip(키배열, 밸류배열) # 튜플 iterator 반환 map, filter를 반환한다는 부분이 이해가 안될 수 있는데, 정말 반환 결과의 타입을 출력해보면 각각 map과 filter로 나온다.  그리고 아래처럼 map은 두번 사용할 수가 없다.def divide_arr(): i..

문제 링크 : 백준 1253. 좋다  /  정답 코드 바로가기  주어진 N개의 수 중에서 '좋은수'를 찾아야한다.좋은수란 다른 두 수의 합으로 나타낼 수 있는 수를 의미한다.값이 같아도 숫자의 위치가 다르면 다른 수로 취급한다. [1, 1, 2, 2, 2]예를 들어 위 케이스에서, 각 2는 모두 다른 수이므로 결과는 3이 되어야한다. 숫자 배열의 길이는 1 ~ 2,000 이며, 각 수의 범위는 -1,000,000,000 ~ 1,000,000,000 이다. 예시 케이스Case 1 ) input : [-1, 0, 1] / output : 1 -1 은 좋은 수가 아니다. -1을 제외한 [0, 1] 로는 -1을 만들 수 없다.0 은 좋은수이다. (-1) + (1) 을 더해서 만들 수 있다.1 은 좋은 수가 아니..

문제 링크 : 프로그래머스 다단계 칫솔 판매 항상 자신의 추천인에게 판매 대금의 10%를 떼줘야하는 다단계 기업이 있다.10% 수수료 계산시 소수점을 버림하는 규칙이 있다.아래와 같은 4개의 배열이 주어질 때, 주어진 각 멤버의 수익을 계산해서 배열로 반환해야한다.빠르게 부모 노드를 찾을 수 있는 자료구조를 고안하는것과, 반례를 찾는것이 중요한 문제였다. 예시 케이스조직도가 [ 사장 - A - B - C ] 형태일 때, 인풋은 아래와 같이 주어진다. 조직도는 아래 형태로 주어지고 [0][1][2]enroll (멤버이름)ABCreferral (추천인)- (사장은 "-" 로 표시한다.)AB 칫솔 판매 실적은 아래처럼 주어진다. 칫솔은 하나에 100원으로 고정이다. [0][1][2]seller (판매 담당자)..

문제 링크 : https://www.acmicpc.net/problem/14712 N x M 격자 안에 네모를 배열하되, 2 X 2 정사각형 모양이 없도록 하는 경우의 수를 구하는 문제이다.예를 들면 격자가 2 X 3 이라고 할 때 세어야하는 경우와 아닌 경우는 아래와 같다.  행의 개수 N, 열의 개수는 M으로 주어지고, 시간제한은 1초이다. (1 ≤ N, M ≤ 25, 1 ≤ N × M ≤ 25) 아무리 생각해도 모든 경우의 수를 만들어낸 후, 네모가 있는지 검사하는 것이 가장 확실하다는 생각이 들었는데, 이중 list를 사용하면 시간도 메모리도 초과할 것이 뻔했다. 게다가 이러면 네모 유무를 확인하는것도 어려웠다. 각 경우의 수를 검사하는 방식을 엄청나게 최적화 해야 최대 2 ^ 25 가지 경우의..

코딩 테스트를 풀 때 필요에 따라 Kotlin, Python, JS를 번갈아가면서 써봤지만, 머리속 생각을 바로 코드로 옮기는 데에는 파이썬만한 언어가 없어서 거의 정착하게 되었다. 이런 결정을 할 때 신경쓰이는건 '파이썬은 느리다' 라는 평가이다. 시간 제한이 있는 문제도 있기 때문에 괄시할 수 없는 문제였다. LeetCode에서 같은 논리구조, 다른 언어로 솔루션을 올리는 사람들의 코드를 빌려 실행시간에 정말 유의미한 차이가 있는지 알아보기로 했다. 아래는 실행시간을 측정한 결과이다. 단위 : msC++PythonPython3JavaScriptSpiral Matrix IV5123860Split Linked List4264157Max Score2173159Min Count of BitFlip02534..

문제 배열 nums가 주어질 때, nums의 원소들을 k 만큼 오른쪽으로 미는 코드를 작성해라. Space complexity O(1)로 풀어보라는 추가 조건이 있으면 어려워진다. 예시 Input: nums = [1,2,3,4,5,6,7], k = 3 Output: [5,6,7,1,2,3,4] // 반환타입 없음 조건 1

문제 Implement pow(x, n), which calculates x raised to the power n (i.e., xn). **Binary Search의 예시 문제로 출제되었다. 예시 Input: x = 2.00000, n = -2 Output: 0.25000 Explanation: 2-2 = 1/22 = 1/4 = 0.25 조건 -100.0 < x < 100.0 -2^31

data class Position( var x: Int, var y: Int, ) { operator fun plus(other: Position): Position { return Position(this.x + other.x, this.y + other.y) } // 깊은 복사에는 .copy 호출(data class에서 구현해줌) } enum class Direction(position: Position) { TOP(Position(-1, 0)), BOTTOM(Position(1, 0)), LEFT(Position(0, -1)), RIGHT(Position(0, 1)) } * copy 사용시 주의할 점 : x, y에 Primitive type이 아닌 객체를 사용한다면, 직접 깊은 복사를 구현해야한다..