코딩테스트 연습

처음엔 그냥 bfs로 풀려고 했는데 하면 할 수록 조합을 이용해서 푸는게 좋겠다는 생각이 들었다.(완전 탐색 필요)그래서 조합을 이용해서 backtracking으로 풀었다.(python3은 시간초과가 나고 pypy만 통과함)

아기상어가 1칸 상하좌우 이동이길래 맨해튼 거리(|x1−x2|+|y1−y2|)로 풀려고 하다가 2시간이 지나서 잘못되었다는 것을 깨닫고 문제에서 요구하는대로 구현했다.<포인트>1\. 아기상어가 물고기를 먹는 조건과 이동 조건에 맞춰 물고기를 잡아먹는다.2\. 그

자기보다 제일 최근에 작은 수 +1 해준다 -> 반례 (2 3 1 4 5 6)자기보다 작은 수중에 최댓값에 +1 해준다 -> 반례 (4 5 1 2 3)앞에 자기보다 작은 수가 없을 때 1을 해준다 (추가)이중 for문 : n x n = 1000 x 1000 = 1,00

1번부터 친구들과의 관계 점수 매기기제일 작은 점수 뽑기 때문에 최소 점수보다 커지는 순간 cut 해준다(backtracking)for문 n번 x while n번 x for문 n번 = 100 x 100 x 100 = 1,000,000 -> O(n^3)

입력값 A부터 글자수대로 쪼개서(list) P번 반복한다음 다 더해준다.그리고 반복되는 부분 이 생기면 그거 빼고 남는 수 len 출력 -> 그 숫자의 index를 구하면됨map 이용for문 이용

처음에 시작점과 끝점을 받아서 이중 for문으로 색칠해준다.(그림에 있는 칸과 그림이 좌우반전이지만 영역만 구하면 되니까 상관없을듯)bfs로 영역을 구하고 칸 개수를 리스트에 담는다

그냥 하라는대로 구현했다.여러개의 '.'을 '.'하나로 치환하는 부분에서 replace를 생각하긴 했으나 그냥answer.replace('.', '') 를 하면 모든 '.'이 사라져서 어떻게 해야 하나 했는데answer.replace('..', '.') 이렇게 하면 된

처음에 무식하게 이중 for문 돌려서 다 찾았더니 시간초과남투포인터와 이분탐색을 섞어서 두 용액의 합이 음수일때는 음수를 줄여주고, 양수일 때는 양수를 줄여주면서 최솟값을 찾아나간다.O(logN)재귀 이용while문 이용

제일 무거운애가 제일 가벼운애를 태워야한다는게 핵심 아이디어 (나는 생각 못했다)나는 제일 무거운애가 태울 수 있는 애들 중 제일 무거운 애를 태워야 된다고 생각했는데 반대였다. 왜냐하면 제일 무거운애가 태울 수 있는 애들 중 제일 무거운 애를 태울 수 있다면 하나 다

프로그래머스에서 비슷한 문제여서 만만하게 봤는데 온갖 반례에 허덕였다.포인트는 여분의 카약이 있는 팀이 부서졌을 때 자신의 것을 고쳐야 한다는 것!카약을 빌려주는 순서가 있기때문에 정렬을 꼭 해줘야 한다.주의 : remove()로 원소를 빼고 나면 index 순서가 내

그냥 문제에서 구현하라는 대로 구현했다문제가 좀 헷갈림(포인트는 무조건 반시계 90도로 돌린 방향부터 청소할 곳이 있는지 확인하는 것)문제에 1-1, 2-1 이렇게 표시해줬으면 좋겠다O(n \* m)

문제가 하라는대로 했다전형적인 bfs 문제처음부터 익은 토마토가 없으면 바로 -1 출력 (그냥 빈 q를 보내면r, c, day가 비어있어서 UnboundError 난다)익은 토마토 찾는 부분 : 이중 for 문 = O(n\*m) (1,000,000)안익은 토마토 찾는

3차원 배열이라 쫄았는데 그냥 삼중 for문 써서 함삼중 for문 break 헷갈린다(+ 파이썬에서 프로그램을 강제종료하는 메서드 exit()을 알게 되었다)O(h \* n \* m) exit()사용

재귀로 풀기 싫어서 while문 돌려서 했다.그냥 문제에서 구현하라는 대로 했다.빙산 덩어리 계산하는 거랑 각 빙산이 바다에 맞닿아있는 부분 계산 구하는 메서드가 중복될 것 같아서 하나로 합쳤다.빙산 녹이는 부분은 그냥 단순하게 반복문 돌려서 했다.빙산 덩어리가 2개

각 문자열을 돌면서 두 글자씩 끊어서 다중 집합을 만든다(똑같은 로직이라 괜히 한번에 하려고 했는데 예외처리가 안됨)new_str2를 돌면서 원소가 중복되면 합집합을 만들기 위해new_str1에서 제거해주고 교집합 리스트에 추가한다.자카드 유사도(A/B)를 구해준다(반

처음에 물과 고슴도치의 이동 로직을 따로 둔건 한눈에 알아보기 쉽게 하려고 한거였는데 다 짜고 나니 중복도 많고 비효율적으로 짠 것 같다.물이 채워질 공간 먼저 조사하고나서 고슴도치 이동시킨다.처음에 다음에 채워질 칸을 미리 \*(물) 표시를 하려고 했는데 그랬더니다음

백준 탈출을 생각하고 똑같이 구현했는데 예외 처리가 힘들었다. (10번만에 통과한듯) -> 실제 시험에서 테스트케이스없이 통과할 수 있을까? 🥺지훈이와 불을 순서대로 queue에 담는다.bfs를 한다.2-1. 지훈이일 때 이동가능한 곳을 찾고 이동한다 + 방문처리 겸

[백준] 7562번. 나이트의 이동 🐴 바로가기 아이디어 전형적인 bfs!! 근데 범위 잘못해서 틀렸다. 범위 잘 보기!! 시간복잡도 O(i * i) 코드

토마토 문제처럼 삼차원인 전형적인 bfs문제테스트케이스가 여러개일 때 q를 비우지 않아서 문제였다 -> 탈출 함수 지역 변수로 선언해서 해결했다(초기화)O(L\*R\*C)

\[백준] 1600.말이 되고픈 원숭이 🐵 바로가기말로 이동을 먼저한다 -> 안되면 원숭이로 이동한다앞에서 이미 말로 이동할 수 있는 횟수를 다써버리면 말로 도착해야할 때(장애물을 만났을 때) 쓸 수 없는 문제가 생겼다....원숭이로 이동한다.K번을 채울 때까지 말로

\[백준] 11048번. 이동하기 바로가기(0, 0)에서 출발해서 bfs로 갈 수 있는 방향 사탕 더해준다.방문처리 하지 않는다. 어떤 경로로 와야 최댓값인지 모르니까(N, M)에 도착할 때 안멈추고 사탕의 수를 리스트에 다 넣어서 최댓값을 찾는다.메모리 초과dp\[r

그냥 반복문 돌렸더니 시간초과 났다앞으로 약수 구하는 건 무조건 int((n \*\* 0.5) + 1)까지라고 기억하기! ⭐⭐⚠️ 25같이 약수가 중복되는 것 주의하기! O(n \*\* 0.5)

\[프로그래머스] 택배상자 바로가기stack쓰는 건 알았는데 구현을 못했다... 🥲O(n\*\*2)

\[프로그래머스] 다리를 지나는 트럭 바로가기다리길이만큼 deque을 만들어서 트럭이 한 칸씩 왼쪽(←) 방향으로 움직인다.예를 들어한 칸씩 왼쪽으로 이동하는 것을 어떻게 구현해야 될지 모르겠었다. \-> 그냥 \[0, 0] 에서 0번째 값을 빼준다. (popleft

\[프로그래머스] 프로세스 바로가기자신보다 높은 우선순위가 있는지 확인하기 위해 우선순위가 높은 순서대로 정렬한 리스트를 이용했다 💡O(N)

\[백준] 2493번. 탑 🗼처음엔 그냥 내 다음번에 나오는 나보다 큰 탑이 나올때까지 반복문을 돌렸는데 시간초과 났다..stack을 이용해서 푸는 전형적인 문제였다..... 아직 내 수준에서 생각해내진 못할 것 같다.... 🤯stack을 리스트로 사용하지말고 de

\[프로그래머스] 기능개발 바로가기for문 돌면서 각자의 작업량을 더해준다.하루의 마지막에 배포하니까 작업 후에 완성된 기능을 검사한다.완성한 작업을 다 배포할 동안 while문 반복한다.배포한 작업 개수를 answer에 담는다O(N^2)

\[백준] 5427번. 불 🔥🔥 바로가기저번에 풀었던 불!과 같은 아이디어로 풀었다.상근이가 먼저 이동불이 이동가장자리에 오면 탈출예외처리를 따로 해주지않고도 처리할 수 있는 방법을 찾아서 했는데 시간은 더 오래걸린다. 아예 상근이 위치를 찾을 때 가장자리에 있으면

\[백준] 6198번. 옥상 정원 꾸미기 바로가기저번에 풀었던 탑의 아이디어 처럼 풀었는데 안 되서 답봤다.. 🥲아직 스택에 대해서 잘 모르고 있는 것 같다 ⭐찾아보니 이렇게 푸는게 monotone stack이라는 알고리즘이었다.for문을 돌면서 자기 자신을 볼 수

\[백준] 17298번. 오큰수 바로가기monotone stack으로 스스로 푼 첫 문제 🤓자신보다 큰 수 중에서 가장 가까이(왼쪽)에 있는 수를 찾는 것수열을 거꾸로 뒤집어서 검사한다첫 숫자는 비교 대상이 없기 때문에 stack에 담는다이후 현재 숫자와 stack의

[백준] 28278번. 스택 2 바로가기 아이디어 문제에서 하라는 대로 구현하면 됨 > 1 X: 정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000) 2: 스택에 정수가 있다면 맨 위의 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다. 3: 스택에 들어있는 정

\[백준] 9935번. 문자열폭발 바로가기처음 아이디어는 for문을 돌면서 문자열이 같은지 체크하는 방식이었다.하다가 stack문제임을 깨닫고 stack에 넣어서 검사하는 방식으로 바꿨다.stack에 넣은 글자가 폭발 문자열의 마지막 문자와 같으면 검사를 시작for문으

\[백준] 17144번. 미세먼지 안녕! 바로가기로봇 청소기는 항상 1번 열에 있다 -> 문제를 잘 읽자!!1번 미세먼지 확산을 했는데 2번 공기청정기 작동은 아이디어가 안떠올랐다.어렵다..................🤯🥲😵그냥 q에 이동하는 위치를 넣었는데 공기

\[코드트리] 2048(Easy) 바로가기모든 방향으로 다 더해본다 -> DFSdfs로 0번부터 시작up방향으로 더해준다 -> 복사해주는 것이 중요up방향으로 5번 더해주고나서 최댓값을 구한다.board를 90도 회전시킨다. -> 복사해주는 것이 중요2-4를 반복한다.

\[백준] 21609번. 상어 중학교 🦈 바로가기블록그룹 만들어서 가장 큰 블록그룹 제거하기중력 작용 시키기💡 빈 칸을 카운트해서 행에 더해준다!반시계방향으로 90도 회전 시키기 💡 암기하자90도 반시계방향 회전 : temp\[n - 1 - y]\[x] = boa

백준의 주사위 굴리기가 도움이 많이 되었다 💡주사위 굴리기 + bfs + 예외 처리그냥 왜 틀렸는지 모르겠으면 처음부터 천천히 다시 짜는 것도 나쁘지 않을듯.... 생각보다 오타 찾기가 쉽지 않다................. 🤯😵🥲move_dice()에서 값을