링크: https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어 백트래킹사용 for문을 돌며 숫자를 선택 방문여부를 확인하며 돌고 다시 이전 깊이로 돌아갈 때 방문여부를 되돌려줘야함 M개의 숫자를 고른 경우의 경로는 print해준다. 시간복잡조 중복을 허용하지 않은 경우니 N!이다 -> 가능! 구현 import sys # 백트래킹 구현 def back(): # 경로를 찾았을 때 출력 if len(check) == m: for i in chec..
백트래킹? 트리방식으로 동작된다고 이해하면 쉽다. 재귀함수를 통해 for문을 돌려 깊이를 마음대로 설정할 수 있음. DFS랑 백트래킹 뭐가 달라? 재귀함수를 통한 dfs랑 백트래킹이 유사하지 않나?라는 생각이 들었다. 둘 다 탐색이지만 원하는 값을 찾기 위한 방법에서 차이가 발생한다. 백트래킹은 불필요한 탐색을 하지 않는다. 경로를 찾아가는 도중에 해가 되지 않을 것 같은 경로에 왔다면 더 가지 않고 되돌아온다. 아래 사진을 보면 느낌이 팍 올 것이다. 되돌아올 때 밑에 노드는 애초 방문하지 않은 것처럼. dfs의 방문처리는 보통 배열을 사용하여 인덱스를 활용한 방문처리를 한다. 하지만 백트래킹은 다시 부모노드로 올라갈 때 이전의 노드들을 방문했다고 생각하지도 않고 진행한다. 그래서 보통 append()..
링크: https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 아이디어 큐를 이용한 BFS 재귀를 이용한 DFS 방문처리 배열 하나로 두 번 사 구현(틀림) import sys from collections import deque #dfs def dfs(v): dfs_li.append(v) for i in range(n): if m_li[i][0] == v and not check[m_li[i][1]]: check..
레포지토리(repository) 레포지토리는 깃에서 폴더/디렉터리랑 동일하다. .git 디렉터리가 있는 디렉터리를 repository라 부른다. 프로젝트 하나당 하나의 레포가 아닌 여라 개가 있을 수 있고(큰 프로젝트) 작은 프로젝트는 하나의 레포만 있는 경우가 있긴 하다. (모노리포) repository 복제 git clone 주소 '분산'버전관리 시스템으로 클론해온 레포는 막 써도 원본이 망가지지 않음 커밋 로그 확인 vs코드의 gitgraph 확장프로그램 설치 후 눈으로 확인가능 git log gitk 위 두 명령어도 있간 한데 잘 안 쓴다고 함 실행취소/과거 시점으로 돌아가기 커밋 체크하웃하기 git checkout 커밋아이디 커밋아이디는 커밋 로그를 통해 알아내어 위 코드를 입력 그럼 detac..
공부를 시작하며.. 나는 지금까지 Git과 GitHub을 간단한 프로젝트 파일 저장용도로만 사용해 왔다. 옛날부터 Git과 GitHub이 버전 관리와 이슈 트래킹과 같은 기능을 제공한다는 것은 알고 있었지만, 주변 사람 중에서 이를 열심히 활용하는 사람을 찾기 어려워서 그 중요성을 완전히 깨닫지 못했었다. 그래서 "나중에 제대로 공부해 봐야지"라고만 생각하며 미루고 있었다. 그런데 최근 해커톤 프로젝트를 진행하면서 주변을 둘러보니, 나처럼 Git을 단순한 저장소로만 사용하는 팀이 거의 없다는 것을 보게되었고, 더 어리고 경험이 적은 친구들조차 Git과 GitHub을 체계적으로 활용하는 모습을 보고, 나도 더 이상 미루면 안 된다고 판단했다. 그래서 지금부터 바로 git과 github에 대한 기본적인 부분..
링크: https://school.programmers.co.kr/learn/courses/30/lessons/43162 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 뭔가 말이 헷갈리긴 하는데 쉽게 보면 그래프 탐색인 듯 방문처리 배열 만들고 각 요소마다 bfs를 진행 bfs가 진행될 때마다 count변수 +1 구현 def solution(n, computers): global chk answer = 0 chk = [False]*n for i in range(n): if not chk[i]: chk[i] = True answer += 1 dfs..
링크: https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 아이디어 dfs bfs 뭘 사용해도 될 듯? dfs를 이용해서 풀어보자 (재귀) ICN부터 dfs탐색 시작 알파벳 순 판별은 대소비교를 통해 진행 지나간 경로는 del 구현(실패) def solution(tickets): # 경로를 저장할 배열 global road road = ["ICN"] # ICN부터 시작 dfs("ICN", tickets) return road # dfs 함수 def..
평소에는 DFS, BFS 둘 중 뭘 써도 풀리는 문제들만 풀었어서 차이점(효율적인 측면)을 명확하게 잘 몰랐다. 그렇게 오늘도 알고리즘 문제를 풀다 갑자기 이 DFS BFS 적용 기준 정리에 필요성을 느껴 바로 실행에 옮기려 한다. BFS, DFS가 뭐야? 내가 알고있는 bfs, dfs는 그래프를 탐색하는 방법으로 알 고 있다. 각 dfs bfs에 대해 간단히 적어보겠다. BFS(너비 우선 탐색) 큐를 사용함 정점에서 가까운 노드들부터 탐색 찾는 노드가 인접할 때 유리 노드가 많을 수록 메모리를 많이 소비 DFS(깊이 우선 탐색) 스택 혹은 재위함수를 사용함 정점에서 가장 깊은 노드까지 들어가며 탐색 그래프의 깊이(depth)가 깊을 수록 빠름 메모리가 적음 언제 뭐 써야해? 공통 단순히 모든 정점을 방..
링크: https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여www.acmicpc.net아이디어바로 보자마자 bfs로도 풀 수 있을 것 같음근데 dfs를 연습하기 위해 dfs를 사용2중 for문을 통해 방문처리를 확인하고 dfs진행dfs는 재귀를 사용각 영역마다 each변수로 크기 표현구현import sys input = sys.stdin.readline n = int(input()) danzi = [list(map(int, input().strip())) for _ in range..
