티스토리

국밥 개발자

검색하기

블로그 홈

국밥 개발자

puk0806.tistory.com/m

차노도리 님의 블로그입니다.

구독자: 1

방명록 방문하기

주요 글 목록

[투포인터] 백준-1806 부분합 골드4 (Python) 백준-1806 : 부분합 https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀의 입력 받은 값의 구간합 배열을 만든다. 투포인터를 이용하여 왼쪽은 구간합 시작점 오른쪽은 구간합의 끝점으로 사용한다. 구간합의 값이 S 보다 작을 경우 오른쪽 포인터를 이동 목표 합 보다 크고 길이가 짧은 경우 정답을 갱신 구간합의 값이 S 보다 클 경우 왼쪽 포인터를 이동 한다. 구간 합을 못찾을 경우 0을 반환 코드 (Python) import sy.. 공감수 0 댓글수 1 2023. 11. 13.
[Graph] 백준-2252 줄 세우기 골드3 (Python) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀의 진입 차수를 담아줄 리스트를 초기화한다. 진출 정보를 담아줄 리스트를 초기화한다. 진입 차수가 0인 것들을 큐에 담아준다. 큐에 값을 꺼내면서 결과 리스트에 큐의 값을 넣어준다. 해당 큐의 값에 진출 정보를 담는 리스트에서 진출 정보를 꺼내면서 해당 진출 정보와 관련된 진입 차수를 줄여준다. 진입 차수가 0이라면 큐에 담아준다. 코드 (Python).. 공감수 0 댓글수 0 2023. 5. 25.
[Graph] 백준-14567 선수과목(Prerequisite) 골드5 (Python) https://www.acmicpc.net/problem/14567 14567번: 선수과목 (Prerequisite) 3개의 과목이 있고, 2번 과목을 이수하기 위해서는 1번 과목을 이수해야 하고, 3번 과목을 이수하기 위해서는 2번 과목을 이수해야 한다. www.acmicpc.net 진입 차수 : 특정한 노드로 들어오는 간선의 개수 진출 차수 : 특정한 노드에서 나가는 간선의 개수 풀의 진입 차수를 담아줄 리스트를 초기화한다. 진출 정보를 담아줄 리스트를 초기화한다. 진입 차수가 0인 것들을 큐에 담아준다. 큐에 값을 꺼내면서 해당 큐의 값에 진출 정보를 담는 리스트에서 진출 정보를 꺼내면서 해당 진출 정보와 관련된 진입 차수를 줄여준다. 큐의 값 이후에 진행되야 하므로 해당값의 결과보다 1보다 작다면.. 공감수 0 댓글수 0 2023. 5. 23.
[Graph] 백준-11558 The Game of Death 실버4 (Python) https://www.acmicpc.net/problem/11558 11558번: The Game of Death 첫 줄에는 테스트 케이스의 숫자 T가 주어지며, 이어서 T번에 걸쳐 테스트 케이스들이 주어진다. 매 테스트 케이스의 첫 줄에는 플레이어의 숫자 N(1 ≤ N ≤ 10,000)이 주어진다. 이어서 N줄에 걸쳐 www.acmicpc.net 풀의 각 플레이어가 가리키는 정보를 담을 테이블에 각플레이어가 가리키는 정보를 담아준다. 각 플레이어의 부모 테이블을 자기 자신으로 초기화 한다. 1번 플레이어부터 가리키는 플레이어를 체크한다. 마지막 플레이어를 발견하기 전에 사이클이 발생하면 사이클이 발생함으로 0을 리턴한다. 마지막 플레이어를 발견하면 이동하 횟수를 리턴한다. 코드 (Python) impo.. 공감수 0 댓글수 0 2023. 5. 21.
[DP(Dynamic Programming)] 백준-9251 LCS 골드5 (Python) 백준-9251 : LCS https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀의 두 문자를 글자마다 비교할 2차원 배열을 생성한다. 문자 하나를 기준을 잡는다. 두번째 문자열과 비교하면서 값을 업데이트 한다. 문자열이 동일한 경우 : 이전 dp의 1을 더한값을 저장한다. 문자열이 다른 경우 : 이전 좌표의 값들중 큰값을 저장한다. 코드 (Python) import sys def input(): retu.. 공감수 0 댓글수 0 2023. 5. 19.
[DP(Dynamic Programming)] 백준-1915 가장 큰 정사각형 골드4(Python) 백준-1915 : 가장 큰 정사각형 https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 풀의 1 되어있을 경우 좌, 우, 좌상 값중 가장 작은 값에 1을 더한 값으로 메트릭스 수정한다. 갱신 후 결과값보다 크면 결과 값을 갱신한다. 놓쳤던 부분 1행 1열 부터 확인하여 0행과, 0열에 1의 값이 있고 그외에 값이 0일때의 케이스를 놓쳤었음 코드 (Python) import sys def input(): return sys.stdin.readline().rstrip() n, m = map(int, input().spli.. 공감수 0 댓글수 0 2023. 5. 4.
[DP(Dynamic Programming)] 백준-14767 Flow Shop(Python) 백준-14767 : Flow Shop https://www.acmicpc.net/problem/14767 14767번: Flow Shop There is only one test case in each file. It begins with a single line containing N and M (1 ≤ N, M ≤ 1000), the number of swathers and stages (respectively). Following this are N lines, each with M integers. The j’th integer of the i’th line is Pi www.acmicpc.net 문제 n개의 스웨터 주문과, m개의 공정을 과정을 입력 받는다. 각 공정마다 기계는 한개씩 존재하고 .. 공감수 0 댓글수 0 2023. 4. 30.
[BFS,Deque] 백준-2206 벽 부수고 이동하기 골드2 (Python) 백준-2206 : 벽 부수고 이동하기 https://www.acmicpc.net/problem/2206 풀의 시작 점 부터 BFS 를 진행한다. BFS 를 진행하며 벽일 경우 벽을 아직 부수지 않았으면 벽을 부수고 진행한다. 벽을 부순 유물를 3차원으로 관리 코드 (Python) import sys from collections import deque read = sys.stdin.readline n, m = map(int, read().split(" ")) matrix = [list(map(int, read().rstrip())) for _ in range(n)] visited = [[[0] * 2 for _ in range(m)] for _ in range(n)] # 상 하 좌 우 dx = [0, 0.. 공감수 0 댓글수 0 2023. 4. 28.
[우선순위 큐] 백준-11000 강의실 배정 골드4 (Python) 백준-11000 : 강의실 배정 https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 풀의 입력 받은 강의 정보들을 시작 시간 기준으로 정렬한다. 우선순위 큐에 강의 정보의 첫번쨰 값의 끝나는 시간을 넣어준다. 강의 리스트를 순회하며 우선순위 큐의 첫번째 값보다 작다면 해당 강의실에서 강의 가능한 값이므로 끝나는 값으로갱신한다. 우선순위 큐의 첫번째 값보다 크다면 강의실을 하나더 추가해야 함으로 끝나는 값을 우선순위 큐에 넣어준다. 코드 (Python) import sys import heapq .. 공감수 0 댓글수 0 2023. 4. 26.
[투 포인트] 백준-2473 세 용액 골드3 (Python) 백준-2473 : 세 용액 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀의 투 포인트 알고리즘을 사용하기 위해 입력 받은 ph 정보를 정렬을 한다. 앞에서부터 기준을 하나씩 잡고 기준이 되는 음수값의 합을 구하기위해 투 포인트 알고리즘을 사용한다. 코드 (Python) import sys def input(): return sys.stdin.readline().rstrip() size = int(input()) ph_.. 공감수 0 댓글수 0 2023. 4. 21.
[이진 탐색] 백준-20551 Sort 마스터 배지훈의 후계자 실버4 (Python) 백준-20551 : Sort 마스터 배지훈의 후계자 https://www.acmicpc.net/problem/20551 20551번: Sort 마스터 배지훈의 후계자 지훈이는 Sort 마스터다. 오랫동안 Sort 마스터 자리를 지켜온 지훈이는 이제 마스터 자리를 후계자에게 물려주려고 한다. 수많은 제자들 중에 후계자를 고르기 위해서 지훈이는 제자들에게 문제 www.acmicpc.net 풀의 입력 받은 숫자들을 오름차순으로 정렬한다. 2진 탐색을 활용하여 가장 먼저 찾은 index를 반환하고 없으면 -1 을 반환 코드 (Python) import sys import bisect def input(): return sys.stdin.readline().rstrip() n, m = map(int, input(.. 공감수 0 댓글수 0 2023. 4. 19.
[우선순위큐,정렬] 백준-2109 순회강연 골드3 (Python) 백준-2109 : 순회강연 https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 풀이 입력 받은 정보를 날짜 순으로 정렬을 한다. 정렬한 데이터를 꺼내면서 우선순위 큐에 넣으며 우선순위 큐의 크기가 날짜보다 클경우 가장 작은 비용의 값을 꺼낸다. 코드 (python) import sys import heapq def input(): return sys.stdin.readline().rstrip() n = int(i.. 공감수 1 댓글수 0 2023. 4. 15.
[DFS] 백준-15173 점프왕 쩰리 (Small) 실버4 (Python) 백준-15173 : 점프왕 쩰리 (Small) https://www.acmicpc.net/problem/16173 16173번: 점프왕 쩰리 (Small) 쩰리는 맨 왼쪽 위의 칸에서 출발해 (행, 열)로 나타낸 좌표계로, (1, 1) -> (2, 1) -> (3, 1) -> (3, 3)으로 이동해 게임에서 승리할 수 있다. www.acmicpc.net 풀이 0,0에서 시작해서 해당 이동할수 있는 값 만큼 이동을하여 우측과 , 아래쪽을 확인하면서 DFS를 실행항 주의사항 좌표의 값이 0인 값도 있기 때문에 해당 부분은 제외해줌 코드 (python) import sys read = sys.stdin.readline n = int(read()) graph = [list(map(int, read().split.. 공감수 0 댓글수 0 2023. 4. 14.
[그리디,이진 탐색] 백준-8983 사냥꾼 골드4 (Java) 백준-8983 : 사냥꾼 https://www.acmicpc.net/problem/8983 8983번: 사냥꾼 KOI 사냥터에는 N 마리의 동물들이 각각 특정한 위치에 살고 있다. 사냥터에 온 사냥꾼은 일직선 상에 위치한 M 개의 사대(총을 쏘는 장소)에서만 사격이 가능하다. 편의상, 일직선을 x-축이라 가 www.acmicpc.net 아이디어 모든 동물들을 X축이 가장 가까운 사대를 확인하며 사냥 가능한 동물한 수를 파악한다. 풀의 사대를 입력 받고 2분 탐색을 위해 정렬을 진행한다. 가장 가까운 사대를 찾고 사냥 가능한 거리 안에 있으면 사냥 가능 동물을 증가 시킨다. 코드 (java) package Greedy.Baejoon8983; import java.io.BufferedReader; impor.. 공감수 0 댓글수 0 2023. 4. 13.
[BFS] 백준-10610 30 실버4 백준-10610 : 30 https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 아이디어 30의 배수 3의 배수이면서 10의 배수 3의 배수 조건 : 각자리 합이 3의배수 10의배수 조건 1의 자리의 숫자가 0 풀의 숫자를 입력받은 후 각자리 합을 더하면서 우선순위 큐에 넣는다. 우선순위 큐에서 꺼낸면서 결과에 더한 후 1의 자리가 0인지 확인한다. 코드 (java) package Bfs.Baejoon2437; import java.util.*; pub.. 공감수 0 댓글수 0 2023. 4. 11.
[BFS] 백준-2437 저울 골드2 백준-2437 : 저울 https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 풀의 입력 받은 숫자들은 오름차순 정렬을 한다. 누적 합(SUM)을 구하면서 그 다음 숫자가 누적합보다 2보다 클 경우 SUM+1 값을 측정할수 없는 값 이다. 코드 (java) import java.util.*; public class Baejoon2437 { public static void main(String[] args) { Scanner sc = new Scanner(Sys.. 공감수 0 댓글수 1 2023. 4. 10.
[BFS] 백준-1339 단어 수학 골드4 백준-1339 : 단어 수학 https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 풀의 입력받은 단어를 입력받은 알파벳들을 알파벳 별로 얼마나 입력 받았는지 기록한다. 우선 순위 큐에 넣은 뒤 큰 값부터 꺼내어 가중치를 9부터 1씩 줄이면 곱해준다. 코드 (java) import java.util.*; public class Baejoon1339 { public static void main(String[] args) { Scanner sc =.. 공감수 0 댓글수 0 2023. 4. 9.
[BFS] 백준-7576 토마토 골드5 백준-7576 : 토마토 https://www.acmicpc.net/problem/7576 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 풀의 익어있는 토마토들을 넣어주고 BFS를 진행 BFS를 진행할때 익어있는 경우 현재 값에 1을 더해서 경과를 표시 더 작은값일 경우 값 갱신 초기 익어있는 토마토값이 1이므로 총 경과일은 가장 큰 값에서 1을 뺀 값을 리턴 코드 (java) import java.util.*; class Baejoon7576Node { private int x; priva.. 공감수 0 댓글수 1 2023. 4. 8.
[해시] 백준-9375 패션왕 신해빈 실버3 (Java) 백준-9375 : 패션왕 신해빈 https://www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 풀의 입력받은 옷을 종류별로 카운트 조합을 이용하여 입을수 있는 방법의 수를 구한다(안 입는 경우는 제외) 코드 (java) import java.util.HashMap; import java.util.Scanner; public class Baejoon9375 { publ.. 공감수 0 댓글수 1 2023. 4. 8.
[완전 탐색] 백준-12100 2048 (Easy) 골드2 (Java) 백준-12100 : 2048(Easy) https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 아이디어 5번만 슬라이딩 가능하니 4방향 4*4*4*4*4 모두 진행해도 1024번 바께 안돼서 완전 탐색해도 괜찮다고 생각함 주의 사항 똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 풀의 모든 슬라이드 경우의 수를 진행한다. 슬라이드 진행후 가장 최대값을 확인하며 갱신해준다. 코드 (java) i.. 공감수 0 댓글수 0 2023. 4. 6.
[완전 탐색, BFS] 백준-14502 연구소 골드4 (Java) 백준-14502 : 연구소 https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 아이디어 최대 8*8 matrix에 기둥을 3개 세우는 거니 64*64*64 백만번이 안돼서 완전 탐색해도 괜찮다고 생각함 풀이 입력받은 matrix에 0(빈곳)에 벽을 세우는 모든 경우의 수를 확인한다. 벽을 세운 이후 BFS를 통해서 바이러스를 확장시킨다. 모든 경우의수를 확인하면 안전지대의 수가 가장 많은 값을 반환한다. 코드 (java) import java.util.*; c.. 공감수 0 댓글수 0 2023. 4. 5.
[Stack] 백준-10773 제로 실버4 (Java) 백준-10773 제로 https://www.acmicpc.net/problem/10773 10773번: 제로 첫 번째 줄에 정수 K가 주어진다. (1 ≤ K ≤ 100,000) 이후 K개의 줄에 정수가 1개씩 주어진다. 정수는 0에서 1,000,000 사이의 값을 가지며, 정수가 "0" 일 경우에는 가장 최근에 쓴 수를 지우고, 아닐 경 www.acmicpc.net 풀이 Stack에 0이 아니면 넣어주고 0일 경우에 Stack에서 꺼내준다. 코드(JAVA) import java.util.*; public class Baejoon10773 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nex.. 공감수 0 댓글수 0 2023. 4. 5.
[그리디] 백준-1744 수 묶기 골드4 (Java) 백준-1744 : 수 묶기 https://www.acmicpc.net/problem/1744 1744번: 수 묶기 길이가 N인 수열이 주어졌을 때, 그 수열의 합을 구하려고 한다. 하지만, 그냥 그 수열의 합을 모두 더해서 구하는 것이 아니라, 수열의 두 수를 묶으려고 한다. 어떤 수를 묶으려고 할 때, 위치에 www.acmicpc.net 아이디어 1을 제외한 양수는 큰수끼리 곱하면 커진다. 1은 더 해준다. 음수 * 음수는 양수이고 작은 음수끼리 곱하면 커진다. 풀이 아래 조건에 따라 우선순위 큐에 넣어준다. 1은 결과에 더해준다. 1보다큰 값끼리 우선순위큐에 넣어준다. 1보다 작은값 끼리 우선순위 큐에 넣어준다. 우선순위 큐에 2개 이상 존재할때 곱하여 결과에 더해주고 1개의 경우에는 꺼내서 더해준다.. 공감수 0 댓글수 0 2023. 4. 4.
[그리디] 백준-1715 카드 정렬하기 골드4 (Java) 백준 1715번 : 카드 정렬하기 https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 풀이 입력받은 값을 우선 순위 큐에 넣는다. (정렬을 하기 위해) 우선 순위 큐에 2개 이상 존재할 때 두개를 꺼내서 합한 이후에 다시 우선순위 큐에 넣는 것을 반복한다. 코드 (java) import java.util.*; public class Baejoon1715 { public static void main(String[] args) { Sc.. 공감수 0 댓글수 0 2023. 4. 2.
[그리디] 백준-1439 뒤집기 실버5 (Java) 백준 1439번 : 뒤집기 https://www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 풀이 앞 숫자와 비교하여 변화한 수 체크 변화 한 수의 절반의 올림 값 만큼 변화가 필요함 코드 (java) import java.util.*; public class BaeJoon1439 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String num = sc.nextLi.. 공감수 0 댓글수 0 2023. 4. 2.

문의안내

티스토리
로그인
고객센터

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