이숭간 공부기록

https://programmers.co.kr/learn/courses/30/lessons/64064 코딩테스트 연습 - 불량 사용자 개발팀 내에서 이벤트 개발을 담당하고 있는 "무지"는 최근 진행된 카카오이모티콘 이벤트에 비정상적인 방법으로 당첨을 시도한 응모자들을 발견하였습니다. 이런 응모자들을 따로 모아 불량 programmers.co.kr 문제유형 : 잘모르겠다.. 나는 DFS로 풀긴햇답 문제풀이 : DFS 과정 DFS를 하면서 depth를 저장하면서 진행한다. depth가 끝까지 도달했다면 현재경로까지 추가된 노드들을 copy해서 전역변수에 저장하고 리턴한다. dfs를 재귀호출하는 다음부분에 현재경로에서 현재노드(마지막노드)를 제거한다. 그다음 dfs를 호출하면 이전까지의 경로는 그대로 있고 마..

https://programmers.co.kr/learn/courses/30/lessons/43164 코딩테스트 연습 - 여행경로 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] programmers.co.kr 문제유형 : DFS 문제풀이 : 하나의 여행지를 노드로 보지않고 하나의 PATH(출발지~도착지)를 하나의 노드로 보고 풀었다. 전형적인 DFS문제이면서 살짝의 변형이 있는 문제이다. ICN ~ @@@ 인 노드를 시작노드로 하여 DFS를 진행한다. DFS의 depth가 tickets길이-1 이면 전체 항공권을 모두 사용한것이 되므..

https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제유형 : DFS/BFS 문제풀이 DFS의 경로상에 순서가 있는경우 (a-b-c 와 a-c-b가 다른경우!!) dfs의 재귀호출이 리턴되는 지점에서 방문처리를 다시 풀어줘야한다 단어가 하나의 노드가되고 차이가 1인 노드끼리 연결되있다고 생각한다. 현재노드로부터 차이가 1인 노드들을 순차적으로 방문탐색하면서 target..

https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제유형 : DFS/BFS 문제풀이 : 전형적인 DFS(BFS)문제로 "연결된 덩어리들이 몇개냐" 구하는 문제 DFS를 통해 노드들을 방문하는데, 자기자신이 아니면서 연결된 노드가 있을때, 해당노드가 아직 방문 전이면 재귀적으로 해당노드를 출발점으로 하여 DFS를 호출한다. 더이상 연결된 노드들이 없을때 DFS의 재귀가 끝나므로 그때 answer에 1을 추..

https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+ programmers.co.kr 문제유형 : DFS/BFS 문제풀이 아래 사진처럼 각 노드들은 결과값을 담고있고, 엣지에 각각 +,- 가 붙은 numbers의 원소가 붙게된다. 최종적으로 numbers끝까지 계산이 완료됬을경우, 즉 count가 len(numbers)인경우에 해당 노드값 (result)가 target과 같으면 원하는 결과값을..

https://www.acmicpc.net/problem/16234 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 문제유형 : 구현, 그래프탐색 (삼성기출) 문제풀이 BFS(DFS도 가능)를 통해 연합가능한 국가를 찾도록 한다. 전체국가를 돌면서 bfs로 연합가능한 국가의덩어리들을 찾고 각 덩어리들사이에서 인구이동을 진행한다. 모든칸(전체국가)을 돌았는데 인구이동이 한번도 없었다면 더이상 진행이 불가한것을 의미하므로 while문을 break하고 빠져나온다. 인구이동이 있었다면, 다시 visite..