코딩기록

이 포스팅은 스프링 핵심 원리 - 기본편 강의를 듣고 정리한 것입니다. 객체 지향 프로그래밍이란? - 객체 지향 프로그래밍은 컴퓨터 프로그램을 명령어의 목록으로 보는 시각에서 벗어나 여러 개의 독립된 단위, 즉 "객체"들의 모임으로 파악하고자 하는 것이다. 각각의 객체는 메시지 를 주고받고, 데이터를 처리할 수 있다. - 객체 지향 프로그래밍은 프로그램을 유연하고 변경이 용이하게 만들기 때문에 대규모 소프트웨어 개발에 많이 사용된다. 이 때, 유연하고 변경이 용이하게 해주는 것이 다형성입니다. 다형성이란? - 하나의 클래스나 메소드가 다양한 방식으로 동작이 가능한 것을 의미 - 부모클래스가 자식클래스의 값으로 대체되는 오버라이딩 - 같은 메소드의 매개변수(parameter)에 따라 다르게 동작하는 오버로..

https://www.acmicpc.net/problem/2206 2206번: 벽 부수고 이동하기 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로 www.acmicpc.net 이 문제는 방문리스트(visited)를 3차원 배열로 만드는 것이 핵심인 문제였다. 벽을 한번만 뚫을 수 있으므로 3차원으로 만들어야 한다. visited[x][y][0] 에는 벽을 뚫지 않고 온 경우의 최단경로를 저장하고, visited[x][y][1] 에는 벽을 뚫고 온 경우의 최단경로를 저장한다. from collections import deque n, m = ma..

오늘은 2021년 마지막 날이다! 한 해를 마무리하면서 정리해보려고 한다 올해는 대학생활 중에 가장 열심히 산 1년이 아니었나 싶다 (3학년 1학기까지 열심히 놀았기때문..ㅎ) 월별로 기억을 더듬어가며 정리를 해봐야겠다 1월 1월엔 졸업작품 개발을 시작했다. 1월엔 주로 앱 화면을 만들었던 것 같다. 매주 학교 졸작실로 출근을 하여 정해진 시간동안 개발을 했다. 매주 학교를 가니 방학이 없는 기분이었다... 처음엔 오랜만에 학교가서 새로운 느낌이었는데 역시나 멀어서 가기 귀찮아짐.... 또 1월에는 개발 동아리를 하고 있었어서 프로젝트를 같이 진행했었다. 지금 생각해보면 동아리를 하게 된 것이 나의 터닝포인트였던 것 같다. 열심히 사는 사람들과 함께하다보니 나도 열심히 하게 되고 열심히 살려고 노력하기 ..

https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 이 문제는 전형적인 LCS 문제입니다. LCS 개념과 푸는 방법만 알면 쉽게 풀 수 있습니다. 먼저 두 문자열을 담은 2차원 리스트를 만듭니다. 그리고 문자 하나씩 비교해가면서 최장 수열의 개수를 세면 됩니다. 최장 수열의 개수를 세는 방법은, 문자가 같은 경우 -> dp[i][j] = dp[i-1][j-1] + 1 (글자가 추가 되기 전 최대 길이 +..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이 문제를 풀기에 앞서 이분 그래프의 개념을 알고 가야 한다. 이런 식으로 정점의 색깔을 바꾸어 칠하면서 같은 색끼리 간선이 없는 경우 이분 그래프이다. 간선이 있다면 이분 그래프가 될 수 없다. 이것을 코드에 적용하면 문제를 풀 수 있다. 코드에서는 색상을 숫자로 표시하였다. (예 - 파랑은 1로, 빨강은 -1로) from collections import deque import sys inpu..

https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net import copy N, M = map(int, input().split()) graph = [list(map(int, input().split())) for _ in range(N)] dx = [-1, 0, 1, 0] dy = [0, 1, 0, -1] direction = { 1: [[0], [1], [2], [3]], 2: [[0, 2], [1, 3]], 3: [[0, 1], [1..

https://www.acmicpc.net/problem/21314 21314번: 민겸 수 민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다. www.acmicpc.net MK일 경우 최소값은 15, 최대값은 50이 된다. MMK일 경우 최소값은 105, 최대값은 500이 된다. MKMM일 경우 최소값은 1510, 최대값은 5011이 된다. 이제 규칙을 알 수 있다. ▶ 최소값의 규칙 = K로 끝날 때마다 10 ** (K가 나오기 전 M의 개수) + 5 를 추가한다. M으로 끝날 때 10 ** (M의 개수 - 1) 를 추가한다. ▶ 최대값의 규칙 = K로 끝날 때마다 5 * (10 ** (K가 나오기 전 M의 개수)) 를 추가한다. M으로 끝날..

https://www.acmicpc.net/problem/2812 2812번: 크게 만들기 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. www.acmicpc.net N, K = map(int, input().split()) nums = list(input()) k, stack = K, [] for i in range(N): while k > 0 and stack and stack[-1] < nums[i]: # 앞에 숫자가 해당 숫자보다 작을 경우 지운다 stack.pop() k -= 1 stack.append(nums[i]) print(''.join(stack[:N-K])) # K개를 지우지 못하는 경우를 위해 인덱스 슬라이싱을 해준다..

https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 이 문제는 그리디 문제이다. 해결방법은 다음과 같다. [ 이동 방법 ] 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 1. N == 1 인 경우 - 위 아래로 움직일 수 없으므로 시작칸만 방문할 수 있다. 따라서 방문할 수 있는 칸의 수는 1이다. 2. N == 2 인 경우 - 위 아래로 1칸만 움직일 수 있으므로 2, 3번 방법만으로 움직일 수 있다. 가로가 아무리 길더라도 최대 3번 이상 움직일 수 없..

https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net N, C = map(int, input().split()) house = [int(input()) for _ in range(N)] house.sort() # 오름차순 정렬 low, high = 1, house[-1] - house[0] while low = cur + mid: cur = house[i] count += 1 if count >= ..