글 작성 제목과 내용을 간결하게 정리해 주세요. 제목 내용 <h2>개념</h2><p>머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정</p><ul><li>모든 문제에 포함되는 개념</li><li>코딩테스트에서는 구현을 중심으로 하는 문제가 출제되어 따로 분류함<ul><li>풀이를 떠올리는 것은 쉽지만 소스코드로 옮기기 어려운 문제 유형을 의미함</li></ul></li></ul><h2>코딩테스트에서의 구현</h2><p>풀이를 떠올려도 소스코드로 옮기기 어려운 문제 유형</p><p>피지컬을 요구</p><p><aside> 💡 <strong>코딩테스트의 피지컬</strong></p><p>프로그래밍 언어 문법에 능숙하고 코드 작성 속도가 빠른 사람을 의미</p><p></aside></p><p>문자열 처리나 큰 수 처리등 구현에 어려움이 없는 파이썬이 유리</p><figure class="table"><table><thead><tr><th>언어</th><th>구현 난이도</th><th>실행 시간</th></tr></thead><tbody><tr><td>파이썬</td><td>쉬운 편</td><td>긴 편</td></tr><tr><td>PyPy</td><td>쉬운 편</td><td>다소 짧은 편</td></tr><tr><td>C/C++</td><td>어려운 편</td><td>짧은 편</td></tr><tr><td>자바</td><td>어려운 편</td><td>긴 편</td></tr></tbody></table></figure><h3>대표적인 까다로운 구현 문제들</h3><ul><li>알고리즘은 간단하지만 코드가 지나치게 길어지는 문제</li><li>특정 소수점 자리까지 출력하는 문제</li><li>문자열이 입력으로 주어졌을 때 한 문자 단위로 끊어서 리스트에 넣는(파싱) 문제</li><li>완전 탐색<ul><li>모든 경우의 수를 주저 없이 다 계산하는 해결 방법</li></ul></li><li>시뮬레이션<ul><li>문제에서 제시한 알고리즘을 한 단계씩 차례로 직접 수행해야하는 문제</li></ul></li></ul><h3>구현에서 고려해야 할 메모리 제약 사항</h3><p><strong>전통적 프로그래밍 언어의 정수형</strong> - <code>int</code>(integer)</p><ul><li>4Byte</li><li>-2,147,483,648 ~ 2,147,483,647</li></ul><p><strong>큰 수를 처리하는 방법</strong></p><p>C/C++</p><ul><li><code>long long</code> 사용<ul><li>9,223,372,036,854,775,807 까지 가능</li><li>이보다 큰 수는 BigInteger클래스를 구현해야 함</li></ul></li></ul><p>Java</p><ul><li>BigInteger 클래스 표준 라이브러리 사용</li></ul><p>Python</p><ul><li>기본 자료형으로 지원</li></ul><p><strong>파이썬의 리스트 크기</strong> - 1당 약 4바이트</p><figure class="table"><table><thead><tr><th>리스트 길이</th><th>메모리 사용량</th></tr></thead><tbody><tr><td>1,000</td><td>약 4KB</td></tr><tr><td>1,000,000</td><td>약 4MB</td></tr><tr><td>10,000,000</td><td>약 40MB</td></tr></tbody></table></figure><ul><li>크기가 1000만 이상인 리스트가 있다면 메모리 초과 가능성이 있음</li></ul><h3>채점 환경</h3><ul><li>파이썬<ul><li>C/C++ 에 비해 2배의 수행 시간 제한을 적용하기도 함</li><li>3.7기준 1초에 2,000만번의 연산 수행을 가정하면 됨<ul><li>제한 시간 1초에 데이터의 갯수가 100만 개라면 시간 복잡도 O(NlogN) 이내 알고리즘을 이용해야함</li></ul></li></ul></li></ul><h2>구현 문제 접근 방법</h2><h3>구현 문제 특징</h3><ul><li>사소한 입력 조건 등을 전부 명시</li><li>문제의 길이가 길어짐</li></ul><p>→ 고차원적인 사고력을 요구하는 문제는 나오지 않는 편이라 문제의 길이를 보고 지레 겁먹지 말고 알고 있는 문법을 이용해 조건을 만족시켜 해결한다</p><h2>문제</h2><h3>상하좌우</h3><p>외쪽 상단 (1, 1)에서 오른쪽 하단 (N, N) 좌표를 갖는 N * N 크기의 공간이 있을 때 다음 네가지 입력들에 대해 (1, 1)좌표에서 출발해 나중에 위치할 좌표를 출력 (단, 공간을 벗어나는 입력은 무시함)</p><ol><li>L : 왼쪽으로 이동</li><li>R : 오른쪽으로 이동</li><li>U : 위로 이동</li><li>D : 아래로 이동</li></ol><p><strong>문제 해설</strong></p><p>요구 사항 대로 구현한다면 연산 횟수는 이동 횟수에 비례 이동 횟수가 N번이라면 시간 복잡도는 O(N)으로 넉넉함</p><p>일련의 명령에 따라 개체를 차례로 이동시킨다는 점에서 시뮬레이션 유형으로 분류할 수 있음</p><p>입력 받은 이동 계획을 하나씩 확인하여 현재 위치를 그에 맞게 하나씩 바꿔준다. 단 (1, 1)에서 (n, n)까지의 범위 내에서만 수행한다.</p><p><strong>코드</strong></p><pre><code class="language-python">import sys input = sys.stdin.readline n = int(input()) # 공간 크기 입력 planer = input().split() # 이동 계획 입력 # 이동 계획에 따라 (이동 축, 이동 방향)을 같는 딕셔너리 mapPlan = {'L':(1, -1), 'R':(1, 1), 'U':(0, -1), 'D':(0, 1)} # 현재 좌표 coor = [1, 1] # 이동 계획을 하나씩 수행 for i in planer: t = mapPlan[i] # 이동 축, 이동 방향을 가져옴 temp = coor[t[0]] + t[1] # 이동 축에서 이동 방향으로 이동한 결과 if temp > 0 and temp <= n: # 범위를 벗어나지 않았다면 coor[t[0]] = temp # 현재 좌표에 적용 print(coor[0], coor[1]) # 최종 출력 </code></pre><h3>시각</h3><h3>왕실의 나이트</h3><h3>게임 개발</h3><h3>백준</h3><p><a href="https://www.acmicpc.net/problem/14503">14503번: 로봇 청소기</a></p><p><a href="https://www.acmicpc.net/problem/16505">16505번: 별</a></p><p> </p> 글 종류 이론 정리 알고리즘 이론에 대한 정리글입니다. 문제 풀이 알고리즘 문제 풀이입니다. 알고리즘 분류 수정 취소