티스토리

coding tasty house

검색하기

블로그 홈

coding tasty house

gyeong99.tistory.com/m

moguogu 님의 블로그입니다.

구독자: 2

방명록 방문하기

주요 글 목록

[백준 2146] 다리 만들기 문제 https://www.acmicpc.net/problem/2146 알고리즘1. bfs그래프 탐색을 통해서 1로 되어 있는 땅을 2, 3, 4 .. 으로 각 구역을 숫자로 구분한다2. 다음 bfs 탐색을 통해서 시작 구역의 위치를 queue에 담아둔다 3. 탐색 과정에서 자신의 구역과 다른 구역을 만났을 때 최단거리를 반환한다 코드 import sysfrom collections import dequedef Input_Data(): input = sys.stdin.readline N = int(input()) graph = [] for _ in range(N+1): graph.append(list(map(int, input().split()))) return N.. 공감수 0 댓글수 0 2024. 9. 17.
[백준 1987] 알파벳 문제 https://www.acmicpc.net/problem/1987코드# 백트래킹 문제 import sysfrom collections import dequesys.setrecursionlimit(10**9)def Input_Data(): input = sys.stdin.readline R, C = map(int, input().split()) graph = [] for _ in range(R): graph.append(list(input())) return R,C, graphd = ((1,0),(-1,0),(0,1),(0,-1))def Dfs(x,y,cnt): global ans ans = max(cnt, ans) for dx, dy in d.. 공감수 0 댓글수 0 2024. 9. 17.
[백준 1922] 네트워크 연결 문제https://www.acmicpc.net/problem/1922알고리즘1. 연결관계를 dict에 저장한다2. 다익스트라 알고리즘으로 최단 경로를 탐색한다 3. 모든 네트워크가 연결되어야 하므로 1번부터 끝 번인 N번까지 탐색 하여 최소 값을 업데이트 한다 코드import sys, math, heapqdef Input_Data(): input = sys.stdin.readline N = int(input()) M = int(input()) adj = {i : [] for i in range(1,N+1)} for _ in range(M): a,b,c = map(int, input().split()) adj[a].append([b,c]) a.. 공감수 0 댓글수 0 2024. 9. 17.
[백준 1431] 시리얼 번호 문제 https://www.acmicpc.net/problem/1431 알고리즘단어의 길이, 숫자의 합, 단어 사전 순으로 내림 차순 정렬이 필요하다 key = lambda :x 와 sort 함수를 사용하여 구현 할 수 있다 소스코드 import sysdef digit_sum(cur): num_sum = 0 for x in cur: if '0' 공감수 0 댓글수 0 2024. 9. 17.
[백준 1092] 배 문제https://www.acmicpc.net/problem/1092 코드import sysN = int(input())weight = list(map(int, input().split()))M = int(input())box = list(map(int, input().split()))weight.sort(reverse=True)box.sort(reverse=True)if weight[0] = box[j]: #현재 크레인을 쓸 수 있음 box.pop(j) else: #현재 크레인을 쓸 수 없음 -> 다시 제일 무거운 크레인 부터 사용 break 공감수 0 댓글수 0 2024. 9. 17.
[백준 5014] 스타트링크 문제 https://www.acmicpc.net/problem/5014코드import sysfrom collections import dequedef Bfs(): q = deque() q.append(S) visited[S] = 1 while q: x = q.popleft() # 위로 가는 경우 if (x+U0): if visited[x-D] == 0: #방문하지 않았으면 방문 visited[x-D] = visited[x] + 1 q.append(x - D) # 도달하지 못한 경우 if visited[G] == 0: return "use th.. 공감수 0 댓글수 0 2024. 9. 2.
[백준 13023] ABCDE 문제https://www.acmicpc.net/problem/13023 코드 import sysfrom collections import dequesys.setrecursionlimit(10**9)def Input_Data(): input = sys.stdin.readline N, M = map(int, input().strip().split()) adj = {i : [] for i in range(N)} for _ in range(M): a, b = map(int, input().strip().split()) adj[a].append(b) adj[b].append(a) return N, M, adjdef Dfs(start, depth): .. 공감수 0 댓글수 0 2024. 9. 1.
[백준 1504] 특정한 최단 경로 문제 https://www.acmicpc.net/problem/1504 알고리즘1. 최단 경로를 탐색해야함2. A/B는 반드시 거쳐가야 하므로 시작점과 끝점을 정해서 최단 경로를 구해 온 뒤 최소 값을 출력한다3. 1->A->B->N /// 1->B->A->N 을 각각 구해서 최소 값을 구한다 코드import sys, heapq, mathdef Input_Data(): input = sys.stdin.readline N, E = map(int, input().split()) graph = {i : [] for i in range(1, N+1)} for _ in range(E): # 양방향 그래프 관계 저장 a,b,c = map(int, input().spl.. 공감수 0 댓글수 0 2024. 9. 1.
[백준 6593] 상범 빌딩 문제https://www.acmicpc.net/problem/6593 코드import sysfrom collections import dequeinput = sys.stdin.readlined = ((1,0,0),(-1,0,0),(0,1,0),(0,-1,0),(0,0,1),(0,0,-1))def Bfs(start_l, start_x, start_y): q = deque() q.append((start_l, start_x, start_y)) visited[start_l][start_x][start_y] = 1 while q: v, x, y = q.popleft() if v == end_l and x == end_x and y == end_y: .. 공감수 0 댓글수 0 2024. 8. 31.
[백준 1068] 트리 문제 https://www.acmicpc.net/problem/1068 코드import sysfrom collections import dequesys.setrecursionlimit(10**9)def Input_Data(): input = sys.stdin.readline N = int(input()) node = list(map(int, input().split())) erase = int(input()) #지울 노드 adj = [ [] * (1) for _ in range(N)] # 간선 저장 for idx, v in enumerate(node): if v == -1 : # root root = idx elif id.. 공감수 0 댓글수 0 2024. 8. 21.
[백준 10026] 적록색약 https://www.acmicpc.net/problem/10026 import sysfrom collections import dequedef Input_Data(): readl = sys.stdin.readline N = int(input()) graph = [list(input()) for _ in range(N)] return N, graph d = ((1,0), (0,1), (-1, 0), (0,-1))def Bfs(i,j,color): q = deque() q.append((i,j)) visited[i][j] = 1 while q: x,y = q.popleft() for dx, dy in d: nx.. 공감수 1 댓글수 2 2024. 7. 24.
[백준 2578] 빙고 문제 https://www.acmicpc.net/problem/2578 2578번: 빙고 첫째 줄부터 다섯째 줄까지 빙고판에 쓰여진 수가 가장 위 가로줄부터 차례대로 한 줄에 다섯 개씩 빈 칸을 사이에 두고 주어진다. 여섯째 줄부터 열째 줄까지 사회자가 부르는 수가 차례대로 www.acmicpc.net 알고리즘 1. 사회자가 불러주는 수의 값을 체크 할 수 있도록 빙고판과 같은 크기의 배열을 생성한다 2. 사회자가 값을 부를 때 마다 체크 한다 3. 체크 한 값이 12 이상일 때 마다 행과열의 합을 구해서 각 한 줄 씩 빙고가 성립한지 확인한다 4. 3줄이상 달성했을 경우 센 횟수 값을 출력하며 종료한다 코드 import sys def Input_Data(): readl = sys.stdin.readli.. 공감수 0 댓글수 0 2024. 2. 10.
[백준 2583] 영역 구하기 문제 https://www.acmicpc.net/problem/2583 2583번: 영역 구하기 첫째 줄에 M과 N, 그리고 K가 빈칸을 사이에 두고 차례로 주어진다. M, N, K는 모두 100 이하의 자연수이다. 둘째 줄부터 K개의 줄에는 한 줄에 하나씩 직사각형의 왼쪽 아래 꼭짓점의 x, y좌표값과 오 www.acmicpc.net 알고리즘 1. 주어진 사각형의 좌표를 조회해서 해당영역을 그래프에 1로 채워준다 (초기화 0으로) 2. 2차원 그래프를 조회해서 0으로 시작되는 구역이 나올때 section의 값을 올려준다 3. bfs순회시, 방문때 이미 간 곳은 2로 바꿔준다 코드 import sys from collections import deque def input_data(): readl = sy.. 공감수 1 댓글수 1 2024. 2. 4.
[백준 6236] 용돈 관리 문제설명 https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net 알고리즘 1. 사용할 수 있는 돈의 최소는 i일 동안 사용할 금액 중에 가장 큰 값, 그리고 돈의 최대는 모든 사용할 돈의 합이다 2. 해당 두 값으로 이분탐색을 진행한다 3. 이분탐색을 할 때, 돈 인출 수를 세어보고 더 많이 인출해야하는 경우 돈을 키우고 그렇지 않은 경우 금액을 줄인다 코드 import sys def Input_Data(): readl = sys.stdin.readline.. 공감수 0 댓글수 0 2024. 1. 31.
[백준 3055] 탈출 문제설명 https://www.acmicpc.net/problem/3055 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 알고리즘 1. 그래프 정보 입력 2. 고슴도치 위치, 홍수 지역 정보 저장 3. 홍수 정보를 통해 1분당 홍수 그래프에 반영 4. 고슴도치 이동 반복 코드 import sys from collections import deque def Input_Data(): R, C = map(int,readl().split()) map_forest = [[0] + list(readl()[:-1]) + [0] if 1 공감수 0 댓글수 1 2024. 1. 31.
[백준 2531] 회전 초밥 문제설명 https://www.acmicpc.net/problem/2531 2531번: 회전 초밥 첫 번째 줄에는 회전 초밥 벨트에 놓인 접시의 수 N, 초밥의 가짓수 d, 연속해서 먹는 접시의 수 k, 쿠폰 번호 c가 각각 하나의 빈 칸을 사이에 두고 주어진다. 단, 2 ≤ N ≤ 30,000, 2 ≤ d ≤ 3,000, 2 ≤ www.acmicpc.net 알고리즘 이번 문제는 단순하게 반복문으로 결과를 구해낼 수 있다 하지만 시간 제약이 있기 때문에 sliding window를 사용해야한다 k개를 확인해서 초밥의 갯수를 세기때문에 1칸씩 옮겨가며 연산한다 이때 모든 초밥을 다 다시세면 반드시 시간초과가 발생하기 때문에, 새로 추가되는 초밥만 세고 먹을 수 없는 초밥은 빼는 것이 문제의 해결 방식이다 .. 공감수 0 댓글수 1 2024. 1. 28.
[백준 1920] 수 찾기 문제설명 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 코드 #include #include #include using namespace std; int n, m, temp; vector num, finds; void binarySearch(int key){ int start=0, end=num.size()-1; while(start temp; num.push_back(temp); } cin >.. 공감수 0 댓글수 0 2023. 5. 17.
[프로그래머스] 추억 점수 문제설명 https://school.programmers.co.kr/learn/courses/30/lessons/176963 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 알고리즘 코드 #include #include #include using namespace std; vector solution(vector name, vector yearning, vector photo) { vector answer; map m; for(int i=0; i 공감수 0 댓글수 0 2023. 5. 12.
[백준 2468] 안전 영역 문제설명 https://www.acmicpc.net/problem/2468 알고리즘 1. 그래프 입력(최대높이 저장) 2. 높이별로 반복해서 dfs 연산 3. 최대 높이 출력 코드 #include #include #include using namespace std; int graph [101][101]={0,}; bool visited[101][101]={0,}; int dx[4] ={1,-1,0,0}; int dy[4] ={0,0,1,-1}; int N; void dfs(int x, int y, int height){ visited[x][y]= true; for (int i = 0; i = N || dx[i]+x =N || dy[i].. 공감수 0 댓글수 0 2023. 4. 11.
[프로그래머스] 음양더하기 문제설명 알고리즘 1. 숫자입력 2. 부호 판별 후 결과 더하기 코드 #include #include using namespace std; int solution(vector absolutes, vector signs) { int answer = 0; for(int i=0; i 공감수 0 댓글수 0 2023. 3. 5.
[프로그래머스] 뒤에 있는 큰 수 찾기 문제설명 알고리즘 1. 수를 stack에 입력 받는다 first는 숫자, second는 인덱스 값이 된다 2. stack이 비어있지 않다면, 맨 위의값을 꺼내어 현재 숫자와 비교하여 크거나 같으면 반복문을 빠져나가고 그렇지 않으면 stack에서 뺀다 3. 반복문을 나온 상태이면 현재 수 값과 인덱스를 저장한다 코드 #include #include #include using namespace std; vector solution(vector numbers) { vector answer(numbers.size(), -1); stack st; for(int i =0 ; i< numbers.size() ; i++){ while(!st.empty()){ pair top = st.top(); if(top.first.. 공감수 0 댓글수 0 2023. 3. 5.
[프로그래머스] 게임 맵 최단거리 문제설명 https://school.programmers.co.kr/learn/courses/30/lessons/1844 코드 #include #include #include using namespace std; int visited[101][101]={}; int dx[4]= {-1,1,0,0}; int dy[4]= {0,0,-1,1}; int solution(vector maps) { int answer = 0; queue q; q.push({0,0}); visited[0][0] = 1; while(!q.empty()){ int x = q.front().first; int y = q.front().second; q.pop(); for(int i=0; i< 4; i++){ int nx = x + dx[.. 공감수 0 댓글수 0 2023. 2. 24.
[프로그래머스] 가장 가까운 같은 글자 문제설명 알고리즘 1. 알파벳과 그 인덱스를 map 에 저장한다 2. map에서 해당 key를 조회하고 있으면 그 value와 문자열을 순회하는 index값을 빼어 결과값에 저장 3. key가 없는 경우 결과값에 -1 저장, 그리고 map에 key값과 현재 index저장 코드 #include #include #include using namespace std; vector solution(string s) { vector answer; map m; for(int i=0; i< s.size(); i++){ char temp = s[i]; if(m.count(temp)){//해당 알파벳이 있으면 answer.push_back(i-m[temp]); //제일 가까운 위치 구해서 거리 저장 m[temp] = i;.. 공감수 0 댓글수 0 2023. 2. 24.
[프로그래머스] 크기가 작은 부분 문자열 문제설명 알고리즘 1. t 문자열을 하나하나 조회한다 2. 조회시 현재 인덱스에서 p의 길이 -1 보다 작을때만 연산을 하는데, substr로 문자를 자른다 3. compare함수를 사용해서 사전순으로 더 앞이면 작거나 같다 -> 답 갯수 증가 코드 #include #include #include using namespace std; int solution(string t, string p) { int answer = 0; for(int i=0; i 공감수 0 댓글수 0 2023. 2. 22.
[프로그래머스] 귤 고르기 문제설명 알고리즘 1. 귤의 크기 별 몇 개 존재하는 지 카운트 -> (key, value) 형태인 map이 가장 적절 2. MAP에 넣은 뒤, 귤의 갯수 기준으로 내림차순 정렬 3. 벡터로 변환하여 벡터 순회하여 k 개에서 최대 귤 수 부터 k 값 감소 시키기 & 결과 값 증가 코드 #include #include #include #include #include using namespace std; bool cmp (const pair &a, const pair &b){ if(a.second == b.second) return a.first > b.first; return a.second > b.second; } int solution(int k, vector tangerine) { int answer.. 공감수 0 댓글수 0 2023. 2. 22.
[프로그래머스] 명예의 전당(1) 문제설명 알고리즘 1. 점수 값을 조회하면서 다른 벡터에 값을 넣는다 2. 내림차순으로 정렬한다 3. K번째가 되기전까지는 가장 큰 인덱스 값이 최하 값이고, K번째까지 벡터에 들어왔을 경우 K-1번째가 최하값이므로 저장한다 코드 #include #include #include #include using namespace std; vector solution(int k, vector score) { vector answer; vector temp; for(int i=0; i< score.size(); i++){ int current = score[i]; temp.push_back(current); sort(temp.rbegin(), temp.rend()); // 내림차순 정렬 if(i 공감수 0 댓글수 0 2023. 2. 22.
[프로그래머스] 과일장수 문제설명 해당 문제는 주어진 값에서 얻을 수 있는 최대 가치를 계산하는 문제이다 상자에 과일의 가치가 주어지면 한 상자에 들어갈 수 있는 과일의 수와 최대 과일의 가치 값을 입력받는다 알고리즘 1. 과일의 가치를 내림차순으로 정렬한다 2. 팔 수 있는 최대의 상자 수 만큼 반복문을 돈다(남는 과일은 버리기 때문에 완성되는 상자 기준으로 계산한다) 3. 각 상자마다 가장 가치가 낮은 것이 얻을 수 있는 값이기 때문에 각 상자마다 제일 가치가 낮은 인덱스에 접근해서 결과 값을 계산한다 코드 #include #include #include #include using namespace std; int solution(int k, int m, vector score) { int answer = 0; //내림차순 .. 공감수 0 댓글수 0 2022. 11. 14.
[백준 7569] 토마토 문제설명 토마토가 상자안에 들어있다 가로M, 세로N, 높이 H로 상자가 주어진다 1은 토마토가 익어있다는 의미이고, -1은 빈 공간이다. 하루마다 익은 토마토를 기점으로 위,아래, 상,하,좌,우가 익는다 모든 토마토가 다 익는데 걸리는 최소한의 기간을 출력시킨다 단, 토마토가 원래 다 익어있는 경우에는 0을 출력하고, 토마토가 다 익지 못하는 경우는 -1을 출력시킨다 알고리즘 1. 입력 정보 받기 2. 그래프의 값이 1인(토마토가 익은경우) queue에 그 좌표값을 넣는다 3. bfs알고리즘을 사용하여 상,하,좌,우, 위, 아래를 모두 확인한다 4. 방문기록을 조회하여 0이 남아있는 경우 -1을 출력하고 그렇지 않은 경우엔 최대값을 출력시킨다 코드 #include #include #include usin.. 공감수 0 댓글수 0 2022. 7. 11.
[백준 5525] IOIOI 문제설명 알고리즘 1. 입력받기 2. N으로 패턴 만들기 3. 주어진 문자열 S에서 N을 find함수로 찾기 4. 찾을때 마다 결과값 변수 1씩 증가, index를 업데이트 1. 입력받기 2. I를 만날때 마다 바로 뒤에 OI가 있으면 k증가, 문자열 index를 2씩 증가 3. OI가 I이후로 N번 나오면 패턴 매칭이 완료된 것이므로 결과 값 증가 , k 감소 4. 결과값 출력 코드 #include #include using namespace std; int main() { int N, M,cnt=0; cin >> N >> M; string S; cin >> S; /*string val; for (int i = 1; i 공감수 0 댓글수 0 2022. 7. 11.
[백준 1992] 쿼드트리 문제설명 알고리즘 1. 그래프 정보 입력 받기 2. 4등분 해서 해당 네모가 모두 같은 값으로 이루어진지 판단 3. 모두 같은 값이면 그 값을 출력하고 종료 4. 모두 같은 값이 아니면 또 4등분 해서 반복 코드 #include #include using namespace std; int graph[65][65]; void cut(int a, int b, int size) { int cnt_0 = 0, cnt_1 = 0; for (int i = a; i < a + size; i++)//모두 1이거나 모두 0 인경우 판단 { for (int j = b; j < b + size; j++) { if (graph[i][j]) cnt_1++; else cnt_0++; } } if (!cnt_0 && cnt_1) .. 공감수 0 댓글수 0 2022. 7. 10.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.