![]()
문제 설명네트워크로 연결되어있는 컴퓨터들이 있는데 1번 컴퓨터가 바이러스에 걸리면 1번 컴퓨터와 연결된 컴퓨터는 모두 바이러스에 감염된다.이때 1번 컴퓨터로 인해 바이러스에 감염된 컴퓨터의 개수를 구하라입력컴퓨터 대수연결된 컴퓨터쌍 수컴퓨터 쌍 1컴퓨터 쌍 2컴퓨터 쌍 3.....ex)761 22 31 55 25 64 7출력감염된 컴퓨터 개수코드(입력 받는 부분은 따로 첨부하지 않았다)이 문제는 항상 1번 컴퓨터에서 바이러스가 시작되는 것으로 정해져있으므로 함수를 만들지 않고 바로 실행하는 코드로 만들었다먼저 visit 리스트를 만들어주고 방문한 노드를 저장할 queue도 만들어준다(14, 15번 줄)그리고 while 문을 이용하여 queue에 더이상 방문할 노드가 없을 때까지 반복한다.한번 방문을 할때..
https://www.acmicpc.net/problem/15723코드#include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std;vector graph[27];int bfs(int start,int find){ bool visited[27] = { false, }; queue q; q.push(start); visited[start] = true; int ans = 0; // 큐가 빌 때까지 반복 while (!q.empty()) { // 큐에서 하나의 원소를 뽑아 출력 int x = q.front(..
2644번: 촌수계산 (acmicpc.net) 코드 import sysinput = sys.stdin.readlinen=int(input())a,b=map(int,input().split())m=int(input())di={}for _ in range(m): #di 입력받기 u,v=map(int,input().split()) if u in di: di[u].append(v) else: di[u]=[v] if v in di: di[v].append(u) else: di[v]=[u]ans_visit={}st=[a]while st: node=st.pop() if node in ans_visit: continue st.extend(di[node]) if node=..
https://school.programmers.co.kr/learn/courses/30/lessons/43163?language=go 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr문제 설명두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다.1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다.2. words에 있는 단어로만 변환할 수 있습니다.예를 들어 begin이 "hit", target가 "cog", words가 ["hot",..
문제https://codeforces.com/contest/1968/problem/D난이도백준기준 G5~G3쯤 될 것 같다.알고리즘 분류DFS, 게임이론, 수학풀이코포 치면서 이 문제 되게 좋았던 것 같다. 이름에서부터 게임이 들어가있듯이 게임이론에 대한 최소한의 이해를 하고 있으면 조금 도움이 된다. 일단 알고 들어가야 하는 것은 양쪽 플레이어는 항상 최선을 다해서, 최대의 점수를 얻기 위해 노력을 하고 이 문제에서 양쪽 플레이어는 서로에게 영향을 주지는 못한다. 따라서 각각 얻을 수 있는 최대 점수를 구해주면 된다.점수는 1초 마다 현재 플레이어의 idx에 해당하는 score의 점수를 얻는다. 그리고 플레이어는 idx와 순열에 따라 이동을 하거나 하지 않을 수 있다. 문제에서 플레이어의 맨 처음 위치..
내리막 길!https://d2gd6pc034wcta.cloudfront.net/tier/13.svg시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율2 초128 MB84978242651742928.392%문제여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.https://upload.acmicpc.net/0e11f3db-35d2-4b01-9aa0-9a39252f05be/-/preview/현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다...
![]()
https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 분석 분류 자료구조 스택 문제 설명 스택 (stack)은 기본적인 자료구조 중 하나로, 컴퓨터 프로그램을 작성할 때 자주 이용되는 개념이다. 스택은 자료를 넣는 (push) 입구와 자료를 뽑는 (pop) 입구가 같아 제일 나중에 들어간 자료가 제일 먼저 나오는 (LIFO, Last in First out) 특성..
문제 https://www.acmicpc.net/problem/17198 Algorithm R인 지점에 유의하여 B부터 L까지의 거리를 저장하는 visited 배열을 선언한 뒤 BFS를 수행한다. B인 지점을 1로 초기화하는 것과 L로 이동하는 거리는 카운트하지 않으므로, 답안 출력 시 -2 연산에 유의한다. Code #include #include #include #include using namespace std; #define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0); typedef long long ll; typedef pair pii; typedef pair pll; char graph[11][11]; int visited[11][11]; pi..
문제 링크 https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net 접근 방법 문제 자체는 간단합니다. 1231234 에서 3개의 숫자를 뺀 가장 큰 숫자가 3234라는 것을 사람은 쉽게 생각할 수 있을 것입니다. 숫자 지우는 과정을 단계별로 살펴보겠습니다. 1231234에서 숫자를 하나빼서 만들 수 있는 가장 큰 숫자는 가장 앞의 1을 뺀 231234입니다. 다른 어느 위치의 숫자를 지워도 이 숫자보다 클 수 없습니다. 231234에서 숫자를 하나빼서 만들 수 있는 가장 큰 숫자는 앞선 이유와 동일하게 31234입니다. 마찬가지..
![]()
https://school.programmers.co.kr/learn/courses/30/lessons/12909 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr def solution(s): li=[] for i in s: if i=='(': li.append(i) elif i ==')' and len(li)>0: li.pop() else: return False if len(li)!=0: return False return True 단순 스택 문제이다. 입력받은 s를 돌며 (면 받아주고 )일 때 스택이 안비어있다면 아직 안닫혔으므로 팝해주고 그게 아니라..
문제 https://school.programmers.co.kr/learn/courses/30/lessons/42627 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 스케쥴링 기법 중 SJF(Shortest Job First)에서 아이디어를 얻어와 문제를 해결했다. Shortest Job First란, 수행해야할 Job 중에 가장 수행 시간이 짧은 Job을 먼저 수행하여 convoy effect(https://www.geeksforgeeks.org/convoy-effect-operating-systems/)를 방지하는 스케쥴링 기법이다. 이 문제에서..
https://www.acmicpc.net/problem/22252 풀이 1 정보 파는 고릴라이름 , k개 , 정보의 가치 2 정보 살 고릴라 이름 , 구매할 정보 개수 시간제한 2초 , 쿼리 최대 수 1e5 , 정보 리스트의 원소 최대 개수 1e5 , 최대 고릴라의 수 1e5 , 최대 정보를 구매 할 수 1e5 최악의 경우 : 1e5 * (파이썬 리스트 정렬 nlogn) → 시간초과 ⇒ 정렬해서 큰 값 뽑아내는거 아님 우선순위큐 힙큐 사용 1일시 hash_map에서 고릴라를 찾고 데이터를(힙큐 속성) 넣어준다 2일시 hash_map에서 고릴라를 찾고 힙큐를 꺼내서 데이터를 뽑아내고 다시 저장 나의 실수 코드 import heapq n=int(input()) hash_map={} result=0 for ..
