프로그래머스/BFS, DFS (7) 썸네일형 리스트형 [DFS] 프로그래머스 '무인도 여행' - js 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/154540#qna 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 구현 처음 푼 코드) 부분 정답 2차원 배열을 만들어주고 값이 X가 아니면 1을 넣어준 뒤, 상하좌우 요소 중 값이 1인게 하나라도 있으면 기존 값에 더해주고 없으면 이전 합을 더하고 temp에 새로운 값을 넣어주는 식으로 짰는데 부분 정답이 나왔다 ㅠㅠ 반례라도 있으면 문제를 파악하기 더 쉬울텐데, 어떤 부분이 틀렸는지 이해가 안된다 ㅠㅠ 복기하다 보니 내 풀이가 왜 틀.. [DFS] 프로그래머스 '여행경로' - js 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43164#qna 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 코드 처음 푼 코드) 처음에는 BFS를 사용하여 풀었고, 결과는 부분 통과였다. 이유는 '사전 순'이라는 조건만 구현해 주었기 때문이다. 이 문제의 주의할 점은 모든 공항을 방문해야 한다는 것이다! 그래서 이 문제는 BFS가 아니라 DFS로 푸는 문제였던 것이다. 만약, [["ICN", "a"], ["ICN", "b"], ["b", "ICN"]] 같은 경우에는 a에 먼저 가.. [BFS] 프로그래머스 '단어 변환' - js 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 코드 이 문제는 최소 단계를 반환하는 문제이기도 하고, 이미 방문한 단어는 또 방문할 필요가 없기 때문에 BFS로 풀어야 한다. 어떻게 해야 최소 단계를 반환할 수 있느냐?! 큐를 사용한다 => 단어 한 개만 다른 경우 큐에 넣는다 => 큐에 들어간 순서대로 처리 되므로 최소 단계 반환 가능! 여기선 선 증감 후 할당이 되는 ++cnt가 핵심이다. cnt++로 바꾸면 선 할당 후 .. [BFS] 프로그래머스 '게임 맵 최단거리' - js 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/1844 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 코드 알고린이 울어유,,, 이게 어떻게 레벨2야!?!! 꼭 복기해야겠다.. 이 문제는 bfs로 풀어야겠다고 생각만하고 풀이 과정은 못찾은 문제..^^ 근데 익숙해지면 이런 류의 최단거리 문제는 잘 풀 수 있을 것 같기도하고(허언증)! bfs는 큐 또는 연결리스트로 구현한다는 것도 잊지말자. 로직 자체는 막 어려워서 이해가 안되는 건 아닌데, 처음부터 혼자 짜기에는 어려운 것 같다. .. [DFS] 프로그래머스 '네트워크' - js 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43162?language=javascript 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 코드 https://bbeeyaks-moment.tistory.com/entry/%EC%99%84%EC%A0%84%ED%83%90%EC%83%89-%ED%8A%B8%EB%A6%AC-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EC%A0%84%EB%A0%A5%EB%A7%9D%EC%9D%84-%.. [DFS] 프로그래머스 '타겟 넘버' - js 1. 문제 https://school.programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 2. 코드 DFS의 기본은 재귀(피보나치 수열 생각하기)다! 문자열을 계속 이어붙히거나, 순서들을 나열할 때는 for문을 사용하지만, 이 문제처럼 단순히 총 합을 target과 비교하는 것이면 for문을 사용할 필요가 없다. 기본 재귀 개념 사용하자! 무조건 for문을 써야한다는 틀에 박혀 한시간을 헤맸다... 그리고 또 하나 중요한 것! 엣지케이스를 정확하게 작성하자. 재귀에서 스택 .. DFS/BFS?! DFS/BFS? DFS는 한 놈만 팬다 !! -> 쉬운 문제에 사용(시간 복잡도 고려하여) BFS는 여기저기 껄떡거리면서 팬다 -> 시간 복잡도(휴율성) 고려해야할 곳에 사용, DFS로 안풀리는 복잡한 문제에서 사용 매 코딩 테스트에 한 문제씩은 나온다. 잘 준비하기! 대표유형 경로탐색, 네트워크, 조합 만들기 구현 방법?! DFS : 재귀함수 또는 for 문 BFS : 큐 또는 연결리스트 https://www.youtube.com/watch?v=BsYbdUnKZ-Y 이전 1 다음
