스키장 갔다와서 오랜만에 릿코드 풀이! 확실히 여행 다녀오니까 머리가 잘 돌아간다 https://leetcode.com/problems/word-search/?envType=study-plan-v2&envId=top-interview-150 Word Search - LeetCode Can you solve this real interview question? Word Search - Given an m x n grid of characters board and a string word, return true if word exists in the grid. The word can be constructed from letters of sequentially adjacent cells, where adja..
dfs
https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 와 ~~ 상당히 어려운 재귀인 것 같다 문제를 읽어봤을 때 얻을 수 있는 힌트는 간단하다. 프로젝트 팀이 형성되는 경우는 그래프 구조에서 cycle이 형성되는 상태이다. 따라서 cycle 을 형성하기 위하여 node 들이 이어져있는 관계를 파악해야 한다. 예를 들어서 문제 예시에서 팀을 이루는 (4, 7, 6) 을 살펴보자. 1. visited node 4를 아직 방문하지 않았으므로 4에 대해 방문처리..
https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 네트워크 덩어리를 찾을 때마다 dfs가 실행되고 그래프 탐색이 종료되면 그 네트워크 덩어리의 탐색이 끝났다는 것이다. 즉, dfs가 몇번 실행되는지 카운트 해주면 된다. 생각할 점은 인접그래프 형태로 computers 2차원 배열이 주어진다는 것이다. def solution(n, computers): answer = 0 visited = [False] * n def dfs(start): visit..
https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr dfs로 풀어야 겠다고 떠올렸다 그런데 보통 입력이 숫자로 주어졌고, 나는 그래프를 표현할 때 주로 이차원 리스트를 사용했는데 각각의 node에 해당하는 공항 이름들이 문자열이다보니, 처리를 쉽게 하기 위해서는 dictionary 자료형이 낫다고 생각했다. 내가 좋아하는.. 쓰기 편한 defaultdict으로 초기화 없이 우선 정의해주고, for 문에서 각각 그래프와, visited 딕셔너리에 F..
백트래킹 문제로 되게 유명하다면서/!??! 그래서 풀어봤다 백트래킹 유형중에 백준에서 푼사람이 가장 많은 문제이기도 하다 백트래킹이란 ? 해를 찾는 도중에 해당 노드가 해가 아니라서 막히면 되돌아가서 다시 해를 찾아가는 기법이다. 첫번째 풀이는 시간초과가 났다 dfs로 퀸을 배치하고, 배치한다음에 시뮬레이션 돌려서 퀸을 공격할 수 있는지 없는지 여부를 true , false 로 반환해서 true 값을 세려고 했다 시간 초과 판정이 떴다. 퀸을 배치하는 과정에서 조금 더 개선해볼 수 있지 않을까 ??? # 9663 N-Queen n = int(input()) graph = [[0]*n for _ in range(n)] dx = [-1, 1, 0, 0, -1, -1, 1, 1] dy = [0, 0, -1, ..
https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net DFS로 풀이했다. 나 근데 가로 세로가 아직 헷갈린다;; 아이디어는 다음과 같다. n = 7, m = 5 사이즈의 2차원 배열 (= 그래프) 가 있다고 생각하면, 각 칸을 모두 0으로 초기화 시킨다 입력되는 직사각형 부분에 해당하는 칸들은 2차원 배열에서 1로 표시한다. 1은 이미 방문된 노드라는 의미이다. 그후 전체 2차원 배열을 이중 for문으로 하나씩 칸의 값을 체크하면..
https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 문제 유형 : 구현 + dfs 문제집에는 dfs로 분류되어 있었는데 구현 유형스러웠던 문제 ㅋㅋ 1. 벽을 설치한다 3개까지 -> board 2차원 배열 돌면서 board[i][j] == 0 이면 벽 설치 가능 2. 3개 다 설치했으면 바이러스를 퍼뜨려 본다. 바이러스 퍼뜨릴 때 재귀호출해서 상하좌우 이동한다. 3. 바이러스를 퍼뜨린 후 안전지대를 계산한다.그리고 원래 가지고 있던 최대 안전지대 값이랑 비교하..
