[BOJ] 백준 2606 바이러스 / 너비 우선 탐색(BFS)

💣 문제 이해 1번 컴퓨터에 바이러스가 감염되면 이와 연결되어 바이러스에 감염되는 컴퓨터의 수를 구하는 문제이다. 1번 컴퓨터(노드)에 연결된 컴퓨터(노드) 개수를 구하면 된다. 너비 우선 탐색(BFS) 기법으로 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include #include using namespace std; int visited[101] = {0, }; int bfs(deque nodes) { int virused = 0; deque queue; // 1번 컴퓨터에서 시작, 방문 처리 queue.push_back(1); visited[1] = 1; while (!queue.empty()) { int now_node = queue.front(); queue.pop_fron..

→2020.11.05

[2020 KAKAO BLIND RECRUITMENT] 문자열 압축

💣 문제 이해 문자열 처리를 필요로 하는 문제이다. 주어진 문자열에서 1개 단위, 2개 단위, 3개 단위, 등으로 문자열을 자를 때, 연속된 문자열을 2a2ba3c와 같이 압축한다. 연속된 문자가 1 자리인 경우, 앞에 숫자를 생략하고 문자만 기입한다. 💭 풀이 과정 작성 언어: Python3 def solution(s): answer = 9999 size = len(s) # 한 자리 문자열의 경우 바로 결과 출력 if size == 1: return 1 for i in range(1, size // 2 + 1): temp = s[:i] count = 0 compressed = '' for x in range(0, size, i): if s[x:x + i] == temp: count += 1 else: ..

→2020.09.01

[BOJ] 백준 7576 토마토 / 너비 우선 탐색(BFS)

💣 문제 이해 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성한다. 너비 우선 탐색(BFS) 기법으로 풀이했다. 💭 풀이 과정 작성 언어: Python from collections import deque def bfs(t_m, t_n, t_box): day = -1 mx = [-1, 1, 0, 0] my = [0, 0, -1, 1] while riped_index: # 하루 씩 증가 day += 1 queue_size = len(riped_index) for _ in..

→2020.08.31

[2018 KAKAO BLIND RECRUITMENT] 다트 게임

💣 문제 이해 문자열 처리를 필요로 하는 문제이다. 카카오에서는 정말 빠질 수 없나봄... 총 3번의 게임이 있고 각 게임마다 0~10점의 정수형 점수, S/D/T로 각 1제곱, 2제곱 3제곱을 하는 영역 점수, 옵션으로 * 또는 #이 주어진다. *는 해당 점수와 바로 전에 얻은 점수를 각 2배로 만들고, #는 해당 점수를 마이너스로 만든다. 첫 번째 기회에서 *가 나온 경우, 이전 점수가 없으므로 해당 점수만 2배가 된다. 정규표현식을 사용해서 언급된 규칙에 따라 문자열을 나눠 처리했다. 💭 풀이 과정 작성 언어: Python3 import re def solution(t_dartresult): score_list = [1, 1, 1] groups = re.findall(r'\d{1,2}[SDT][*#..

→2020.08.29

[2019 KAKAO BLIND RECRUITMENT] 실패율

💣 문제 이해 정렬을 이용하는 게 포인트인듯한 문제이다. 딕셔너리를 사용했고, Key 값은 1~N까지의 스테이지 번호, Value 값은 각 스테이지의 실패율을 담는다. 딕셔너리의 Value 값인 실패율을 key 로 하여 내림차순 정렬을 수행한다.정렬된 딕셔너리의 Key 값이 문제에서 요구하는 순위가 된다. 💭 풀이 과정 작성 언어: Python3 import operator def solution(t_n, t_stages): answer = [] user_left = len(t_stages) stages_dict = {num: 0 for num in range(1, t_n + 1)} # 실패율 계산 for key in stages_dict.keys(): if user_left != 0: user_cnt ..

→2020.08.29

[2018 KAKAO BLIND RECRUITMENT] 비밀지도

💣 문제 이해 먼저 입력으로 받은 배열의 10진수를 2진수로 변환한다. 부족한 자리는 0으로 채운다. 이후, 2진수들로 채워진 배열을 하나 씩 선택하여 각 자리를 비교한다. 두 자리 중 하나라도 1이면 #, 두 자리 다 0이면 공백이 된다. 즉, OR연산을 수행하는 것이다. 그렇게 생성된 문자열 리스트를 반환한다. 💭 풀이 과정 arr1 = [9, 20, 28, 18, 11] arr2 = [30, 1, 21, 17, 28] 는 아래와 같이 변하게 된다. arr1 = ['01001', '10100', '11100', '10010', '01011'] arr2 = ['11110', '00001', '10101', '10001', '11100'] 첫 번째 인덱스에 위치한 arr1의 "01001"과 arr2의 "..

→2020.08.28

[2020 카카오 인턴십 for Tech developers] 키패드 누르기

💣 문제 이해 [1, 4, 7] 은 무조건 왼손으로 터치한다. [3, 6, 9] 는 무조건 오른손으로 터치한다. 가운데에 위치한 [2, 5, 8, 0] 은 더 가까운 곳에 있는 손가락이 터치한다. 번호를 키(Key) 값으로, 행, 열 번호 리스트를 값(Value)으로 하는 딕셔너리를 선언해두고, 현재 번호와 양 손가락의 거리 차이의 절댓값을 비교하여 더 값이 작은 손가락이 터치하는 것으로 한다. 💭 풀이 과정 작성 언어: Python3 def solution(numbers, hand): num_dict = { 1: [0, 0], 2: [0, 1], 3: [0, 2], 4: [1, 0], 5: [1, 1], 6: [1, 2], 7: [2, 0], 8: [2, 1], 9: [2, 2], 0: [3, 1] }..

→2020.08.27

[BOJ] 백준 1935 후위 표기식2 / 스택(Stack)

💣 문제 이해 후위 표기식과 각 피연산자에 대응하는 값들이 주어질 때, 그 식을 계산하는 문제이다. 스택(Stack)을 활용하여 풀이했다. 💭 풀이 과정 작성 언어: C++ #include #include using namespace std; int main() { string operation = ""; int numCnt = 0; int alphabet[30] = {0, }; stack oper_Stack; // 입력의 수와 후위 표기식 입력받기 cin >> numCnt >> operation; // 피연산자에 대응하는 값 입력받기 for (int i = 0; i > alphabet[i]; } for (int i = 0; i < operation.length()..

→2020.07.27

[BOJ] 백준 1918 후위 표기식 / 스택(Stack)

💣 문제 이해 후위 표기법(postfix)은 연산자가 피연산자 뒤에 위치하는 방법이다. 예를 들어 a+b*c를 후위 표기식으로 바꾸면 abc*+가 된다. 중위 표기식이 주어졌을 때 후위 표기식으로 고치는 프로그램을 작성한다. 스택(Stack)을 활용하여 풀이했다. 💭 풀이 과정 C++ Stack 라이브러리를 참조하여 중위 표기법을 구현하였다. 작성 언어: C++ #include #include using namespace std; int main() { string expression = ""; stack s1; cin >> expression; for (int i = 0; i = 60) { // 피연산자 출력(모든 ..

→2020.07.18

[BOJ] 백준 10828 스택 / 스택(Stack)

💣 문제 이해 정수를 저장하는 스택을 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성한다. 명령은 push, pop, top, size, empty로 총 다섯 가지이다. 스택(Stack) 단순 구현 문제이다. 💭 풀이 과정 C++ template을 활용하여 Linked-List로 스택을 구현하였다. 작성 언어: C++ #include using namespace std; template class Node { public: T value; Node *next; Node(): next(nullptr){} Node(T tValue, Node *tNext): value(tValue), next(tNext){} }; template class Stack { public: int size; Nod..

→2020.07.17