알고리즘의 성능을 판단하는 데에는 시간 복잡도(Time Complexity), 공간 복잡도(Space Complexity) 등이 쓰입니다. 시간 복잡도는 알고리즘이 얼마나 빠르게 실행되는지, 공간 복잡도는 알고리즘이 얼마나 메모리를 잡아먹는지를 판단하는데 쓰입니다. 이번 편에서는 그 중에서도 시간 복잡도(Time Complexity)를 알아보겠습니다. 시간 복잡도 (Time Complexity) 시간 복잡도는 입력되는 데이터의 양에 따라 알고리즘의 수행 시간이나 연산 횟수가 어떻게 달라지는지를 분석하는데 쓰입니다. 알고리즘을 짤 때에는 문제를 해결하는 것도 좋지만, 알고리즘을 얼마나 효율적으로 짜는 것 역시 중요합니다. 같은 입력을 넣었을 때, 같은 출력을 갖는다 하더라도, 알고리즘에 따라 성능이 달라질..

백준을 알게 되어 알고리즘 공부를 시작한지는 꽤 되었지만, 사실 심심할때 1달에 1~2문제 풀었던 정도라, 본격적으로 알고리즘을 공부하기 시작한지는 약 1년 정도 된 것 같습니다. 800문제를 풀었을 즈음, 1000문제를 찍어보고 싶다는 생각에 하루에 10 문제씩 풀며 달려왔는데, 1000문제를 찍는 날이 오긴 했네요. 1일 1코딩테스트를 했던게 꽤 도움이 됬던 것 같습니다. xxx일 연속 문제 해결이 꽤 쌓이다보니, 끊기면 되게 아쉬울 것 같더라고요. 매일 매일 코딩하고, 공부하는 원동력중 하나가 되었습니다. 지금까지도 쉽진 않았지만 앞으로도 쉽진 않을테니 열심히 해야겠네요.

AWS Lightsail 세팅 AWS(Amazon Web Services). 클라우드 서비스의 대표격인 플랫폼입니다. AWS를 처음 사용할 때, 초기 세팅이나 설치해야 할 것들이 다소 있습니다. AWS Lightsail은 보다 간편하고 사용하기 쉬워 초보자, 개인, 소규모 팀이 사용하기 좋습니다. 오늘은 이 AWS Lightsail에 Spring + Thymeleaf를 사용해 제작한 웹 사이트를 배포해보려 합니다. 먼저, AWS Lightsail 홈페이지에 접속합니다. https://lightsail.aws.amazon.com https://lightsail.aws.amazon.com/ls/webapp lightsail.aws.amazon.com 회원가입 과정은 생략하겠습니다. 저의 경우 이전에 미리 생..

https://www.acmicpc.net/problem/20302 20302번: 민트 초코 상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다. www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 정수론, 소수판정, 에라토스테네스의채 설명 상당히 어려웠던 문제였습니다 그냥 단순히 입력으로 주어지는 연산을 그대로 했더니 당연하게 시간초과 발생하였고, *, / 연산을 각각 리스트로 만들어 6 -> 2 * 3, 10 -> 2 * 5와 같이 소인수 분해 한 후, 각각에 리스트에 넣어준 뒤 (첫 항은 *로 처리), * 연산이 남아있으면 유리수, / 연산이 남아있으면 유리수로 판단하였습니다. 6 / 4 = (3 * 2) / (2 * ..

https://www.acmicpc.net/problem/25585 25585번: 86 ─에이티식스─ 1 첫 번째 줄에 전장의 크기 $N$이 주어진다. 전장은 $N \times N$ 크기 좌표로 이루어져 있다. 다음 $N$개의 줄에는 전장의 정보가 주어진다. 각 줄마다 $N$개의 좌표 정보가 주어지며 0은 빈칸, 1은 레기 www.acmicpc.net 난이도 : 골드 5 태그 : 백트래킹, 브루트포스 설명 대각선으로만 이동할 수 있는 장기말로, 다른 적들을 다 잡을 수 있는지, 잡을 수 있다면 얼마만큼의 시간이 소요되는지 구하는 문제입니다. 처음엔 n이 꽤 작길래, 대각선 방향으로 이동하는 모든 경우의 수를 다 확인하였으나, 당연하게도 시간초과. n이 최대 100이여도 n이 1 만큼 증가할때마다 말도안..

for문의 차이 위 for 문은 C, C++, C#, Java 등에서 흔히 접할 수 있는 for문의 형태 입니다. C와 자바를 사용하시는 분들이라면 매우 익숙하실 텐데요. 하지만 파이썬을 주로 사용하는 분들에게는 다소 어색할 수도 있을 것 같습니다. 저는 코딩을 C와 자바로 처음 배웠다 보니, 파이썬의 반복문은 상당히 낮설었습니다. 이는 코틀린의 반복문 역시 마찬가지였습니다. 변수 하나를 두고, 해당 변수의 범위를 지정하는 방식으로 for문이 작동하였습니다. 조건식 + 증감식 기반 vs 대입 기반 파이썬의 반복문을 위와 같이 리스트 내 원소를 순회하는 용도로 사용하는 것을 볼 수 있습니다. 이는 list 내 원소 하나 하나 씩 i에 대입이 된다고 볼 수 있습니다. range(n1, n2) 역시 마찬가지입..

x가 0이 아니면서, x와 -x가 같은 경우 ? https://www.acmicpc.net/problem/15549 15549번: if 다음 프로그램을 실행시켰을 때, "true"를 출력하는 변수 x의 자료형과 값을 찾는 프로그램을 작성하시오. import java.util.*; public class Main { public static void main(String[] args) { ??? x = ???; if (x != 0 && x == -x) www.acmicpc.net 백준 15549번. 위 코드에서 true를 출력할 수 있도록 변수 x의 자료형과 값을 찾으라는 문제였습니다. (단 자료형은 int, long 중 하나) true를 출력하려면... x랑 -x랑 같아야 하나, x는 0이 아니다. ??..

라이브러리(Library)와 프레임워크(Framework). 개발을 하다 보면 매우 자주 듣는 용어들입니다. 두 녀석을 한 마디로 쉽게 설명해보자면 '누군가가 이미 만들어놓은 코드 뭉치' 라고 볼 수 있습니다. 둘 다 소프트웨어를 개발하는데 있어 필요한 여러 기능을 제공하는 코드 덩어리 입니다. 라이브러리 (Library) 이 포스팅의 첫 번째 주인공인 라이브러리는 소프트웨어를 개발하는데 있어 특정 기능이나 특정 작업을 하기 위한 기능이나 도구, 함수, 클래스, 데이터 등을 모아놓은 코드 뭉치 입니다. 이는 개발자들이 자주 사용하는 코드를 재작성하지 않고 그저 라이브러리를 호출해 사용하면 되기에, 코드의 재사용성이 증가합니다. 파이썬의 Numpy, Pandas, TensorFlow 등등이 있으며, 안드로..

https://www.acmicpc.net/problem/1331 1331번: 나이트 투어 나이트 투어는 체스판에서 나이트가 모든 칸을 정확히 한 번씩 방문하며, 마지막으로 방문하는 칸에서 시작점으로 돌아올 수 있는 경로이다. 다음 그림은 나이트 투어의 한 예이다. 영식이는 6× www.acmicpc.net 난이도 : 실버 4 태그 : 구현, 시뮬레이션 설명 6 * 6 체스판 위 한 점에서 시작하여 나이트가 이동하며 모든 칸을 한 번씩만 (두 번 이상 같은 곳을 방문하면 실패) 방문하면서, 첫 시작점으로 돌아올 수 있는지 확인하는 문제입니다. 해당 문제 매 좌표 입력을 받을 때 마다 체크해야 할 것이 있습니다. 1. 이미 방문했는가(2번 이상 같은 칸을 반복할 수 없음) -> 2차원 boolean - v..

https://www.acmicpc.net/problem/2563 2563번: 색종이 가로, 세로의 크기가 각각 100인 정사각형 모양의 흰색 도화지가 있다. 이 도화지 위에 가로, 세로의 크기가 각각 10인 정사각형 모양의 검은색 색종이를 색종이의 변과 도화지의 변이 평행하도록 www.acmicpc.net 난이도 : 실버 5 태그 : 구현 설명 도화지 위에 색종이를 붙였을 때, 색종이의 전체 크기를 출력하는 문제입니다. 어떻게 풀까 고민을 좀 해봤는데, 도화지의 가로, 세로의 크기가 100밖에 되지 않는 것을 보고 그냥 100 x 100인 2차원 boolean 배열을 만든 뒤, 색종이로 덮인 부분을 true로 처리하여 최종적으로 true인 부분의 개수만 카운팅하여 출력하면 될 것 같습니다. 소스코드 f..