개발자 노트

문제설명 스택 및 이차원배열을 물어보는 문제 접근 바구니는 단순히 stack만을 이용하면 되고, 이차원 배열에서 뽑을 인형을 잘 두는게 포인트. 이차원 배열도 세로로 스택으로 보기 위해 각열에서 top을 미리 찾은 다음 뽑을 때마다 +1 씩 해주는 방식으로 접근했다. 왜냐하면 아래로 갈 수록 값이 증가하니까.(이 부분에서 디버깅하는데 10분 소요했다. (전체 풀이시간 30분)) 구현 def solution(board, moves): n = len(board) tops = [0 for _ in range(n)] #값이 있는 index for c in range(n): for r in range(n): if board[r][c] != 0: tops[c] = r break answer = 0 basket = ..

문제설명 https://programmers.co.kr/learn/courses/30/lessons/64063 문제 이해하는 것은 쉬운 편이나 어떻게 접근할 것인지 결정하는게 어려운 문제 1번방에 배정받은 사람이 있고 1번 방을 배정받기 원한다면 2번방을 배정해줘야 한다. 2번방에도 사람이 있다면 다음 사람이 없는 방인 3번방으로 배정. 예외도 없다. 방이 모두 5개있고 5번방을 2번 요청하는 경우는 input으로 주어지지 않는다고 적혀있다. 접근 1.UnionFind 딱 UnionFind가 생각나는 문제. 1~3번방에 사람이 있다면 결국 하나의 그룹을 이룬다고 생각할 수 있다. 그 이유는 1) 문제의 목표는 번호 x가 주어질 때 다음 방 배정을 찾는 것이다. 2) 번호가 1,2,3일 때 다음 방 배정은..

문제설명 구현문제이다. 구현문제는 늘 그렇듯 글을 잘 읽는게 중요하다. 접근 M과 N을 보면 시행횟수가 적다. 회전하는 경우까지 포함하면 대략 M*N*4(roate수)가 된다. 완전탐색을 적용하면 편하다. 초기 완전탐색 접근 방법은 이렇다. 접근1. DFS를 통한 완전탐색 매 단계 rotate할 건지 이동할 건지 선택.(이때 이동은 이동을 1칸씩 이동으로 정의) 해당 케이스가 자물쇠를 열 수 없다면 계속 탐색 baseCase는 rotate4번 다 돌았을 때 또는 이동 범위를 벗어났을 때이다. 이를 DFS로 구현한다. 이렇게 하니까 매단계 rotate구현하는게 너무 빡쎘다. 그리고 이렇게 짜면 비효율적이란 감이 들었다. 따라서 rotate 1회전 후 r,c모두 탐색, 2회전후 r,c 모두 탐색으로 접근하려..

문제 설명 간단히 말하여 net의 수를 구하는 문제이다. 이와 유사한 문제는 삼성 코딩테스트, 백준의 컴퓨터 네트워크 수 구하기, 크루스칼 알고리즘 등에서 보이듯, 기본문제이다. 주어진 그래프의 자료형은 인접행렬(2차원 행렬)으로 주어졌고 무방향 그래프이다. 문제 접근 Union Find 한 그래프와 다른 한 그래프의 노드를 비교하여 서로 다른 그래프에 속해있다면 합쳐준다. 같은 그래프에 속해있는지 판단하는 방법은 서로의 루트노드가 같은지 비교하면 된다. BFS,DFS 깊이우선 탐색. 모든 노드에 대해 방문했는지 체크해주는 visited 리스트 or 비트를 구현하고 한 노드에 대해 탐색 후 탐색이 안된 노드를 찾아 탐색해주면 된다. 탐색이 안된 노드를 찾아 탐색하는 횟수가 곧 그래프의 수. 왜냐하면 DF..