본문 바로가기

Algorithm/Implementation

 (750)
(C++) - 백준(BOJ) 2028번 : 자기복제수 https://www.acmicpc.net/problem/2028 2028번: 자기복제수 어떤 자연수 N을 제곱했을 때, 그 제곱수의 맨 뒷자리에 원래의 수 N이 다시 나타나면, 우리는 그 수 N을 자기복제수라고 한다. 예를 들면, 5의 제곱은 52는 25이고 25의 맨 뒷자리에 원래의 수 5가 www.acmicpc.net 단순 구현문제였습니다. 풀이방법 1. 입력받은 수와 제곱수를 문자열로 바꿉니다. 2. 제곱수 문자열에서 입력받은 수의 문자열을 찾습니다. find함수를 통해 찾은 인덱스를 확인해서 마지막에 입력받은 수 문자열이 나온다면 YES, 아니라면 NO를 출력합니다. *find함수는 인자에 해당하는 값을 찾지 못했다면 string::npos를 반환합니다. Code #include using na..
(C++) - 프로그래머스(2020 KAKAO BLIND RECRUITMENT) : 기둥과 보 설치 https://programmers.co.kr/learn/courses/30/lessons/60061?language=cpp 코딩테스트 연습 - 기둥과 보 설치 5 [[1,0,0,1],[1,1,1,1],[2,1,0,1],[2,2,1,1],[5,0,0,1],[5,1,0,1],[4,2,1,1],[3,2,1,1]] [[1,0,0],[1,1,1],[2,1,0],[2,2,1],[3,2,1],[4,2,1],[5,0,0],[5,1,0]] 5 [[0,0,0,1],[2,0,0,1],[4,0,0,1],[0,1,1,1],[1,1,1,1],[2,1,1,1],[3,1,1,1],[2,0,0,0],[1,1,1,0],[2,2,0,1]] [[ programmers.co.kr 구현 문제였습니다. 풀이방법 set을 이용해 해결했습니다. ..
(C++) - 프로그래머스(2019 KAKAO BLIND RECRUITMENT) : 길 찾기 게임 https://programmers.co.kr/learn/courses/30/lessons/42892 코딩테스트 연습 - 길 찾기 게임 [[5,3],[11,5],[13,3],[3,5],[6,1],[1,3],[8,6],[7,2],[2,2]] [[7,4,6,9,1,8,5,2,3],[9,6,5,8,1,4,3,2,7]] programmers.co.kr Linked list로 graph를 만든뒤 전위, 후위 순위를 하는 문제였습니다. 풀이방법 1. 노드 번호를 nodeinfo에 추가해줍니다. i번째 nodeinfo는 i+1의 노드번호를 가집니다. 2. x축에 대해 오름차순으로 정렬해줍니다. 이러면 중간에 적절히 root에 해당하는 가장 큰 y값의 node가 위치하게 됩니다. 3. tree구조를 struct 형태로..
(C++) - 프로그래머스(2020 KAKAO BLIND RECRUITMENT) : 자물쇠와 열쇠 https://programmers.co.kr/learn/courses/30/lessons/60059# 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 구현 문제였습니다. 풀이방법 검은색 부분은 key이고 파란 부분은 lock입니다. 계속해서 오른편으로 이동하고 끝에 다다르면 한 칸 내려가 처음부터 시작해 다시 오른쪽으로가는 방법으로 열 수 있는지의 여부를 알아낼 수 있습니다. 1. expandedLock 배열을 만들어 lock을 50 * 50으로 넉넉하게 확장해줍니다. 그리고 (20 ~ 20 + 행)부터 (20번째 열 ~ 20 + lock.size()번째 ..
(C++) - 백준(BOJ) 17413번 : 단어 뒤집기 2 www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net stack이용한 구현문제였습니다. 풀이방법 3가지 경우에 단어가 stack에서 빠져나옵니다. 1. 현재 보는 문자가 ''인 경우 3. '공백' 또는 마지막 문자인 경우 1.의 경우 stack에 들어있는 문자들이 tag인 경우는 없으므로 (''가 번갈아 나오기 때문) 모두 뽑아 ans에 붙여줍니다. 2. ''포함 모두 뽑아내고 다시 뒤집어주어 원래 단어가 나오게 한 다음 ans변수..
(C++) - 백준(BOJ) 17406 : 배열 돌리기 4 www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 순열 + 구현 문제였습니다. 풀이방법 1. 매 연산마다 범위를 계산해 s와 함께 넣어줍니다. x1 : r - s, y1 : c-s, x2 : r + s, y2 : c + s 로 계산한 후 그 점들과 s를 op라는 변수에 vector형태로 넣어줍니다. 2. dfs형태로 모든 형태의 연산 순열을 뽑아냅니다. 한 연산의 순열을 뽑아냈다면 뽑아낸 순열을 comb라는 vector 변수에 저..
(C++) - 백준(BOJ) 21609번 : 상어 중학교 www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net bfs와 정렬을 구현하는 문제였습닌다. 풀이방법 1. 블록 그룹 넓이, 무지개 블록 개수, 기준 블록의 행,열을 struct로 하는 자료구조인 groups vector변수를 선언해줍니다. 그 외 기본적인 입력을 받을 board 등을 선언해줍니다. 2. 조건에 만족하는 블록 그룹의 기준 블록을 찾아줍니다. 무지개 블록은 공유될 수 있기 때문에 check이후 check해제해야합니다. 기준 블록을 찾았으면 gro..
(C++) - 백준(BOJ) 21608번 : 상어 초등학교 www.acmicpc.net/problem/21608 21608번: 상어 초등학교 상어 초등학교에는 교실이 하나 있고, 교실은 N×N 크기의 격자로 나타낼 수 있다. 학교에 다니는 학생의 수는 N2명이다. 오늘은 모든 학생의 자리를 정하는 날이다. 학생은 1번부터 N2번까지 번호 www.acmicpc.net 구현 문제였습니다. 풀이방법 1. x번 학생이 좋아하는 사람이 i,j자리에 앉아있으면 그 자리의 인접칸들중 비어있는 칸들마다 1씩 더해줍니다. 이런식으로 가중치를 부여하면 그 최대값과 같은 자리들을 possibleSeats vector변수에 넣어줍니다. 2. possibleSeats를 first, second 순으로 기준을 두어 오름차순으로 정렬합니다. 이들 좌표의 인접 칸에 대해 빈 칸들을 세주고 ..

티스토리툴바