프로그래밍 관련 정보

 문제 설명 문제 링크:  https://school.programmers.co.kr/learn/courses/30/lessons/12902 Idea 풀이 방법이 직관적으로 떠오르지 않아 정의된 문제의 N 값에 따른 답안을 구하며 규칙을 찾아보기로 했습니다. 우선 2x1인 직사각형 타일을 이용하여 3xN인 바닥을 채워야 합니다.  다만, 3xN 바닥의 세로 길이가 3이기 때문에 2x1 직사각형은 반드시 누워져서 들어가는 경우가 발생합니다. 이는 N이 홀수인 경우엔 2x1 직사각형 타일을 이용하여 3xN 바닥을 채울 수 없음을 의미합니다. (아래 그림 참고) 3x3, 3x5인 바닥의 경우 위 이유로 규칙은 N이 짝수인 경우에만 찾도록 하겠습니다. 1. 규칙 찾기 N=0: 0개, 타일을 둘 수 없음 N=2: 3개, 아래 사진 참고 N=4: 11개, (3*3 + 2)   - N=2일 때 있었던 3개의 경우에 다시 3가지의 경우의 수들 추가.   - N=4일 때 특수한 형태의 모양 생성 (그림 맨 하단 참고)  N=6: 41개, (3*11 + 2*3 + 2)   - N=4일 때 있었던 경우에 다시 3가지의 경우의 수들 추가.   - N=4일 때 있었던 특수한 형태의 모양에 대한 예외 경우의 수 추가 (그림 우측 참고)      > 특수한 형태의 모양은 "앞, 뒤"에 따라 다른 경우의 수를 만들 수 있습니다.    - N=6일 때 특수한 형태의 모양 생성 (그림 맨 우하단 참고)  N=8: 153개, (3*41 + {6*3+2*2} + 2*3 + 2)   - N=6일 때 있었던 경우에 다시 3가지의 경우의 수들 추가.   - N=6일 때 있었던 특수한 형태의 모양에 대한 예외 경우의 수 추가 (그림 우상단 참고)      > 특수한 형태의 모양은 "앞, 뒤"에 따라 다른 경우의 수를 만들 수 있습니다.    - N=4일 때 있었던 특수한 형태의 모양에 대한 예외 경우의 수 추가 (그림 우중

  문제 설명 문제 링크:  https://school.programmers.co.kr/learn/courses/30/lessons/148652 Idea 풀이 방법이 직관적으로 떠오르지 않아 정의된 문제에 대한 규칙을 찾아보기로 했습니다. 1. 규칙 찾기 N=0 : 1 (1개) N=1 : 1 / 1 / 0 / 1 / 1 (5개) N=2 : 11011 / 11011 / 00000 / 11011 / 11011 (25개) N=3 : 1101111011000001101111011 / 1101111011000001101111011 / 000000000000000000  / 1101111011000001101111011 / 1101111011000001101111011 (125개) N-1 값들이 앞뒤*2로 생기며 중간은 N-1의 길이의 0이 생기는 규칙을 발견할 수 있습니다. Ex. N=2라면, 11011(N=1)이 앞뒤*2로 생기며 중간에는 11011의 길이인 5개의 0이 생김       -> 11011 / 11011 / 00000 / 11011 / 110111 2. 규칙 정리 1. 규칙 찾기에서 찾은 규칙을 정리하면 아래와 같습니다. (1만 세서 정리) N cantor_bit total_1 len 1 1/1/0/1/1 4 5 2 4/4/0/4/4 16 25 3 16/16/0/16/16 64 125 4 64/64/0/64/64 256 625 5 256/256/0/256/256 1024 3125 N이 증가함에 따라 1의 수는 $4^{N}$으로, 길이는 $5^{N}$으로 증가하는 규칙을 발견할 수 있습니다. Ex. N=2라면, 1의 수는 총 16개 (4 / 4 / 0 / 4 / 4), 유사 칸토어 길이는 25 3. 수식 정리   1. 총 5개의 그룹으로 나눔 (X / X /

  문제설명 문제 링크:  https://school.programmers.co.kr/learn/courses/30/lessons/131701 Idea 행의 %N으로 원형 리스트 인덱스를 추출하여 탐색 후 값을 더해줍니다.  중복된 값이 없어야 하기 때문에 set을 이용하여 부분 수열 합의 값을 저장합니다. 이 때 부분 수열의 합을 구한 값을 재사용합니다. (구했던 값을 굳이 또 다시 구할 필요는 없습니다) Solution 01 def solution (elements): N = len (elements) for i in range (N- 1 ): elements.extend([elements[i*N+j] + elements[(i+j+ 1 )%N] for j in range (N)]) return len ( set (elements)) 부분 수열의 합을 구한 값들을 elements 변수에 추가하며 추가된 변수 값과 기존에 제공된 elements의 값을 더해줍니다. 이후 set으로 변경하여 중복되지 않은 부분 수열 합의 개수를 구합니다. Solution 02 def solution (elements): N = len (elements) ans = set (elements) add = [e for e in elements] for i in range ( 1 , N): for j in range (N): add[j] += elements[(i+j)%N] ans.add(add[j]) return len (ans) Solution 01의 접근법과 동일합니다. 다만 01에서 사용한 elements 리스트에 계산된 부분 수열의 합을 추가하는 형식이 아닌, add라는 리스트를 생성하여 부분 수열의 합을 누적하여 계산합니다. 계산된 값은 set에 바로바로 추가하며 중복되지 않은 부분 수열 합의 개수를 구합니다. So

문제설명 문제 링크:  https://school.programmers.co.kr/learn/courses/30/lessons/131130 Idea 특정 인덱스를 기반으로 cards를 탐색해 해당 리스트 값을 새 인덱스로 설정하며 cards를 탐색합니다. 이미 탐색된 cards에 접근한 경우 탐색을 종료하고, 이 때까지 탐색된 수량을 저장합니다. 전체 cards를 모두 탐색할 때까지 위를 반복합니다. 탐색이 종료된 경우 탐색된 수량이 2개 이상이면 최대 수량 2개의 곱을, 1개 이하면 0을 반환합니다. Solution 01 def solution (cards): ans = [] for i in range ( len (cards)): cnt = 0 pts = i while cards[pts]: cnt += 1 temp = cards[pts] cards[pts] = 0 pts = temp - 1 if cnt: ans.append(cnt) ans.sort() return 0 if len (ans) < 2 else ans[- 1 ] * ans[- 2 ] 0~N-1까지 돌며, 탐색하지 않은 cards[pts]라면 해당 값을 pts 변수에 저장하고 방문한 수량(cnt)을 증가합니다. 이미 방문한 cards라면 그 전까지의 수량을 ans 변수에 저장합니다. ans 변수를 오름차순으로 정렬한 뒤, 길이가 2 이상이면 -1 번째와 -2번째 길이의 곱을 반환합니다. 전체 코드는 깃허브 에서 확인 가능합니다.

  16진법이란 16진법은 10개의 숫자(0~9)와 6개의 문자 (A~F)를 사용해서 값을 표현합니다. 문자는 A(10), B(11), C(12), D(13), E(14), F(15)이며 아래 표를 참고하세요. 위 그림에서 2진법은 15라는 숫자를 4자리로 표현하는 반면 16진수는 1자리로 표현할 수 있습니다. (2의 4승을 표현할 수 있기 때문) 16진법은 4개의 비트 값을 "한번"에 표현할 수 있다는 점을 확인해주세요. 16진법을 사용하는 이유 바이트가 커질 때 2, 10, 16진법 범위를 보게되면 아래와 같습니다. 2진법은 바이트가 늘어남에 따라 자릿수가 기하급수적으로 늘어나는 단점이 존재하며, 사람은 10진수에 익숙하기 때문에 2진수로 적힌 값이 10진수로 얼마인지 직관적으로 파악하기 어렵습니다. 0b1111101000은 10진수로 얼마인가? -> 1000 반대로 10진법은 바이트마다 떨어지는 단위가 깔끔하지 않습니다.(255, 65535, 4294967295...) 또한 1000이라는 수는 2 바이트로 저장되는데, 만약 바이트 단위로 나눠 10진수로 표현할 때 문제가 발생합니다. (10진수는 바이트 단위로 나눠 떨어지는 값이 아니여서) 물론 각 바이트에 저장된 1000을 표현하기 위해 256(1바이트 범위)으로 나눠 몫과 나머지로 표현할 수 있습니다. (256 * 3 + 244 = 1000) 다만, 2바이트를 몫과 나머지로 표현한 그림을 보고 1000이라는 것을 직관적으로 이해할 사람은 거의 없을 겁니다. 마지막으로 16진법은 1바이트(8비트)마다 FF 단위로 증가하고 자릿수 또한 다른 진법보다 적게 사용합니다.  1000을 2진수로 표현할 때 사람이 직관적으로 변환 할 수 없고 계산을 통해  0b1111101000임을  알 수 있습니다. 하지만 16진법은 0x3e8(1000)로 훨씬 짧게 표현할 수 있으며, 16진법은 자릿수가 4비트를 의미하기 때문에 아래와 같이 직관적인 2진법 변환 및 해

python - id() 파이썬의 Built-in Function으로 객체의 식별값을 반환하는 함수, 반환 값 타입은 int id(object) 인자로 object를 넣으면 id 함수는 객체의 unique한 int형 id값을 반환합니다. id란? 파이썬은 Call by Assignment로 모든 것을 객체로 식별합니다. (문자열, 정수, 클래스 등 모두 객체) id는 객체가 생성될 때 자동으로 할당되며 unique한 값을 보장합니다. 만약, 두 객체의 lifetime이 겹치지 않으면 같은 id 값이 할당될 수 있습니다. id는 C언어에선  메모리 주소  표현하고 파이썬은 unique id 로 표현합니다. (포인터 개념으로 이해하면 됩니다) id 할당은 프로그램을 실행할 때 마다 매번 다른 값이 부여됩니다. 단, 일반적으로 많이 사용되는 객체는 파이썬에서 내부적으로 메모리가 할당되어 있어 프로그램을 실행할 때 마다 같은 id가 부여됩니다. (Ex, int -5 to 256은 매번 같은 메모리 주소로 할당됨) Examples Mutable과 Immutable 개념이 헷갈리는 분은 Mutable과 Immutable 차이점 글 을 참고해주세요. 1. Mutable - list x = [ 1 , 2 , 3 ] y = [ 1 , 2 , 3 ] print ( f"x id: { id (x) } , y id: { id (y) } " ) # x id: 140572825821664, y id: 140572825824224 x와 y객체를 생성하면 자동으로 id가 할당되며, x와 y의 객체 id를 출력하기 위해 id() 함수를 이용합니다. 두 객체 id가 각각 140572825821664, 140572825824224로 할당된 걸 확인할 수 있습니다. 두 객체 id가 다른 이유를 모르시는 분은 Mutable과 Immutable 차이점 글 을 꼭 참고해주세요. 2. Mutable - set x = { 1 , 2 , 3 } y

Mutable과 Immutable 차이점 파이썬은 Call by Assignment로 모든 것이 객체이며, 속성으로 Mutable과 Immutable로 구분합니다. Mutable 이란? 객체를 생성한 뒤, 객체의 값을 수정할 수 있습니다.  값을 수정한다면 변수가 원래 가르키던 주소에 값을 수정합니다. 대표적으로 list, set, dict (아래 표 참고) Immutable 이란? 객체를 생성한 뒤, 객체의 값을 수정할 수 없습니다.  값을 수정한다면 변수가 가르키는 주소에 값을 수정하는 게 아닌,  새로운 주소에 새로운 객체를 가르킵니다.  (수정X, 새롭게 할당) 대표적으로 int, float, tuple, str (아래 표 참고) Mutable과 Immutable 비교 1. Mutable - list x = [ 1 , 2 , 3 ] y = x print ( f"x id: { id (x) } , y id: { id (y) } " ) # x id: 140542819770848, y id: 140542819770848 (주소 값 같음) print ( f"x: { x } , y: { y } " ) # x: [1, 2, 3], y: [1, 2, 3] x += [ 4 , 5 , 6 ] print ( f"x id: { id (x) } , y id: { id (y) } " ) # x id: 140542819770848, y id: 140542819770848 (주소 값 같음) print ( f"x: { x } , y: { y } " ) # x: [1, 2, 3, 4, 5, 6], y: [1, 2, 3, 4, 5, 6] y=x라는 구문으로 x, y는 동일한 주소(140542819770848)의 [1, 2, 3]을 가르키고 있습니다. (id 값이 동일) x에 [4, 5, 6]을 추가하면 140542819770848 주소에 있는 값이 변경 되기 때문에, y 값을

문제설명 문제 링크:  https://programmers.co.kr/learn/courses/30/lessons/43105 Idea 문제의 조건을 보면 "꼭대기에서 바닥까지 이어지는 경로 중, 숫자 합이 가장 큰 경우"를 찾는 문제입니다. 2차원 리스트가 주어졌을 때 모든 경우의 수를 계산 해야만 숫자 합이 가장 큰 경우를 찾을 수 있습니다. 리스트의 합을 구하는 조건은 "한 칸 오른쪽"과 "한 칸 왼쪽"으로 갈 수 있다고 정의되어 있습니다. 이는 triangle[0][0]에 있는 값은 triangle[1][0]과 triangle[1][1]로 갈 수 있고,  triangle[2][1]은 triangle[3][1]과 triangle[3][2]로 갈 수 있다는 의미입니다. 숫자의 가장 큰 합을 구해야하기 때문에 triangle[1][0]에는 triangle[0][0]+triangle[1][0]을 해주면 되고, triangle[3][1]은 triangle[3][1] + triangle[2][0] 또는 triangle[3][1] + triangle[2][1] 중 큰 값을 넣으면 됩니다. 이는 triangle[i][j] + triangle[i-1][j]와 triangle[i][j] + triangle[i-1][j+1] 중 큰 값을 triangle[i][j]에 넣어주면 됨을 유추할 수 있습니다. Solution 01 from copy import deepcopy def solution (triangle): # 0.298445245 triangle_temp = deepcopy(triangle) max_sum = triangle[ 0 ][ 0 ] for i in range ( 1 , len (triangle)): for j in range (i): if triangle[i][j] < triangle_temp[i][j

문제설명 문제 링크:  https://programmers.co.kr/learn/courses/30/lessons/42895 Idea 01 유의미한 풀이 규칙을 찾을 수 없어 다른 분의 접근 방법을 참고했습니다. ( 참고 블로그 ) 주어진 N은 2, number이 11일 때 return 3을 구할 수 있는 횟수(n)를 구하는 방법은 다음과 같습니다. n이 1일 때는 딱 1개만 만들 수 있습니다. n이 2일 때는 2를 2번 이어붙인 경우와, 2를 1번(n-1) 사용했을 때 값에서 2를 사칙연산한 경우가 존재합니다. n이 3일 때는 2를 3번 이어붙인 경우와, 2를 2번(n-1) 사용했을 때 값에서 2를 사칙연산한 경우가 존재합니다. N=2일 때, number=11을 만족하는 식은 22/2=11이고 이때 2가 최소 3번 사용된 걸 확인할 수 있습니다. 위 방법을 통한 풀이를 하기 위해서는 2를 이어붙이는 경우를 제외하곤 n이 2인 숫자 조합을 만들기 위해선 2를 1번(n-1) 사용했을 때 값과 2를 사칙연산합니다. n이 3인 숫자 조합을 만들기 위해선 2를 2번(n-1) 사용했을 때 값과 2를 사칙연산합니다. 특정 N에 대한 최소 조합을 구하기 위해선 n-1값에 N을 사칙연산하면 최소 n을 구할 수 있는 것으로 보이지만, 단순하게 n-1 숫자 조합에서 N을 사칙연산하는 방법으로는 최소횟수를 제대로 구할 수 없습니다. N=4일 때 number=3을 만족하는 최소 식은 4-(4/4)이지만, 위의 접근 방법을 사용하면 4에서 (4/4)를 빼주는 경우는 없습니다. (숫자조합이 (2+2)라면 여기에 2를 +, - ,*, / 만 진행하기 때문) Idea 02 위에서 발생한 예외(4-(4/4))를 처리하기 위해 다른 분의 접근 방법을 참고했습니다. ( 참고블로그 ) 우선 N=4일 때, 숫자 4를 최소 1~8번 조합할 수 있습니다. (문제에서 최소 사용 횟수를 8까지 정의) 4를 2번 사용해서 만들 수 있는 경우이며, 이 때 숫자 2에 대한