차곡차곡

https://www.acmicpc.net/problem/9663 해당 풀이는 Python 으로 제출시에도 시간초과가 발생하지 않습니다. 초기 아이디어처음에 문제를 풀 때는 2차원 배열을 사용하여 체스판을 표현한 후, 백트래킹을 이용해 각 칸에 퀸을 배치했다. 결과는 당연히 시간초과가 발생했다.N이 커질수록 백트래킹을 통해 모든 가능성을 탐색하는 과정에서 시간 복잡도가 급격히 증가하기 때문이다. 이를 해결하기 위해서 퀸의 이동 방식에 대해서 다시 생각해보면 아래와 같다. 퀸의  이동방식 퀸은 다음과 같은 방식으로 이동한다. 같은 행에 있는 퀸끼리는 서로 공격할 수 없으므로, 한 행에 하나의 퀸만 배치할 수 있다.퀸은 같은 열에 있는 다른 퀸과도 공격할 수 없으므로, 한 열에도 퀸은 하나만 배치되어야 한다..

백트래킹 재귀적으로 문제를 하나씩 풀어나가되 현재 재귀를 통해 확인 중인 상태(노드)가 제한 조건에 위배되는지 판단하고 위배되는 경우 해당 상태를 제외하고 다음 단계로 나아가는 방식이다. 해를 찾는 도중에 막히면 해당 상태로 더 탐색하지 않고 돌아가서 해를 찾아나가는 방식이다. 이때 더 이상 탐색할 필요가 없는 상태를 제외하는 것을 가지치기(pruning)이라고 한다. 모든 경우의 수를 체크하지 않게 되므로 시간을 단축할 수 있다. 유사한 알고리즘으로 DFS(깊이 우선 탐색)이 있다. DFS와 백트래킹의 차이는 DFS는 모든 경우의 수를 탐색하지만 백트래킹은 DFS와 다르게 백트래킹은 불필요한 탐색을 하지 않는다. 사용 문제 의사결정 문제 최적화 문제 열거 문제 핵심 아이디어 재귀 호출 : 문제를 해결하..

https://school.programmers.co.kr/learn/courses/30/lessons/43163 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV 3 문제 설명 시작 단어 begin, 도착 단어 target이 주어지고 변환할 수 있는 단어의 배열 words가 주어진다. 변환할 수 있는 조건은 한번에 한 개의 알파벳만 바꿀 수 있고, words안에 있는 단어로만 변경이 가능하다. 최소 몇단개에 걸쳐 begin의 단어를 target으로 변환 가능한지 Retrun해준다. 만약 변환할 수 없는 경우 0을 Retrun 해준다. 해결법 d..

https://school.programmers.co.kr/learn/courses/30/lessons/43164 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 난이도 LV3 문제 설명 [출발지,도착지] 형태로 적힌 항공권 정보 List가 주어진다. 출발지는 항상 ICN 공항에서 출발하며 모든 항공권을 사용해야 한다. 이를 만족하는 경로를 Return하고 만약 만족하는 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 Return한다. 접근법 스택에 ICN을 넣어준다. 출발지와 도착지 정보가 담긴 dictionary 배열의 key(출발지) 와 valu..

깊이 우선 탐색 알고리즘 (DFS) 한 루트로 들어가 가장 깊이 들어가서 탐색후 돌아가 다시 다른 루트로 가장 깊이 탐색하는 방식이다. 넓게 탐색하는 것이 아닌 깊이 탐색하는 방식이다. 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. 스택 자료구조를 사용한다. 구현 방법 재귀 호출 스택 배열 동작 과정 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다. 사용 용도 순회를 하는 경우에 많이 사용된다. 백트레킹에 사용된다. 자동 미로 생성에 많이 사용된다. 유향 그래프에서 ..

https://www.acmicpc.net/problem/11403 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 정답 code #경로 찾기 n = int(input()) graph = [] for i in range(n): graph.append(list(map(int,input().split()))) for k in range(n): for i in range(n): for j in range(n): if (graph[i][k] == 1 and graph[k][j] == 1): graph[i][j] = 1 for i in graph: for j i..

https://www.acmicpc.net/problem/10026 10026번: 적록색약 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록) www.acmicpc.net 정답 code -bfs활용 #적록색약 from collections import deque import sys input = sys.stdin.readline dx = [-1,1,0,0] dy = [0,0,-1,1] def bfs(x,y): q.append([x,y]) visit[x][y] = cnt while q: x, y = q.popleft() for i in range(4): nx ..

https://www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 정답 code -DFS풀이 #연결 요소의 개수 import sys sys.setrecursionlimit(5000) input = sys.stdin.readline #dfs풀이 def dfs(x): visited[x] = True for i in c[x]: if not visited[i]: dfs(i) n, m = map(int,inp..

https://www.acmicpc.net/problem/2606 2606번: 바이러스 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어 www.acmicpc.net 정답 code -dfs 활용 #dfs이용 def dfs(com, x): global cnt visited[x] = True for i in com[x]: if visited[i] == False: dfs(com,i) cnt += 1 return True n = int(input()) c = int(input()) cnt = 0 com = [[] for _ in range(n+1)] for _ in ra..

https://www.acmicpc.net/problem/1260 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net 정답 code #DFS 와 BFS from collections import deque import sys input = sys.stdin.readline def dfs(v): print(v, end = ' ') visit[v] = True for i in graph[v]: if visit[i] == False: dfs(i) def bfs(n): visit[n..