본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 1952번 : 달팽이 https://www.acmicpc.net/problem/1952 1952번: 달팽이2 M줄 N칸으로 되어 있는 표 위에, 달팽이 모양으로 선을 그리려고 한다. 위의 그림은 M=5, N=3의 예이다. 이제 표의 왼쪽 위 칸(ㅇ)에서 시작하여, 오른쪽으로 선을 그려 나간다. 표의 바깥 또는 이미 www.acmicpc.net 구현문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1행 1열부터 시작한다는 의미로 curR = 1, curC = 1로 저장합니다. 이 후 지나온 길을 다시가지 않기 위해 2차원 배열 ck를 선언합니다. 📔 풀이과정 그리기가 끝나는 시점은 방향을 바꾼 후 그 방향으로 갔을 때에도 이미 그린 선인 경우입니다. 1. 현재방향 dir에 대해 curR, curC를 갱신합니다. 2. 벽에 부딪히거..
(C++) - 백준(BOJ) 17143번 : 낚시왕 https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 구현 문제였습니다. 📕 풀이방법 구조화, 갱신 시점을 꼼꼼히 처리해줘야합니다. 📔 입력 및 초기화 1. 상어의 정보를 가지고 있는 구조체 Shark를 선언합니다. 2. 각 상어의 정보를 가지고 있을 vector 변수 shark를 선언합니다. m을 입력받은 후 resize해줍니다. 3. 낚시왕의 좌표를 저장할 구조체 King을 선언합니다. 이에 해당하는 변수는 fishKing입니..
(C++) - 백준(BOJ) 11265번 : 끝나지 않는 파티 https://www.acmicpc.net/problem/11265 11265번: 끝나지 않는 파티 입력의 첫 번째 줄에는 파티장의 크기 N(5 ≤ N ≤ 500)과 서비스를 요청한 손님의 수 M(1 ≤ M ≤ 10,000) 이 주어진다. 각각의 파티장은 1번부터 N번까지 번호가 붙여져 있다. 다음에는 N개의 줄에 걸 www.acmicpc.net floyd warshell문제였습니다. 📕 풀이방법 O(n^3)의 시간복잡도를 가지기 때문에 효율적이지는 않으나 n이 적절히 작을 경우 구현이 간편하기 때문에 자주 사용합니다. 📔 입력 및 초기화 인접그래프를 party라는 이 차원 배열에 입력받습니다. 이후 n, m만큼 적절히 입력받습니다. m만큼 각각 a,b,c를 입력했다면 party[a][b]는 a에서 b로..
(C++) - 백준(BOJ) 15723번 : n단 논법 https://www.acmicpc.net/problem/15723 15723번: n단 논법 m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다. www.acmicpc.net bfs로 해결한 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. 삼단논법을 그래프로 빗대어 설명하자면 a에서 b로가는 길이 있고 b에서 c로가는 길이 있는 경우에 a에서 c로가는 길이 있음이 자명합니다. 2. 적절히 입력을 받아 유향 인접 그래프를 형성합니다. 📔 풀이과정 1. m개의 질문에 대해 다음을 수행합니다. 1-1. getline으로 한줄 입력받고 x,y 문자변수에 해당하는 질문 알파벳을 저장합니다. 1..
(C++) - 백준(BOJ) 1689번 : 겹치는 선분 https://www.acmicpc.net/problem/1689 1689번: 겹치는 선분 첫째 줄에는 선분의 개수(1 ≤ N ≤ 1,000,000)가 입력으로 들어온다. 그 다음 N개의 줄에 선분의 시작 좌표와 끝나는 좌표가 입력으로 들어온다. 선분의 좌표는 절댓값이 10억보다 작거나 같은 정수 www.acmicpc.net priority_queue를 이용한 sweeping 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 1. 선분 시작좌표, 선분 끝 좌표를 pair로 한 vector형 자료구조 v를 선언하고 n만큼 입력받습니다. 2. v를 오름차순으로 정렬해줍니다. 기준은 first먼저 그 다음 second로 정렬됩니다. 3. min heap인 priority_queue 변수 pq를 선언해줍니다. 4...
(C++) - 프로그래머스(위클리 챌린지) : 2주차 https://programmers.co.kr/learn/courses/30/lessons/83201 코딩테스트 연습 - 2주차 [[100,90,98,88,65],[50,45,99,85,77],[47,88,95,80,67],[61,57,100,80,65],[24,90,94,75,65]] "FBABD" [[70,49,90],[68,50,38],[73,31,100]] "CFD" programmers.co.kr 단순 구현문제였습니다. 📕 풀이방법 📔 풀이과정 1. 한 열에 대해 최댓값, 최솟값을 찾습니다. 2. 중복 여부를 확인하기 위해 최댓값, 최솟값들의 개수를 각각 세줍니다. 3. 다시 한 열에 대해 최소 또는 최댓값이 유일하다면 sum에 더하지 않고 평균을 구할 때도 나누는 인원수에서 1을 제해야합니다...
(Rust) - 백준(BOJ) 1000번 : A + B https://www.acmicpc.net/problem/1000 1000번: A+B 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net a, b를 입력받고 a+b를 출력하는 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 한 줄의 문자열을 입력받습니다. 📔 풀이과정 numbers에 공백을 제거하고 숫자만 collect해서 담습니다. 📔 정답출력 문자열 형태의 number_a, number_b의 합을 출력합니다. 📕 Code use std::io; fn main() { let mut input_number = String::new(); io::stdin().read_line(&mut input_number) .expect("Falied to read l..
(C++) - 백준(BOJ) 1240번 : 노드사이의 거리 https://www.acmicpc.net/problem/1240 1240번: 노드사이의 거리 N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라. www.acmicpc.net bfs로 푼 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 인접리스트로 트리를 구현합니다. 📔 풀이과정 플로이드 와샬은 1000^3의 시간복잡도가 걸리므로 시간초과가 될 수 있습니다. 따라서 매 출발과 도착점을 입력받을 때마다 출발점을 기준으로 거리를 구해줍니다. 1. 출발점과 도착점의 입력 후에 해당 부분으로 bfs를 수행합니다. 2. 트리에는 사이클이 없으므로 방문하지 않은 정점까지의 거리는 인접정점에서 그 정점으로 가는 거리를 더한 값이..

티스토리툴바