https://www.acmicpc.net/problem/21609 21609번: 상어 중학교 상어 중학교의 코딩 동아리에서 게임을 만들었다. 이 게임은 크기가 N×N인 격자에서 진행되고, 초기에 격자의 모든 칸에는 블록이 하나씩 들어있고, 블록은 검은색 블록, 무지개 블록, 일반 블록 www.acmicpc.net 난이도 : 골드 2 태그 : 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비 우선 탐색 설명 삼성 기출문제로도 유명한 상어 시리즈 중 상어 중학교 입니다. 다른 상어 시리즈와 마찬가지로 시뮬레이션 + 그래프(탐색 및 백트래킹) + 배열 뒤집기가 인상적이였던 문제였습니다. 계속 테스트케이스가 다르게 나왔는데, 시뮬레이션 문제 특성 상 한 회차당 맵이 어떻게 바뀌는지 확인해야 하기 때문에 엑..
데코레이터 (Decorator) 패턴 데코레이터 패턴이란, 이름에서 알 수 있듯이 기존 객체에 새로운 요소를 추가할 때 쓰입니다. 흔히 음식이나 방을 꾸밀 때 데코한다고 하죠? 데코레이터 패턴을 알게되면 이제는 클래스에도 데코를 할 수 있게 될 겁니다. 방을 데코할땐 원래 있던 가구를 치우거나 바꿀수도 있습니다. 하지만 데코레이터 패턴을 사용해 클래스를 바꿀 때에는 기존의 클래스를 수정하지 않으면서, 새로운 기능을 추가할 때 사용합니다. 정확히는, 기존의 클래스를 감싸는(wrap) 방식으로 이루어집니다. 이제 음료를 데코레이터 해봅시다. 카페를 차렸습니다. Uknow 커피 디자인 패턴 마을점. 신규 오픈하였습니다. 아직 메뉴가 몇개 없지만, 이를 전산화하기 위한 작업을 해봤습니다. 클래스 Boooooom..
https://www.acmicpc.net/problem/16920 16920번: 확장 게임 구사과와 친구들이 확장 게임을 하려고 한다. 이 게임은 크기가 N×M인 격자판 위에서 진행되며, 각 칸은 비어있거나 막혀있다. 각 플레이어는 하나 이상의 성을 가지고 있고, 이 성도 격자판 위 www.acmicpc.net 난이도 : 골드 2 태그 : 그래프 탐색, 그래프 이론, 너비 우선 탐색 설명 각 플레이어 i는 한 턴에 S(i) 거리 만큼 확장을 할 수 있습니다. 각 플레이어 별로, 그리고 한 싸이클씩 그래프 탐색을 진행하는게 포인트라 할 수 있습니다. 예제중 하나를 가져와봤습니다. 초기 상태가 아래와 같고, 플레이어 1이 2칸, 플레이어 2가 1칸씩 움직일 수 있는 경우입니다. 1..1 .... .... ..
Observer Pattern (옵저버 패턴) 옵저버 패턴은 특정 객체를 관찰(Observe)하다가, 해당 객체의 상태가 변경된다면 이를 관측하고 있는 객체들에게 연락을 하는 일대다(one-to-many) 의존성을 정의합니다. 사실 자바 Swing, 안드로이드, 프론트엔드 등 GUI 프로그래밍을 하신 분들이라면 버튼을 하나 만들고, 이를 클릭하면 특정 이벤트를 발생시키기 위해 onClickListenr 등을 사용해본 경험이 있으실텐데요. 이와 같은 Listener들은 버튼을 관측하고 있다가, 사용자가 버튼을 누루면 이벤트를 발생시키는 Observer 패턴의 일종인 Listener 패턴입니다. 버튼 클릭 리스너를 떠올리니, '한 객체를 관측하고 있다가 해당 객체의 상태가 변화되면 이벤트를 발생시킨다'는게 ..
https://level.goorm.io/l/challenge/goormthon-challenge?utm_source=notion&utm_medium=cta&utm_content=open&_gl=1*1lv0w8b*_gcl_au*MTA2NTY4MTU0My4xNjkyMDE0OTc4 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 구름톤 알고리즘 챌린지 19일차 : 대체 경로 구름톤 알고리즘 챌린지 19일차 문제인 대체 경로 입니다. 1일부터 n일까지, i일에는 i번째 도시가 공사를 한다고 하였을 때, 해당 도시가 공시중일 때 시작 도시에서 도착 도시로 가는 최단 경로를 찾는 문제였습니다. 단순 최단 경로라면 BFS를 사용한 최단경로 찾기 기법을..
https://level.goorm.io/l/challenge/goormthon-challenge?utm_source=notion&utm_medium=cta&utm_content=open&_gl=1*1lv0w8b*_gcl_au*MTA2NTY4MTU0My4xNjkyMDE0OTc4 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 구름톤 알고리즘 챌린지 18일차 : 중첩 점 18일차 문제인 중첩 점입니다. 바둑판 모양의 정사각형이 있습니다. 한 사각형을 중심으로 상,하,좌,우로 직선을 그리는데요. 각 직선이 교차하면서 생기는 점들의 총 개수를 구하는 문제입니다. 각 칸의 점의 개수를 구하는 방법은 간단합니다. 바로 해당 칸의 수직선 * 수평선의 ..
https://level.goorm.io/l/challenge/goormthon-challenge?utm_source=notion&utm_medium=cta&utm_content=open&_gl=1*1lv0w8b*_gcl_au*MTA2NTY4MTU0My4xNjkyMDE0OTc4 구름LEVEL 난이도별 다양한 문제를 해결함으로써 SW 역량을 향상시킬 수 있습니다. level.goorm.io 구름톤 알고리즘 챌린지? 이번엔 조금 재밌는 챌린지를 하게 되었습니다. 구름(구름 LEVEL) 에서 진행하는 구름톤 알고리즘 챌린지인데요. 조금 늦게 알게 되었지만 챌린지가 종료되기 전에라도 알게되어 다행입니다. 😀 이번 포스팅에서 다룰 문제는 챌린지 17일차 '통신망 분석' 입니다. 일반적인 DFS/BFS를 활용한 그..
error: unmappable character (0xED) for encoding x-windows-949 새 프로젝트를 만들고 테스트로 print문 하나를 작성했는데 오류가 났습니다. Hello World는 잘 출력 되나, 한글을 넣었을 때 발생하는 걸로 봐서 아무래도 한글 인코딩 문제 같네요. [File] -> [Settings]에 들어갑니다. [Editor] -> [File Encodings]에 들어갑니다. 검색창에 Encoding을 입력하면 더 쉽게 찾을 수 있습니다. 저 같은 경우는 Project Encoding이 x-windows-949로 되어있었습니다. 국제 표준 인코딩 방식인 UTF-8로 변경합니다. 이제 다시 코드를 실행해봅시다. 에러는 안뜨지만 출력된 한글이 깨집니다... [Help..
유클리드 기하학(Euclidean geometry)이란 무엇일까요? 고대 그리스 수학자 유클리드가 정립한 기하학으로, 우리가 초중고 수학시간에 배운 대부분의 기하학은 유클리드 기하학으로 보아도 됩니다. 오늘은 유클리드 기하학에서 사용되는 유클리드 거리와, 비 유클리드 기하학 중 택시 기하학의 맨해튼 거리에 알아보겠습니다. 유클리드 거리 위 2차원 평면에서, 두 점의 거리는 어떻게 구할 수 있을까요? 매우 간단합니다. 피타고라스를 통해 손쉽게 구할 수 있습니다. 점 p(x1, y1)와 q(x2,y2)가 있을 때 이 둘 사이의 거리는 아래와 같습니다. 위와 같이 일반적인 평면에서 두 점 사이의 최단거리를 구한 것을 유클리드 거리라고 합니다. 일상 생활에서 일반적으로 사용하는 거리이죠. int x1 = 2, ..
공간 복잡도 (Space Complexity) 시간 복잡도가 알고리즘의 연산횟수, 수행시간을 평가하는데 쓰이는 척도라면, 공간 복잡도는 알고리즘이 메모리를 얼마나 사용하는 지에 관한 척도입니다. 알고리즘을 설계할 때는 시간 복잡도와 공간 복잡도 모두 고려한 적절한 알고리즘을 설계 및 사용해야 합니다. 다만, 두 마리 토끼를 둘 다 잡을 수 없을 경우엔 공간 복잡도 보다는 시간 복잡도를 더 우선시하는 경향이 있습니다. 하드웨어의 발전 메모리 용량 자체가 커지기도 했고, 병렬 처리와 분산 컴퓨팅 역시 발전했습니다. 요즘 같은 대용량 데이터를 처리해야 하는 시대에는 처리 시간이 짧은 알고리즘이 중요하기 때문입니다. 그럼에도, 공간 복잡도는 중요한 개념입니다. 하드웨어가 얼마나 발전했던 간에, 메모리의 한계는 ..