Problem Solving in C++

This is where I leave my problem solving process and the c++ solution code.

Solved Problems

Problem #1: kick start

Problem #2: maximum coins

Problem #3: combination lock

Problem #4: allocation

Problem #5: plates

Problem #6: workout

Problem #7: two sum

Problem #8: palindrome number

Problem #9: reverse integer

Problem #10: city finding

Problem #11: eureka

Problem #12: decomposition sum

Problem #13: maze escape

Problem #14: laboratory

Problem #15: contagion

Problem #16: merge sort

Problem #17: moving blocks

Problem #18:

Problem #1

Problem Link

Kick Start 2020 RoundG - Kick Start

Solution process

1. Count number of a word "kick" from the begining of the sentence.
2. When a word "start" shows up, add number of a word "kick" to the answer.

Note

1. Make sure the substr input is covered in the string size.
2. Don't make extra unneccessary addition in scanning characters.

Solution Code

kick_start.cpp

Problem #2

Problem Link

Kick Start 2020 RoundG - Maximum Coins

Solution process

1. Calculate every possible candidates.
2. Update the maximum result to the answer.

Note

Make sure the possible maximum is covered in the type of int.

Solution Code

maximum_coins.cpp

Problem #3

Problem Link

Kick Start 2020 RoundG - Combination Lock

Solution process

1. Calculate the number of moves wheels have to make for every numbers(1-N).
2. Update the minimum value.

Note

1. Be careful of data type choices.

Unsolved

1. I get a TLE for the second testcase.
2. I asked about it on Stack Overflow.(deleted)

Solution Code

combination_lock.cpp

Problem #4

Problem Link

Kick Start 2020 RoundA - Allocation

Solution process

1. Sort house prices in ascending order.
2. Get the maximum number of houses under buget.

Solution Code

allocation.cpp

Problem #5

Problem Link

Kick Start 2020 RoundA - Plates

Solution process

1. Try every combination of number of plates to take from each stack.
2. Update the maximum value.

Note

1. Combination with repitition : Implementable with DFS algorithm(back tracking)

Unsolved

1. I get a TLE for the second testcase.
2. I wonder what could be a faster algorithm than DFS that I used.

Solution Code

plates.cpp

Problem #6

Problem Link

Kick Start 2020 RoundA - Workout

Solution process

Note

Solution Code

workout.cpp

Problem #7

Problem Link

LeetCode - Two Sum

Solution process

1. Sort input numbers in an ascending order.
2. Check if two sum equals to target number until two sum is smaller than the target number.

Solution Code

two_sum.cpp

Problem #8

Problem Link

Leet Code - Palindrome Number

Solution Process

1. Cast int to string.
2. Check if front characters are the same as back characters.

Solution Code

palindrome_number.cpp

Problem #9

Problem Link

Leet Code - Reverse Integer

Solution Process

1. Check the integer sign.
2. Find the lowest digit of input.
3. Update reverse number.
4. Divide input by 10.(Delete the used digit of input.)
5. Check overflow before multiplying reverse number by 10.
6. Repeate.

Solution Code

reverse_integer.cpp

Problem #10

Problem Link

BAEKJOON - 특정거리의 도시 찾기(City Finding)

Solution Process

DFS

1. Put first node(city) to visit and check as visited.
2. Find the adjacent nodes and visit if those exists. If not, pop the first node.
3. Repeate until stack is empty.

Solution Code

city_finding_DFS.cpp

city_finding_BFS.cpp

Problem #11

Problem Link

BAEKJOON - 유레카 이론(Eureka)

Solution Process

DFS

1. Put first node(city) to visit and check as visited.
2. Find the adjacent nodes and visit if those exists. If not, pop the first node.
3. Repeate until stack is empty.

Solution Code

eureka.cpp

Problem #12

Problem Link

BAEKJOON - 분해합(decomposition sum)

Solution Process

DFS

1. Put first node(city) to visit and check as visited.
2. Find the adjacent nodes and visit if those exists. If not, pop the first node.
3. Repeate until stack is empty.

Solution Code

decomposition_sum.cpp

Problem #13

Problem

Maze Escape

Dongbin is trapped in a NxM size rectangular maze. There lives several monsters that he needs to avoid to escape. In the beginning, Dongbin is located in cell (1,1) and the exit is located in cell (N,M). 0s are put in the cells with monsters and, 1s are put in cells without monsters. How many moves in minimum should he make to escape from the maze? You should count the starting and the finishing cells in the final answers.

Solution Process

BFS

1. Put first node to visit and check as visited.
2. Put every adjacent nodes that is not visited yet and pop the current node.
3. Repeate until queue is empty.

Solution Code

maze_escape.cpp

Problem #14

Problem Link

BAEKJOON - 연구소(laboratory)

Solution Process

DFS and BFS

1. get the input map (0:blank 1:wall 2:virus)
2. Choose 3 blank spaces to place the wall.(DFS)
3. Save the temporary map with the 3 additional walls
4. Spread virus all over to the temporary map.(BFS)
5. Compare the number of safe places with the answer candidate.
6. Update the answer if the number is bigger than the answer candidate.

Solution Code

laboratory.cpp

Problem #15

Problem Link

BAEKJOON - 경쟁적 전염(contagion)

Solution Process

Search

1. Get the input map and push points with virus presents.
2. Spread virus for S seconds in ascending order. (BFS)
3. Print the value of map[Y-1][X-1];

Solution Code

contagion.cpp

Problem #16

Problem

Solve the sorting problem with merge sort algorithm.

Solution Process

Merge

1. Set input parameters as an unsorted array, the initial, middle, and end points.
2. Set indices for the former array (i) and the latter array (j).
3. Set a new index k as the initial point.
4. While i <= middle point and j <= end point, compare each array's element in the index and put smaller element in the sorted array's kth index.
5. If while statement breaks, push the residual array's leftovers in the sorted array.

Recursive function

1. Set input parameters as an unsorted array, the initial point and the end point.
2. Check if the size of the array is greater than 1.
3. If the size of the array is greater than 1, calculate the middle point.

• Call each recursive function giving the array ahead of the middle point and behind.
• After the dividing and conquering, merge those divided and sorted arrays.

Solution Code

mergesort.cpp

Problem #17

Problem

Programmers - 블록 이동하기(Moving Blocks)

Solution Process

BFS

1. The solution must give the minimum value that needs BFS algorithm to solve.
2. Queue is used to implement BFS Algorithm

• Unsolved yet.

Solution Code

moving_blocks.cpp moving_blocks.py moving_blocks_v2.py