본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ) 3078번 : 좋은 친구 www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 이분탐색 문제였습니다. 풀이방법 1. map 자료구조 m을 선언합니다. key엔 이름길이, value는 해당 이름길이를 가진 학생들의 등수들이 담긴 vector입니다. 2. m의 크기만큼 loop를 돕니다. 매 이름 길이마다 좋은 친구의 순서쌍을 변수 ans에 더해줍니다. 현재 index에서 k만큼 더한 v[i] + k를 초과하는 등수를 가진 친구가 처음나오는 index를 찾습니다. 찾게 된..
(C++) - 백준(BOJ) 3190번 : 뱀 www.acmicpc.net/problem/3190 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net deque을 이용한 시뮬레이션 문제였습니다. 📕 풀이방법 📔 입력 및 초기화 deque snake를 선언합니다. 뱀의 머리는 front(), 뱀의 꼬리는 back()이라고 생각합니다. 한 원소의 자료형은 Snake라는 x,y 좌표 정보를 가지고 있는 구조체입니다. 뱀의 몸통에 부딪혀 게임이 종료될 수 있기때문에 뱀의 형태를 모두 저장해야 하기 때문입니다. 입력을 받습니다. 사과가 있는 위치는 1로만들어주고, map자료..
(C++) - 프로그래머스(2019 KAKAO BLIND RECRUITMENT) : 실패율 programmers.co.kr/learn/courses/30/lessons/42889?language=cpp# 코딩테스트 연습 - 실패율 실패율 슈퍼 게임 개발자 오렐리는 큰 고민에 빠졌다. 그녀가 만든 프랜즈 오천성이 대성공을 거뒀지만, 요즘 신규 사용자의 수가 급감한 것이다. 원인은 신규 사용자와 기존 사용자 사이에 스 programmers.co.kr 간단한 구현문제였습니다. 풀이방법 1. map에 스테이지별로 도전하고 실패한 사람을 세줍니다. (key,value) = (스테이지, 실패자 수) 입니다. 2. 실패율을 구해 vector 변수에 loseRatio 저장합니다. 실패율은 다음과 같습니다. 스테이지 i-1까지 도전한 사람들의 누적 수를 구해줍니다. 현재 스테이지 / (총 인원 - 누적 수)가..
(C++) - 백준(BOJ) 16928번 : 뱀과 사다리 게임 www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x > m; for(int i = 0; i < n + m; i++){ ..
(C++) - 백준(BOJ) 21318번 : 피아노 체조 www.acmicpc.net/problem/21318 21318번: 피아노 체조 피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 www.acmicpc.net 부분합 문제였습니다. 풀이방법 1. 악보 1부터 실수를 할 때마다 배열 d의 i+1번에 실수횟수를 1더해서 저장해줍니다. 2. d[end] - d[start]시 해당 구간 사이의 실수횟수를 구할 수 있습니다. Code #include #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std; int n, ..
(C++) - 프로그래머스(2021 KAKAO BLIND RECRUITMENT) : 메뉴 리뉴얼 programmers.co.kr/learn/courses/30/lessons/72411?language=cpp 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr backtracking으로 푼 문제였습니다. 풀이방법 1. orders의 문자열 하나씩을 확인하여 정렬합니다. 이런식으로 정렬한다면 세번째 예제에서 'XWY'는 'WXY'로 정렬됩니다. 2. map으로 모든 orders문자열들을 보면서 각 알파벳이 몇 개씩 나왔는지 세줍니다. 2개 이상나온 알파벳들을 합쳐 새로운 문자열 candidates를 만들어 줍니다..
(C++) - 프로그래머스(고득점 kit - 그래프) : 순위 programmers.co.kr/learn/courses/30/lessons/49191 코딩테스트 연습 - 순위 5 [[4, 3], [4, 2], [3, 2], [1, 2], [2, 5]] 2 programmers.co.kr 플로이드 와샬 문제였습니다. 풀이방법 1. 누가 누구를 이겼는지에 대한 정보를 담을 2차원 배열 gameInfo라는 변수를 선언합니다. i선수가 j선수를 이겼다면 gameInfo[i][j] = 1이 됩니다. 2. 플로이드 와샬을 수행해서 누락된 승부 정보를 알아냅니다. 만약 i가 k를 이겼고 k가 j를 이겼다면 삼단논법에 의해 i는 j를 이긴것이 됩니다. 3. i가 j를 이겼거나 i가 j에게 패배했다면 그 개수를 세줍니다. 예를들어 2번 선수의 순위가 도출되려면 1,3,4,5번 선수..
(C++) - 프로그래머스(고득점 kit - 그래프) : 가장 먼 노드 programmers.co.kr/learn/courses/30/lessons/49189 코딩테스트 연습 - 가장 먼 노드 6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3 programmers.co.kr bfs문제였습니다. 풀이방법 1. 주어진 간선들이 단방향으로 주어지기 때문에 양방향 인접 그래프로 변환해줍니다. 2. 1번 노드에서 시작하여 bfs를 시행합니다. 연결된 노드들까지의 최소거리를 dist배열에 저장합니다. 2. 가장 먼 노드까지의 거리를 저장합니다. 3. 해당거리와 같은 거리의 노드들의 개수를 세줍니다. Code #include #define MAX 0x3f3f3f3f using namespace std; int bfs(vector..

티스토리툴바