OSNIM

DFS/BFS, 실버 2 문제: https://www.acmicpc.net/problem/1012 문제 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. 한 배추의 상하좌우 네 방향에 다른 배추가 위치한 경우에 서로 인접해있는 것이다. 한나가 배추를 재배하는 땅은 고르지 못해서 배추를 군데군데 심어 놓았다..

DFS/BFS, Level 3 문제: 문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. 입출력 예 t..

DFS/BFS, Level 3 문제: https://programmers.co.kr/learn/courses/30/lessons/43163 코딩테스트 연습 - 단어 변환 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 programmers.co.kr 문제 설명 두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변..

DFS/BFS, Level 2 문제: https://programmers.co.kr/learn/courses/30/lessons/43165 코딩테스트 연습 - 타겟 넘버 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 programmers.co.kr 문제 설명 n개의 음이 아닌 정수들이 있습니다. 이 정수들을 순서를 바꾸지 않고 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다. -1+1+1+1+1 = 3 +1-1+1+1+1 = 3 +1+1-1+1+1 ..

문제: https://www.acmicpc.net/problem/10026 문제 적록색약은 빨간색과 초록색의 차이를 거의 느끼지 못한다. 따라서, 적록색약인 사람이 보는 그림은 아닌 사람이 보는 그림과는 좀 다를 수 있다. 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다. 그림은 몇 개의 구역으로 나뉘어져 있는데, 구역은 같은 색으로 이루어져 있다. 또, 같은 색상이 상하좌우로 인접해 있는 경우에 두 글자는 같은 구역에 속한다. (색상의 차이를 거의 느끼지 못하는 경우도 같은 색상이라 한다) 예를 들어, 그림이 아래와 같은 경우에 RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람이 봤을 때 구역의 수는 총 4개이다. (빨강 2,..

Level 3, DFS/BFS 문제: https://programmers.co.kr/learn/courses/30/lessons/43162 코딩테스트 연습 - 네트워크 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있 programmers.co.kr 문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결 > 컴퓨터 A와 컴퓨터 C도 간접적으로 연결된 하나의 네트워크 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주..

문제 : https://www.acmicpc.net/problem/11724 첫번째 풀이 처음에 서로소 방법인 줄 알고 그래프 이론의 서로소 구하는 방법을 이용하여 구현하려고 했습니다. 코드는 다음과 같습니다. import sys #특정 원소가 속한 집합 찾기 def findParent(parent, v): # 루트노드가 아니라면 루트 노드를 찾을 때 까지 재귀적 호출 if parent[v] != v: parent[v] = findParent(parent, parent[v]) return parent[v] #부모 합치기 def unionParent(parent, v1, v2): v1 = findParent(parent, v1) v2 = findParent(parent, v2) if v1 < v2: par..

문제: https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV7GOPPaAeMDFAXB T = int(input()) # 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다. def dfs(start, depth): global ans ans = max(ans, depth) for next in graph[start]: if visited[next]: continue visited[next] = True dfs(next, depth + 1) visited[next] = False for test_case in range(1, T + 1): N, M = map(int, input().split()) graph = [..

문제 출처: https://www.acmicpc.net/problem/19238 나의 접근법 그래프에 남은 연료를 넣기 위해 벽을 -1로 변경 손님들의 위치 정보와 도착정보를 따로 저장 BFS() 1. 먼저 현재 위치에 손님이 있는지 확인 2. BFS로 거리 1차이 나는 거리 확인 -> q에 넣기 3. 같은 거리에 또 다른 손님이 있는지, 첫 손님은 찾았는지, 거리가 같은지 -> custList에 추가 4. 현재 g에 넣는 연료 (남은 연료)가 첫 손님을 찾았을 때 남은 연료보다 작은지 -> 작다면 거리가 같은 손님은 다 찾은 것 -> 정렬 후 행이 낮고 열이 낮은 손님부터 목적지 찾기 5. 가까운 손님을 첫손님을 찾은 경우 -> custList에 추가 5-1 만약 그 첫 손님이 마지막 칸에 있는 경우 ..

문제 출처: https://www.acmicpc.net/problem/17142 나의 접근법 먼저 바이러스 중에서 M개를 선택하는 조합의 경우를 모두 구합니다. 그리고 난 뒤 그래프의 모든 곳을 방문해야 하는데 이를 위해 DFS와 BFS중 무엇을 사용할지 고민 했습니다. 구현을 바로 하기 전에 먼저 DFS로 머리 속에서 시뮬레이션을 돌려봤습니다. 1. DFS로 할 경우 첫번째로 선택한 바이러스의 위치가 모든 곳을 탐색하고 이동할 때 마다 시간을 적습니다. 2. 그 다음 바이러스가 탐색할 때 첫번째 바이러스가 저장한 장소 중 자신이 탐색하는 시간보다 큰 경우에만 탐색을 하며 시간을 업데이트 합니다. 위 방식으로 하게 되면 불필요한 계산이 생기고 방문했던 곳을 또 방문하게 된다면 visited 판단에서 에러..

문제 출처: https://www.acmicpc.net/problem/14501 나의 접근법 상담 일정 전체를 탐색하는 반복문 안에 일정이 가능한지 확인하며 일정과 T를 확인하며 N+1이 넘어갈 때까지 while로 체크하며 해결하려고 했습니다. 하지만 이렇게 할 경우 예제1 은 1일 -> 4일 -> 5일은 찾지만 예제 4의 1일 -> 6일 -> 7일은 찾았지만 1일 -> 6일 -> 8일의 경우는 못 찾았습니다. 이 문제점을 찾았더니 DFS와 백트래킹이 생각나서 바로 구현 방식을 틀고 다음과 같이 작성하였습니다. 첫번째 코드 def dfs(startDate, period, pay): global ans # 상담하면 퇴사날이 넘어 가는 경우 for i in range(startDate+period, N+1)..

문제 출처: https://www.acmicpc.net/problem/15683 나의 접근법 먼저 그리디 인지 DFS인지 고민을 했습니다. cctv의 번호가 높을 수록 많은 범위를 감시하는 것 같아서 그리디로 먼저 풀었습니다. 그래서 번호가 높은 cctv를 역으로 정렬하여 탐색했습니다. 하지만 그리디로 풀 경우 현재 값이 다음 값에 영향을 받을 수 있다는 것을 office를 출력해서 알게 되었습니다. DFS로 작성하기 위해서는 원래의 office에 #을 추가한 office을 따로 구분해야 했습니다. 또한 #을 추가한 office을 임시로 저장하고 DFS 탐색이 끝난 뒤 return 했을 때, 또 새로운 office를 DFS 단계에 넘겨줘야 하는데 여기서 해답을 찾지 못했습니다. 마지막으로 cctv 번호 ..

문제 출처: https://www.acmicpc.net/problem/18405 나의 접근법 위 문제는 이것이 코딩테스트다 with 파이썬 에 수록된 문제입니다. 먼저 답을 읽지 않고 제 스스로 풀어보려고 노력했습니다. 바이러스의 위치를 x,y좌표로 기억하여 번호 마다 리스트에 저장하였습니다. 그리고 시간 S 만큼 반복하여 바이러스를 퍼뜨렸습니다. 일반 케이스 말고 특이 케이스도 생각해봤습니다. 만약 1번 바이러스가 2번 나오면 어떡하지? 만약 1~K번의 바이러스가 연속으로 나오지 않고 랜덤으로 나오면 어떡하지? 저는 위와 같은 경우의 수도 고려하며 풀려고 노력했습니다. 첫번째 풀이법 import sys from collections import deque def BFS(virus, virusPositi..

문제 출처: https://www.acmicpc.net/problem/14502 깊은 복사와 얕은 복사 파이썬에서는 리스트를 크게 얕은 복사와 깊은 복사 2가지로 복사하고 있습니다. 얕은 복사 객체의 주소값을 복사하는 경우입니다. 대입 연산자 (‘=’) 를 사용해서 리스트를 다른 리스트에 대입하는 방식입니다. 변형(mutable) 객체는 복사한 객체의 내용을 변경하면 원본 리스트의 내용도 변합니다 불변형(immutable) 객체는 복사한 객체의 내용을 변경해도 원본에는 영향이 없습니다. 깊은 복사 객체의 데이터만을 복사하는 경우입니다. copy 모듈의 copy() ,deepcopy() 함수를 사용합니다. 1차원 리스트는 copy()를 사용하고 2차원 이상의 배열은 deepcopy() 함수를 사용합니다. ..

탐색 (Search) 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정으로 그래프, 트리등의 자료구조 안에서 탐색이라는 과정을 사용합니다. 대표적인 탐색 알고리즘으로는 DFS, BFS이 있습니다. 이러한 탐색 알고리즘을 사용하기 위해서는 스택(Stack)과 큐(Queue)라는 자료구조를 사용합니다. 자료구조: 데이터를 표현하고 관리하고 처리하기 위한 구조 스택과 큐는 push(삽입), pop(삭제) 함수들을 사용합니다. push(삽입), pop(삭제)를 사용하기 위해서는 오버플로우(Overflow), 언더플로우(Underflow)를 고려해야 합니다. 오버플로우(Overflow): 스택과 큐 등의 자료구조의 용량이 가득 찬 상태에서 push()를 수행할 경우 발생합니다. 언더플로우(Underflow): ..