레벨업 일지

문제 https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알아야 할 개념 차원 축소 풀이 두시간 넘게 고민하고 프로그래머스의 질문하기 란을 참고하여 작성했다. 2차원 행렬에서 네모 박스 범위의 값을 효과적으로 구하는 풀이법이어서 감탄했던 문제. 문제에서 주어진 공격 정보를 3중 for문으로 나이브하게 탐색하면 worst case 에서 시간 초과가 난다. (배열의 최대 길이 ) x ( skill의 최대 길이 ) = 1000 * 1000 * 250,0..

문제 https://leetcode.com/problems/find-the-town-judge/description/ Find the Town Judge - LeetCode Find the Town Judge - In a town, there are n people labeled from 1 to n. There is a rumor that one of these people is secretly the town judge. If the town judge exists, then: 1. The town judge trusts nobody. 2. Everybody (except for the town judge) trusts leetcode.com 모든 사람의 신뢰를 받고, 그 자신은 아무도 믿지 않는 유..

문제 11058번: 크리보드 (acmicpc.net) 11058번: 크리보드 N = 3인 경우에 A, A, A를 눌러 A 3개를 출력할 수 있다. N = 7인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V를 눌러 9개를 출력할 수 있다. N = 11인 경우에는 A, A, A, Ctrl-A, Ctrl-C, Ctrl-V, Ctrl-V, Ctrl-A, Ctrl-C, Ctrl www.acmicpc.net 알아야 할 개념 점화식 dp 풀이 버튼 4가지의 역할은 다음과 같다. A를 출력 전체 선택 선택 영역 복사 붙여넣기 알수 있는 규칙은 단순히 A를 추가하면 현재 길이 + 1 가 되고 , 붙여넣기를 하면 현재 단계 i 에서 3번째 전 단계의 것을 가져와서 붙여넣기를 한다. 붙여넣..

문제 LeetCode - The World's Leading Online Programming Learning Platform Sudoku Solver - LeetCode Sudoku Solver - Write a program to solve a Sudoku puzzle by filling the empty cells. A sudoku solution must satisfy all of the following rules: 1. Each of the digits 1-9 must occur exactly once in each row. 2. Each of the digits 1-9 must occur exactly once leetcode.com 알아야 할 개념 brute force 구현 재귀 함수 풀이..

문제 https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/description/ Binary Tree Zigzag Level Order Traversal - LeetCode Binary Tree Zigzag Level Order Traversal - Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between). Example 1: [https://assets leetc..

문제 요약 총 4문제가 나왔다. 1번 문제 : 조건에 따라 배열로 작성하면 되는 문제 2번 문제 : 체스 이동 하는 DFS 문제 였는데, 이동 조건이 생소했다. 3번 문제 : DP 인데 이건 아직 부족해서 패스 4번 문제 : 최적화된 풀이법이 생각나지 않아 나이브하게 접근하다 시간 종료 총평 체감 난이도는 프로그래머스 lv 1 ~ lv 5 골고루 한문제씩 나온 듯하다.1 , 2번은 건드려 보고 4번 문제를 풀다가 인덱스 에러를 손보다 시간이 다 돼서 시험종료됐다. 기업에서 요구하는 pccp 정도가 LV 3 이라는데, 오늘 시험 분위기를 보아하니 4문제 모두 테케 통과할 정도로 건드려야 나오는 점수이다. 느낀점 lv 4, 5문제들은 손이 잘 안갔는데 이번기회로 일주일에 두문제 정도는 꾸준히 봐야겠다고 생각..

문제 https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net 알아야 할 개념 dfs 백트래킹 코드 dfs 탐색시 주의점을 알려준 문제 예제에 사이클 그래프가 보여서 난이도가 높은줄 알고 당황했었다. 해당 문제는 모든 정점에서 dfs 를 돌리는것으로 간단히 풀이 가능하다. 풀이는 다음과 같다. 주어진 그래프를 무방향 인접 그래프로 구현한다. 모든 정점에대해 DFS 탐색을 한다. DFS 탐색 깊이가 4 ( 시작 = 0 ) 이상이면 탐색을 종료하고 1 리턴한다. 그렇지 않으면 0 리턴한다. 백트래킹을 연습하는 문제라고 생각한다. 플래그를 세워서 dfs 탐색 종료..

문제 https://school.programmers.co.kr/learn/courses/15008/lessons/121685 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알아야 할 개념 재귀함수 호출 dfs 풀이 재귀 함수 dfs 탐색을 주어진 조건을 고려했을때, 탐색 레벨의 최대값은 16이다. bfs로 주어진 index까지 브르투 포스 하면 4억번 이상의 연산으로 tle 를 마주하게 된다 특정 위치만 찾는법은 없을까? 라는 생각이 들었다. 풀이는 다음과 같다. 우선 주어진 조건을 재귀함수로 받는다. Level이 1이면 "Rr" 리턴. Level이 2..