난이도: Lv.0유형: 시뮬레이션, bruteforce해결 여부: 테스트케이스 오답 후 해결아이디어2차원 배열에서 대각선 포함 근처에 폭탄이 없는 칸의 개수를 구하는 문제다. 그냥 쌩 순회여서 시간줄이는법있나 했는데 그냥 시뮬레이션 부르트포스 문제였다오답 이유 혹은 알게 된것이차원 배열 처리애서 애를 먹었다. 어떻게해야 효율적일지2차원 리스트 슬라이싱을 잘못해서 삽질했다. list[start:end][start:end] 이러면 딱 나오는줄 알았는데 이상한 값이 나왔다. 그래서 이런 경우 그냥 numpy 써서 np.array()로 변환해준 다음에 array[startY:endY, startX:endX] 이런식으로 하는게 나을 것이다. 3. 만약 numpy 쓰기 싫으면 directions로 8방향 리스트에 ..
Algorithm
난이도: Lv.1유형: 스택해결 여부: 오답아이디어숫자를 문자열로 접근하며, 각 자리의 숫자를 세는 계수적 정렬 사용아이디어 자체는 정답오답 이유 및 알게 된것시간초과문자열의 반복 추가에 반복문 사용 -> * 문법으로 바꾸었지만 여전히 시간초과문자열에서 특정 문자의 개수 셀 때 for문으로 1회 순회하여 사용 -> count() 함수 사용이 결정적, count() 가 for문 1회독보다 훨씬 빠름엄청긴 문자열, 숫자열의 형변환은 그만큼 오래걸림. 그래서 모두 0인것을 검출해야 할때 len()=count() 문법 사용 필요했음.즉, 파이썬은 내장함수가 많은대신 이를 잘 이용해야만 한다. 시간차이가 엄청 크다.def solution(X, Y): answer = '' for i in range(9,..
난이도: Lv.1유형: 수학해결 여부: 정답아이디어배열에서 주어진 숫자 3개의 합으로 나오는 소수의 개수를 구하는 문제이다.조합 계산 후에 정렬하여 가장 큰 값을 기준으로 그 값까지의 소수 리스트를 함수로 만들었다.그래서 소수 개수 리스트가 합 리스트 개수보다 적을 것이라는 것을 이용해 반복문을 돌려 해당 값의 count만큼 답에 추가하게 했다. 오답 이유 혹은 알게 된것itertools에 combinations 사용이 계산을 편리하게 해주었다. 파이썬에 별도의 소수 관련 모듈은 없지만 sqrt를 사용해서 풀었다. from itertools import combinations import mathdef solution(nums): comb = list(combinations(nums,3)) s..
난이도: Lv.1유형: 시뮬레이션해결 여부: 통과아이디어- 2차원 배열 구현해서 드래그의 시작점과 끝점을 최소 최대로 잡는 것이었다.오답 이유 혹은 알게 된것1. 격자점이 칸이아니라 줄 기준이어서 마지막에 1더해주어야 했다.2. 처음에는 max, min 구하는데 특정 값 기준으로 정하고 그러는줄알았는데 아니었다. 그냥 가장 최소, 가장 최대 2차원 배열 각각 구해주면 되는것이었다. 그래서 2차원 배열 막 뒤집는 함수 찾으려고 했는데 풀다보니 필요 없다는 것을 알아냈다. 3. find와 rfind를 잘 써먹었다. 4. sort 안에 sort(key=lambda x: x[1]) 이렇게 key와 lambda 문법으로 효율적으로 정리하는 법을 알게되었다 def solution(wallpaper): answ..
난이도: Lv.2유형: bfs / dfs해결 여부:오답아이디어2차원 리스트에서 인접한 값들의 합을 리스트로 뽑아라 라는 문제다. 문제 자체는 간단하다.. 오답 이유 혹은 알게 된것파이썬으로 bfs 하는 문제에 대한 자각이 없어서 for문으로 아래방향, 오른쪽 방향으로 쭉 돌리면 되겠지 생각했다가 그렇지 않은 모양도 있다는 걸 깨달았다.처음에는 똑같은 2차원 리스트를 하나 더만들어서 방문여부를 확인하려 했다. 근데 그냥 방문하면서 해당 위치를 'X'로 바꾸는게 공간복잡도 적으로도 훨씬 효율적이었다. 2차원 배열의 합은 numpy 모듈사실 문제 자체에 주어진건 1차원 배열이고 그 안의 문자열이라서 따로 처리를 해주어야 했다. 그냥 arr[i][j] 이런식으로 문자열 바꾸려고 하면 에러가 났다. maps = ..
난이도: Lv. 3유형: DP, 수학, 부분합해결 여부: 오답아이디어홀수는 들어올 수 없다. 애초에 0으로 잡아야 한다.짝수가 들어올때 이전에 있던 모양에서 가로 2줄씩 3가지 경우가 붙는다고 봐야 한다.. 하지만 여기에 특수한 형태가 있다. 오답 이유 혹은 알게 된것DP로 접근하는 것 까지는 맞았으나, 이후 점화식에서 틀렸다. f(n)은 항상 f(n-2) 에서 도출되며 3*f(n-2) +2 로 잡았는데 f(n-4) 에서도 도출되는 경우를 생각해야 했다. 만약 하나만 세로로 하고 그 옆을 3줄짜리 가로로 주르륵 채운다면 그건 f(n-2) 에서는 얻을 수 없는 형태가 된다. 그래서 f(n) = 3f(n-2) -> f(n-2) 에서 3칸 붙이기 뿐만 아니라 2f(n-4), 2*f(n-6) ...2f(0) ..
서문학교에서 알고리즘 수업을 듣는데 이해가 안 되는 부분은 GPT가 짠 예시 코드를 보면서 해결했다. 그런데 그 과정에서 GPT는 곧잘 쓰지만 나는 잘 쓰지 않았던 문법들이 있어서 정리해 보았다. 코딩테스트에서 유용하게 쓰일 것이다.자료구조 자료구조 안에 자료형을 명시한다. 자료'구조'와 자료'형'의 차이 때문에 매번 어디에 어떤 게 들어가야 할지 자주 헷갈렸던 문법이다.자료구조 안에 자료형을 명시한다.예를 들어 vector는 정수형 벡터이다.vector> matrix; // 2차원 정수 벡터static_cast이런 자료형은 static_cast로 형을 변환할 수 있다.문법: static_cast(바뀌는 변수명)예:double num = 3.14;int intNum = static_cast(num); ..
이전 내용 [알고리즘] 7. Backtracking1. Brute force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Programming7. Backtracking8. Branch and Bound여기서는 Backtracking에 대해 다룬다. Backtracking이란DFS인데 조건이 있어juneforpay.tistory.com 1. Brute force2. Divide and conquer3. Decrease and conquer4. Transform and conquer5. Greedy Method6. Dynamic Programming7. Backtracking8. B..
