이 문제를 풀 때 모두 다음과 같은 풀이 법을 떠올렸을 것이라 생각한다. 어떤 위치에 올 수 있는 경우의 수는 위쪽 위치에 올 수 있는 경우의 수와 왼쪽 위치에 올 수 있는 경우의 수를 더한 것이다. 웅덩이가 있는 부분은 in 함수를 써서 해당 위치일 경우에는 0 값을 넣어주면 간단하게 해결되는 문제이다! 그리고 나는 이러한 방식을 첫줄과 첫열에도 적용하기 위해서 (계산의 편의를 위해) 한 줄과 한 열을 더 만들었다. 한 줄씩을 더 만들고 집이 있는 곳의 값을 1로 주면 왼쪽과 위에 있는 값을 더해서 현재의 값이 나오도록 짤 수 있다. def solution(m, n, puddles): dp = [[0]*(m+1) for _ in range(n+1)] dp[1][1] = 1 for i in range(1..

이해를 돕고자 그림을 그려봤다... 목적은 정수 삼각형과 같은 리스트를 만드는 것인데, 점점 아래로 내려갈 수록 위의 값과의 합을 저장하여 리스트르 만드는 것이었다. 예시로 그럼에 위 세 줄만 뽑아서 만들어봤다 문제는 가운데에 있는 값의 경우 왼쪽에서 내려온 값과 오른쪽에서 내려온 값 2가지의 경우가 생긴다는 것이다. 문제에서는 가장 큰 값을 구하는 것이 문제이므로 두 값을 비교한 후 더 큰 값을 저장하기로 한다. 이때 그림에서도 볼 수 있듯이 오른쪽 값은 항상 자기와 같은 idx 값을 가지고 왼쪽 값은 idx-1 값을 구하면 된다. def solution(triangle): height = len(triangle) list = [0]*height for i in range(height): if i==0..

우선 N으로 표현 코드를 설명하기 전, 저의 코드가 그다지 깔끔하고 예술적인 코드는 아니라는 점을 말씀드립니다.. 하지만 이 문제를 풀며 겪었던 생각들과 사고의 과정을 담아보고자 합니다 :) N으로 표현은 코딩테스트 공부를 결심하고 가장 처음으로 풀었던 문제다. (왜 이런 잘못된 선택을 했을까..) 처음에는 곱하기, 나누기, 더하기, 빼기를 다 섞어보며 어떻게든 모든 경우의 수에 부합하는 논리를 만들고자 했으나... 경우의 수가 너무 많다는 것을 깨달았다. 숫자를 자리수로 채울 수도 있는게 컸다. 이렇게 경우의 수가 많은 경우에는 모든 상황을 아우르는 궁극의 알고리즘을 찾아내려 하는 것이 아니라, 해당 문제에서만 가능한 알고리즘을 찾는 것이 바람직 하다는 것을 깨달았다! ( 예전에 수능 수리영역을 공부할..

체육복 문제는... 정말 해결이 안되는 테스트 케이스가 있었던 문제다 그 이유는 reserve 배열이 정렬이 안되서 들어오는 것이었던 것!! 나는 예시도 정렬이 되어 있고 하다보니 당연히 정렬이 되어 있을 줄 알았다. 이 문제를 통해 가장 강하게 깨달은 점은 list 에서 알 수 없는 (?) 오류가 생기면 1. deep copy, shallow copy, 참조 문제가 아닐까? 2. 정렬 문제가 아닐까? 를 생각해 봐야지 라는 점이다. 문제 자체는 크게 어렵지 않았던 것 같다. 학생들의 수와 맞게 list 를 만들고 모두 체육복을 가지고 있다는 뜻에서 1을 참조하도록 한다. 그리고 잃어 버린 학생 리스트가 나오므로 lost 배열에 따라서 해당하는 학생을 1 => 0 으로 만들어 준다. 그리고 제약 조건에 ..

우선 아래 풀이에 앞서, ord 함수를 소개하고자 한다. print(ord('A')) 위 결과 값으로는 65가 나오고 ord 함수는 character 의 ASCII code 값을 반환하는 함수이다. 나는 이 함수를 몰랐기에.... 아래 코드 처럼 panix 라는 dictionary 를 정의해서 풀었다 :( 이 문제를 풀 때는 오른쪽 왼쪽으로 움직이는 횟수와 위 아래로 움직이는 횟수를 분리해서 풀었다. - 위 아래로 움직이는 문제는 해당 알파벳을 숫자로 변환한 후 Z 에서 내려가는 것과 A 에서 올라가는 것 중에 어느 것이 더 가까운지 비교해서 더하는 것으로 계산했다. - 오른쪽 왼쪽으로 움직이는 횟수는 처음에 그냥 오른쪽으로 갔을 때와 왼쪽으로 갔을 때를 비교해서 더 적은 횟수를 기준으로 계산했지만 큰 ..

주어진 number 에서 k 자리수를 제외하여 큰 수를 만드는 문제이다. 어떤 수가 만들어 지든지 간에 k 자리수를 제외하면 결국 남는 number 의 자리수는 동일하다. 그렇다면 가장 큰 수란? 앞자리가 1이라도 더 큰 수가 가장 큰 수이다! 이 문제를 풀며 배운 점은, 앞자리와 뒷자리를 계속 비교해야 하는 로직에는 Stack 자료구조를 사용해야 한다는 점이다. 즉 나는 stack 에 number 를 차곡차곡 쌓으면서 만약 스택의 가장 상단에 위치한 값보다 큰 값을 넣는 경우에는 최상단 값을 삭제하는 논리로 문제를 풀었다. 중요한 점은 최상단 값을 삭제하고 다시 넣으려고 할 때, 다시 최상단 값과 넣는 값을 비교하여 넣는 값이 클 경우에는 위 과정을 반복하도록 했다. 이러한 반복문이 끝나는 시점은 삭제..

이 문제는 처음에 문제를 이해하기 위해 종이에 다음과 같은 좌표(?) 그림을 그려보았다. 문제 자체가 자동차들의 데이터를 바탕으로 카메라 위치를 결정하는 문제이기 때문에 자동차 데이터 들을 먼저 정렬할 필요성을 느꼈다. 자동차의 데이터에 따라서 카메라의 개수를 결정하면 되는 문제라고 생각했다. 문제는 정렬의 기준이었다. 자동차들이 들어오는 시간을 기준으로 할 것인지 혹은 나가는 시간을 기준으로 할 것인지 였는데, 나가는 시간을 기준으로 정렬하고자 했다. 뭐로 하든 상관 없을 것 같은데, 나가는 순으로 정렬하면 다음과 같은 경우의 수를 줄일 수 있었다. 기준으로 선택한 자동차의 나가는 시간과 다음 자동차의 들어오는 시간을 비교해야 하는데 나가는 순으로 정렬되어 있다면 위 경우 처럼 다음 자동차의 나가는 시..

문제를 읽자마자 아~ 이런 문제 어디서 많이 봤는데? 라는 생각이 들었다. 찾아보니 Kruskal 알고리즘의 대표적인 유형이었다. 나는 이 문제를 풀기 위해 3가지 개념을 공부했다. 1. Python 에서 list 를 정렬하는 방법 2. Union - Find 자료구조 3. Kruskal 알고리즘 1. Python 에서 list 를 정렬하는 방법 파이썬의 정렬에는 list.sort() 와 sorted(list) 두 가지 종류가 있다. list.sort() 의 경우에는 list 를 정렬해 주지만, sorted(list) 의 경우에는 list 를 정렬한 것을 리턴해준다는 특징이 있다. sorted(list) 의 경우 list 자체에는 영향을 미치지 않는다. 또한 sort() or sorted() 에는 2가지..

다른 것 보다도 문제를 풀면서 있었던 사고의 흐름을 적어보고자 한다. 먼저, 보트에는 무게 제한이 있기 때문에 최대한 무게 제한에 가까운 숫자로 보트를 꽉꽉 채워 넣는 것이 중요하다고 생각했다. 그렇게 하기 위해서는 무게가 많이 나가는 사람부터 태우고, 남는 무게 중 가능한 사람이 있으면 추가로 태우는 방식을 고려했다. 때문에 사람들을 무게 순으로 정렬했다. 그 다음은 반복문을 어떻게 돌까? 하는 고민이 들었다. 가장 큰 수부터 뽑고 남은 무게를 채울 수 있는 사람이 있는지 확인해야 하는데, 가장 작은 몸무게 부터 확인해야 할지, 그 다음으로 큰 몸무게 부터 확인해야할 지가 고민이었다. 결론은 그 다음 큰 수를 뽑을 경우 이전의 큰 수 보다 무조건 작기 때문에, 작은 수를 뽑을 때도 가장 작은 몸무게 부..

안녕하세요 :) 이번 포스팅은 [자바스크립트 프로토타입] 입니다. 1. Prototype 이란? 모든 자바스크립트의 객체 (Objects) 들은 Prototype 으로부터 Properties 와 methods 를 상속 받습니다. 예시로 우리가 자주 사용하는 list 를 하나 생성하겠습니다. let list = [1, 2, 3]; console.log(list.length) //3 위 예시를 보면 list 객체만 정의했을 뿐인데, list 내부 요소들의 개수를 알려주는 length 변수가 생성된 것을 알 수 있습니다. length 변수는 어떻게 생성된 것일까요? 콘솔창에서 list를 생성하고 그 모습을 보게 되면 [[Prototype]] 속성이 추가된 것이 보입니다. 이는 list 와 같은 Array ty..