전체 글

[C++] 백준 10282번 해킹

다익스트라의 기초적인 문제. 다익스트라란? 그래프에서 시작점이 있을 때, 시작점에서부터 최단 거리로 한 점씩 이동해보며 해당 점의 최소거리를 확정해 나가는 알고리즘이다. 이 때, 특정 점에서 다른 점들까지의 거리를 구한다는 뜻은 그 특정 점까지의 최단 거리는 확정됐다는 뜻이다. 그래프 이론에서 중요한 알고리즘이다. 이 때 모든 간선치는 양의 정수라고 가정한다. 다익스트라는 머리로는 그리기가 쉬운데, C++에서 구현하려면 복잡한 문법을 많이 알아야 한다. 내 구현 기준으로는 pair : pair 자료형은 특정 자료형 두개를 동시에 저장할 수 있다. make_pair(1, 2) 혹은 {1, 2} 이런 식으로 사용 가능하다. priority_queue : 우선순위 큐는 T 자료형을 container(vecto..

[C++] 백준 15649번 N과 M (1)

백트래킹의 기본적인 문제. 백트래킹 알고리즘을 알고있다면 쉽게 접근할 수 있는 문제이다. 백트래킹이란? 기본적으로 백트래킹은 '가능한 모든 방법을 탐색'한다는 데 그 기본 아이디어가 있습니다. 이 아이디어의 구현은 DFS, BFS 둘 다 가능한 방법입니다. 다만, 백트래킹은 보통 '불가능한 방법'임을 인지한다면 이전 상태로 돌아오는 작업이 필요한데 이는 큐를 사용하는 BFS보다는 스택(혹은 재귀)을 사용하는 DFS가 더 편하기 때문에 일반적으론 DFS를 사용합니다. 출처 : https://www.acmicpc.net/board/view/15738 - simm4256님 댓글 참고 쉽게 말해서 내가 길을 가다가 이 길이 아닌거 같으면 돌아가서 다른 길로 가는 것을 뜻한다. 물론 경우의 수가 상당히 많으로 시..

[C++] 백준 1011번 Fly me to the Alpha Centauri

처음 문제를 접근 했을 때 백트래킹으로 풀려고 시도했다. 재귀함수로 모든 경우를 돌면서 최소로 접근할 수 있는 것으로 계속해서 갱신하려고 했다. 구현은 했는데, 메모리 초과가 나면서 풀지 못했다. 단계별로 풀어보기에서 발견한 문제였는데, 분야가 수학이였다. 결국 조금 도움을 얻고자 게시판을 조금 검색해서 규칙성이 있다는 것을 얼핏 보았다. 그래서 이 규칙성을 가지고 어떻게 구현을 해야할까 고민했지만 결국 해답을 얻지 못했다. 글 읽기 - 풀이 정리해 보았습니다 댓글을 작성하려면 로그인해야 합니다. www.acmicpc.net 그러다가 게시판을 찾던 중 이런 글을 발견했고, step마다 갈 수 있는 거리가 정해져 있다는 것이였다. 이동 횟수 과정 이동 거리 1 1 1 2 1 1 2 3 1 2 1 4 4 1..

[C++] 백준 1436번 영화감독 숌

처음에 이 문제를 봤을 때 문제를 처음 봤을 때 666, 1666, 2666 ... 이런식으로 흘러가는 건 이해를 했다. 근데 너무 쉬워서 그냥 N - 1 출력하면 되는 게 아닌가 생각했는데 아무리 생각해도 너무 쉬워서 문제를 계속 읽었다. 함정은 6이 연속으로 3번 들어가면 그게 영화의 번째수가 된다는 것. 7번째는 따라서 6666이 아니라 6660이 된다는 것이다. 접근한 방식 처음에는 모든 경우의 수를 나누려고 했다. 맨 처음에는 모든 경우의 수를 다 생각하려고 했다. 그러다 보니 문제가 고려할 부분도 상당히 많아졌고, 맞았다고 생각해도 틀렸습니다 가 나왔다. 결국 이 방법으로 1, 2시간 고민하다가 이건 아닌 것 같아서 다 지우고 새롭게 생각했다. 1000씩 더하는 게 아니라 1씩 더해봐서 6이 ..

[Android] 상대 레이아웃, Relative Layout

상대 레이아웃으로 만들 수 있는 것들은 제약 레이아웃(Constraints Layout)으로 만들 수 있으므로 상대 레이아웃 사용은 권장되지는 않는다. 그러나 상대 레이아웃으로 만들어진 코드를 이해해야 하려면 알고 있어야 한다. 상대 레이아웃은 부모 컨테이너 혹은 다른 뷰와의 상대적인 위치를 통해 뷰의 위치를 결정할 수 있다. 이 때 뷰들의 id를 통해 상대적인 위치를 결정한다. layout_alignParent 속성과 layout_above, layout_below 등의 속성을 사용한다. 제약 레이아웃에 익숙해져 있어서 조금 낯설게 느껴졌지만 비슷하다. 제약 레이아웃이 더 많은 기능을 지원하므로 제약 레이아웃을 쓰는 것을 권장한다고 한다.

[자료구조]2. 스택

STACK ADT, 스택 추상자료형 스택 추상자료형은 필요한 타입에 맞는 정보를 저장한다. 삽입과 삭제가 후입선출 구조로 이루어진다. 스택의 주요 기능은 다음과 같다. push(object) : element를 삽입한다. pop() : 마지막으로 push된 element를 꺼낸다(return하고 삭제한다). 스택의 추가적인 기능은 다음과 같다. top() : 마지막으로 push된 element를 보여준다. size() : 저장된 elements의 수를 알려준다. empty() : 스택이 비어있는지 확인한다. 예외 처리에서는 pop()과 top() 메서드를 사용할 때 Stack Empty 예외처리를 사용한다. Stack을 사용한 프로그램 예시에는 다음이 있다. 웹 브라우저 방문 기록 텍스트 편집기 되돌리기..

[Android] 리니어 레이아웃, Linear Layout

리니어 레이아웃 방향 설정 리니어 레이아웃은 한 쪽 방향으로 뷰를 쌓는다. 따라서 리니어 레이아웃에는 필수 속성으로 방향을 설정해 주어야 한다. orientation 속성을 사용하고 가로 방향으로 쌓을 때는 horizontal, 세로 방향으로 쌓을 때는 vertical로 설정한다. 디폴트 값은 horizontal인 것 같다. 그래도 가독성을 위해서는 써 주는게 좋을 것 같다. ※ 최상위 레이아웃을 바꾸고 싶을 경우 xml 코드를 바꿔서 수정할 수도 있지만 Convert view를 사용해서 쉽게 바꿀 수 있다. 뷰의 크기 관련 속성 layout_width와 layout_height는 dp로 크기를 지정할 수도 있지만 match_parent, wrap_content로 지정할 수 있다. 이 때, match_p..

[Android] 레이아웃의 종류

레이아웃의 종류 제약(Constraint) 레이아웃 : 제약 조건 기반, 연결선을 제약조건으로 한다. 안드로이드 스튜디오 디폴트 레이아웃 리니어(Linear) 레이아웃 : 한 쪽 방향으로 차례대로 뷰를 추가한다. 뷰가 차지하는 사각형 영역을 나타낸다. 리니어 레이아웃은 어느 쪽 방향으로 뷰를 추가할 지에 대한 orientation 속성이 필수이다. 상대(Relative) 레이아웃 : 제약 레이아웃을 사용하면서 권장하지 않는다. 부모 컨테이너 혹은 다른 뷰와의 상대적 위치로 화면을 구성한다. 프레임(Frame) 레이아웃 : 싱글 모델. 가장 상위에 있는 하나의 뷰 또는 뷰 그룹만 보여준다. 여러 개의 뷰가 들어가면 중첩하여 쌓이게 된다. 테이블(Table) 레이아웃 : 격자(Grid) 모델. HTML에서 ..

[C++] 백준 1920번 수 찾기

이런 문제를 보면 바로 이분탐색부터 떠올려야 한다. big-O 표기법에 따르면 탐색 알고리즘에서 가장 시간소요가 적은 것이 O(NlogN)인데 쉽게 접근할 수 있는게 이분탐색이다. STL 제약이 없기 때문에 vector에 값들을 넣은 후 algorithm STL을 사용해서 sort와 binary_search 메서드를 사용했다. 이렇게 풀면 정말 가볍게 풀 수 있지만 이분 탐색 정도는 구현을 하라는 목적인 것 같았다. head와 tail (보통 left와 right로 표현하는 것 같다.) 그리고 mid를 정해놓고 남은 살펴볼 개수를 절반씩 줄여나가는 방식이다. 물론 STL을 사용할 수 있다면 그냥 algorithm STL을 사용해서 만들면 된다. (사실 STL 없이 sort하라고 하면 정말 답없을 것 같다..

[C++] 백준 1018번 체스판 다시 칠하기

오랜만에 풀어보는 알고리즘 문제였다. 어려운 문제는 아니고 손풀기 목적으로 골라본 문제였다. 처음 이 문제를 봤을 때 내가 접근했던 방식은 백트래킹을 생각했었다. 그리고 큐를 사용해서 후위표기식 느낌으로 모든 줄마다 push해서 pop했을 때 같은 색깔이 두 번 나오면 바꿔야되는 색을 하나씩 늘리는 것을 생각했다. 그런데 이렇게 할 경우 고려해야하는 예외의 경우가 너무 많아져서 포기했다. 후에 접근한 방식 문제를 다시 한번 잘 읽어보니, 체스판을 색칠하는 경우가 두 가지 뿐이라고 나와있었다. 즉, 내가 고려해야 하는 경우의 수는 두 개 뿐인 것이다. 좌상단이 검은색으로 시작하거나, 흰색으로 시작하거나이다. 이렇게 하면 모든 경우의 수를 다 고려할 수 있다. 보드를 나타내는 변수, n과 m을 나타내는 변수..