본문 바로가기

Coding Test33

[ 프로그래머스 ] LV.2 짝지어 제거하기 // 문제요약 문자열 s 가 주어지면 짝이 맞는 문자 한 쌍을 제거하고 앞뒤로 남은 문자들을 다시 붙이는 작업을 반복할때 모든 문자를 없앨 수 있다면 1 그렇지 않다면 0을 반환하는 함수를 완성해라. // 사고 특정한 페턴을 추출/제거하는 방식중에서 stack의 선입후출 LIFO의 특성을 이용하는 전형적인 문제다. 보여지는 대로... 선입선출은 먼저 들어간 것이 먼저 나오는 것이고 선입후출은 먼저 들어간 것이 나중에 나오는 것이다. 편의점 알바를 해보면 저 둘의 차이를 확실히 알것이다. 사장님은 선입선출로 정리하라고 하고 손님들은 선입후출로 사가려고 한다... 아무튼 문제를 많이 풀어보면 어느 순간 자동으로 스택이라는 것을 직감하게 되는 전형적인 문제다. 페턴을 외워두는 것도 나쁘지 않다. // 풀이 원.. 2021. 7. 22.

[ 프로그래머스 ] LV.2 가장 큰 정사각형 찾기 // 문제 요약 0과 1이 채워진 2차원의 행렬이 주어지면 1로 만들 수 있는 정사각형중에 가장 큰 정사각형의 넓이를 구하여라 // 사고 기본적으로 생각할 수 있는 풀이는 DFS나 BFS다 그러나 효율성 문제를 보는 점이나 LV.2 인 것을 감안하면 DFS / BFS 가 아닐 가능성을 생각해야한다. 이 문제의 풀이는 greedy로 푸는 것이다. 정사각형을 구성하는 가장 작은 단위는 2x2 정사각형이다. 이 단위정사각형을 필터로 하여 훑으면서 지나가는데 모든 값은 0과 1로 주어지므로 단위 정사각형이 구성될 경우 정사각형 내의 값을 아무리 크게 업데이트 해줘도 움직인 필터에서 구성되지 않을 경우의 minimum값은 여전히 0이다. 이 성질을 이용해서 누적해가면서 정사각형이 구성되는 경우를 구하면 된다. 코.. 2021. 6. 23.

[ 백준 ] 2630 색종이 만들기 파이썬python 풀이 // 문제 요약 위와 같이 절반씩 나누어서 만들 수 있는 가장 큰 정사각형 종이를 원할때 얻을 수 있는 종이 중에서 파란색과 흰색의 수는 각각 몇장씩인지 출력하여라 // 사고 분할 정복을 사실상 한번도 구현해보지 않은 상태에서 만난 문제 처음에는 종이를 나눈 횟수에 따라 정사각형의 시작점과 끝점을 구하고 그 안에서 탐색을 다시 하는 함수를 탑다운으로 짜고 있었는데 짜면서 바로 아 이방법으로는 안되겠다 하는 부분이 너무 많아서 그냥 풀이를 바로 찾아봤다. 이 풀이는 분할정복 중에서도 4개로 나뉘는 방식이라 하여 쿼드트리 방식이라고 한다. 코드를 보자. // 풀이 https://url.kr/1zmqlt hyun06000/coding_test_study_with_python It is a coding test.. 2021. 6. 23.

[ 프로그래머스 ] 110 옮기기 파이썬python 풀이 // 문제요약 0과 1로 이루어진 문자열이 하나 이상 주어지면 각 문자열의 부분 문자열 중 110에 해당하는 부분을 추출하여 위치를 바꾸는 과정을 거친다고 할때 사전 순서에서 가장 앞서는 문자열들을 찾아 반환하여라 // 사고 '사전순서'라하면 dfs가 번뜩 떠올랐지만 주어지는 문자열의 길이가 어마어마해서 다른 방식으로 접근해야한다고 생각했다. 만약 다른 문제에서 '사전순서'를 미리 만나지 못했다면 문제를 이해 하는데만 엄청 오래 걸렸을 것이다. 그래도 조금씩 성장하는 모양이다. 110 의 경우는 이미 사전순서로 배열이 잘 이루어진 문자열이므로 0을 만나면 그 0의 뒤에 1을 만나면 그 1의 앞에 위치시켜 주면 해결될 일이었다. 문제는 111100 이런 문자열의 경우 11 [ 110 ] 0 이렇게 추출 후.. 2021. 6. 16.

[ Baekjoon 백준 ] # 7569 번 Python 풀이 // 문제 요약 토마토를 3차원 격자에 배치한다. 익은 것, 안 익은 것, 빈 칸 이렇게 세 종류의 칸이 존재한다. 익은 토마토의 대각선 방향을 제외한 이웃한 칸에 안 익은 토마토가 있을 경우 하루가 지나면 익은 토마토로 바뀐다고 할때 토마토가 다 익는데 걸리는 최소 일자를 구해라 단 모든 토마토가 익을 수 없다면 -1을 처음부터 모두 익어있다면 0을 출력해라. // 사고 3차원에 덜컥 겁을 먹었는데 알고보니 원래 2차원 문제였던걸 확장한 문제여서 2차원 문제 풀었던 사람들은 쉽게 접근을 했던 문제였다. 역시 코테는 문제를 얼마나 풀어보느냐가 절반은 먹고 들어간다. 아무튼 시간이 많이 걸리겠다 생각이 들어서 백트래킹을 생각할 수 있는데 백트래킹은 DFS 이므로 하루에 이웃한 한 칸만 전염시키는 조건에 맞.. 2021. 6. 14.

[ 프로그래머스 ] N-Queen 파이썬python 풀이 // 문제 요약 자연수 n 이 주어질때 n x n 의 채스판에서 n개의 퀸이 서로를 공격할 수 없도록 위치시킬 수 있는 경우의 수를 모두 구해라. // 풀이 dfs 중에서도 백트래킹 문제다. 사실은 "모든 경우의 수" 문제이므로 브루트 포스이긴 한데 이후의 사건이 이전의 사건에 종속적이므로 조건문을 통해 가지를 치는 것이 가능하다. 이런 문제가 가장 어려운 부분은 여러 겹의 for문으로 브루트 포스로 설계할 것인가? 수학적 접근으로 n에 대한 규칙을 찾을 것인가? 재귀 함수를 통해 백트래킹을 할 것인가? 이 선택을 순간적으로 하기 어렵다는 것이다. n이 작으니 브루트 포스도 그럴싸해 보이고 그림을 그려보면 묘하게 페턴도 있어 보이며 백트래킹을 잘 쓰면 굉장히 섹시한 답을 제출할 수도 있어 보인다. 이럴 .. 2021. 6. 7.

이전 1 2 3 4 5 6 다음

티스토리툴바