구현 Implementation
- 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정
- Problem - Thinking - Solution
유형
- 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제
예시
- 알고리즘은 간단하지만 코드가 지나치게 긴 문제
- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제
- 문자열을 특정한 기준에 따라 끊어 처리해야 하는 문제 (파이썬이 상대적으로 편함)
- 적절한 라이브러리를 찾아 사용해야 하는 문제 (ex. 모든 순열과 모든 조합을 찾는 문제 등)
많은 연습이 필요
행렬
for i in range(5):
for j in range(5):
print('(', i, ',', j, ')')
print()
2차원 공간에서의 방향벡터 (이동)
# 동, 북, 서, 남의 방향벡터 정의
dx = [0, -1, 0, 1] #dx는 세로축!!!
dy = [1, 0, -1, 0] #dy는 가로축!!!을 의미한다
#현재위치
x, y = 2, 2
for i in range(4):
# 다음 위치
nx = x + dx[i] #행 방향으로는 어떤 방향으로 이동하는지 설정할 수 있고
ny = y + dy[i] # 열 또한 dy이용해서 어떤 방향으로 이동할지 설정할 수 있다
print(nx, ny) 상하좌우 문제
여행가 A는 N x N 크기의 정사각형 공간위에 서 있다. 가장 왼쪽 위 좌표는 (1,1) 이며, 가장 오른쪽 아래 좌표는 (N, N)에 해당한다. 상, 하, 좌, 우 방향으로 이동할 수 있으며 시작 좌표는 항상 (1, 1).
- L : 왼쪽으로 한 칸 이동
- R : 오른쪽으로 한 칸 이동
- U : 위로 한 칸 이동
- D : 아래로 한 칸 이동
입력
- 첫째 줄에 공간의 크기 나타내는 N 주어짐
- 둘째 줄에 여행가 A가 이동할 계획서 내용 주어짐
출력조건
- 첫째 줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X, Y)를 공백으로 구분하여 출력.
python
# 연산횟수는 이동횟수에 비례
# O(N) 시간복잡도이므로 넉넉한 편이다.
#N을 입력받자
n = int(input())
x, y = 1, 1
plans = input().split()
# 방향벡터를 명시해주기 위해
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D'] # 방향을 각각 리스트에 담음
# 이동 계획을 하나씩 확인
for plan in plans:
# 이동 후 좌표를 구한다
for i in range(len(move_types)): # 현재의 이동계획이 move_types 중 어떤 것인지 확인한다
if plan == move_types[i]:
nx = x + dx[i] # (현재 위치 + 이동해야 하는 방향) 더한 값을 다음 위치에 넣어준다
ny = y + dy[i]
#공간을 벗어나는 경우에는 무시한다
if nx < 1 or ny < 1 or nx > n or ny > n:
continue
# 이동을 수행한다
x, y = nx, ny
print(x, y) # 모든 이동 계획을 하나씩 확인하며 이동한 결과를 출력 c++
#include <iostream>
using namespace std;
int n;
string plans;
int x = 1, y = 1;
// L, R, U, D 에 따른 이동방향
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
char moveTypes[4] = {'L', 'R', 'U', 'D'};
int main(void){
// 정수를 입력받고, 이 후 한줄로 된 문자열을 입력받는 경우
// 정수 입력받은 후, 문자열 입력받기 전 버퍼를 비워줘야 한다
cin >> n;
cin.ignore(); // 버퍼 비우기
getline(cin, plans);
// 이동계획을 하나씩 확인한다
for (int i = 0; i < plans.size(); i++){
char plan = plans[i]; // 이동 후 좌표
int nx = -1, ny = -1; // 다음 좌표 초기화 (파이썬에선 초기화 불필요)
for (int j = 0; j <4; j++){
if (plan == moveTypes[j]){ // 움직일 방향과 계획이 같으면
nx = x + dx[j]; // 현재 위치 + 움직일방향 -> 다음 좌표에 넣어준다
ny = y + dy[j];
}
}
// 공간을 벗어나는 경우 무시
if (nx < 1 || ny <1 || nx >n || ny > n) continue;
// 다음 좌표에 이동한다.
x = nx;
y = ny;
}
cout<<x <<' ' << y << endl;
return 0;
}시각 문제
n을 입력받았을 때 00시 00분 00초부터 n시 59분 59초까지의 시각 중 3이 포함되어 있는 모든 경우의 수를 구하여라.
python
h = int(input())
count = 0 # 3이 포함된 경우를 세는 count를 0으로 초기화
for i in range(h+1): # 0 부터 h시까지 1씩 증가하도록 한다
for j in range(60): # 분 또한 0부터 59까지 증가
for k in range(60): # 분이 증가할 때마다 0부터 59초까지 매번 반복
if '3' in str(i) + str(j) + str(k):
# 3이 하나라도 있는 경우
# 시, 분, 초를 죽 이어서 나열해서 3이 포함되어 있다면
count += 1
print(count) - 내가 틀렸던 부분
매 분마다 60초를 반복시켜야 하고, 매 시마다 매 분, 매 초를 반복시켜야 하므로 중첩 반복문을 사용했어야 했는데, 경우의 수에 집착하느라 for문을 별도로 사용하였다.
- 문자열에서 특정 문자 찾기
'3' in str(i)
C++
#include <iostream>
using namespace std;
int h, cnt;
// 특정 시각 내 '3'이 포함되어 있는지 여부를 판단하는 함수
bool check(int h, int m, int s){ // 시, 분, 초를 매개변수로 입력받아
if (h%10 == 3 || m / 10 == 3 || m % 10 == 3|| s/10 == 3|| s%10 == 3)
// 시가 1의 자리수가 3인지 검사
// or 분의 10의 자리수, 1의 자리수가 3인지 체크
// or 초의 10의 자리수, 1의 자리수에 3이 있는지 확인
return true;
return false;
}
int main(void){
cin >> h; // 시간 입력 받자
for (int i = 0; i <= h; i++){
for (int j = 0; j<60; j++){
for (int k = 0; k <60; k++){
if (check(i, j, k)) cnt++;
// check 함수에 넣어서 true 리턴하는 경우 cnt 1씩 증가
}
}
} // 모든 시, 분, 초에서 반복
cout << cnt << endl;
return 0;
}왕실의 나이트 문제
8x8 좌표 평면에서 나이트의 위치가 주어졌을 때 아래와 같이 움직일 수 있다면 이동할 수 있는 경우의 수 구하기
1. 수평으로 두 칸 이동한 뒤 수직으로 한 칸 이동한다
2. 수직으로 두 칸 이동한 뒤 수평으로 한 칸 이동한다
- 나이트의 8가지 경로를 하나씩 확인하며 해당 경로로 이동 가능한지 확인한다 (체스판을 벗어나면 안되므로)
- 리스트를 이용해 8가지 방향에 대한 방향벡터를 정의한다
- 문자열을 숫자로 변환하기
ord('a'): a의 아스키코드 값 (10진수)로 변환
python
# 현재 위치를 입력받는다 ex. c3, a1, ...
input_value = str(input())
# solution에서는 그냥 input()으로 받았으나
# 주피터 노트북에선 str이 없으니 오류가 났다
row = int(input_value[1])
#문자열의 두번째 자리에 있는 것을 숫자로 받는다 (열)
column = int(ord(input_value[0])-96)
# 소문자 a의 아스키코드 값이 10진수로 97이므로 1을 얻으려면 96을 빼준다.
# a의 아스키코드 검색할 필요없이
# int(ord(input_data[0])) - int(ord('a')) + 1 라고 하면 된다
now = (row, column) # 이 코드는 필요없었다.
steps = [(2,1), (2,-1), (-1, 2), (-1, -2), (-2, 1), (-2, -1), (1, 2), (1, -2)]
# dx, dy 대신 하나의 리스트로 구현하였다.
result = 0
for now in steps:
next_row = row + now[0]
next_column = column + now[1]
# 다음 위치가 체스판을 벗어나지 않는다면 (1~8사이의 값)
if next_row >= 1 and next_row <= 8 and next_column >=1 and next_column <= 8:
result += 1
print(result) C++
#include <iostream>
using namespace std;
string inputData;
int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
int dy[] = {-1, -2, -2, -1, 1, 2, 2, 1};
int main(){
cin >> inputData;
int row = inputData[1] - '0';
int column = inputData[0] - 'a' + 1;
// 입력받은 문자열 형태에서 문자의 아스키 코드 값 뺌으로써 행과 열 초기화
// 8가지 방향에 대해 각 위치로 이동이 가능한지
int result = 0;
for (int i = 0; i<8; i++){
int nextRow = row + dx[i];
int nextColumn = column + dy[i];
// 해당 위치로 이동 가능하면 카운트 증가
if(nextRow >= 1 && nextRow <= 8 && nextColumn >= 1 && nextColumn <= 8){
result += 1;
}
}
cout << result << endl;
}