Jonyo Programming

[BOJ 1806(G4) 리뷰] 오늘 투 포인터를 공부하고 푼 문제다. 투 포인터는 배열 내에서 부분의 합을 구할때 아주 유용하게 쓰이는 알고리즘이다. 배운 개념을 그대로 적용했더니 G4문제치곤 간단하게 풀렸다. 다만 투 포인터를 응용한 문제를 풀려했더니 생각보다 어려웠다. 더 공부해야겠다. /* 21.01.04 BOJ : 1806 부분합 (https://www.acmicpc.net/problem/1806) 구현 */ #include using namespace std; int arr[100001]; int main() { cin.tie(0); ios::sync_with_stdio(0); int N, S; cin >> N >> S; for (int i = 0; i > arr..

[BOJ 17837(G2) 리뷰] 2차원 벡터를 이용해 풀었다. 조건에 주어진 대로 구현하면 된다. 다만 이동하려는 곳이 파란색이거나 범위를 벗어날 경우 방향을 바꿔주는 작업을 좀 신경써야 한다. 말들이 이동하는 방법은 가장 간단한 방법을 사용했다. 이동하기전에 현재 위치에 있는 말들을 탐색하면서 남아있어야 할 말들과 이동해야 할 말들을 각각의 벡터에 넣은 후, 이동시키면 된다. 만약 이동하고자 하는곳이 빨간색이라고 하면 이동해야 할 말들을 넣은 벡터만 reverse해주면 된다. 방향을 바꾸는 작업은 방향을 바꾼후에 다시 한 칸을 이동해야 한다는 조건때문에, 방향을 바꾸고 반복문 i의 값을 감소시켜 한번 더 반복문을 돌게 했다. 이때 이미 한번 방향을 바꾼적 이 있다면 그대로 움직이지 말아야 한다. 구현..

[BOJ 20055(S1) 리뷰] 오늘 푼 시뮬레이션 문제다. 설명은 위에 나온대로 친절하게 나와있다. 어떻게 구현을 할까 고민하던 중에 원형큐나 연결리스트를 사용하면 될 것같아 C++ STL에 존재하는 리스트를 사용해보기로 했다. 리스트를 사용해본적이 별로없어서 사용법을 익히느라 시간을 꽤 오래썼다. (그냥 연결리스트를 구현하는게 빨랐을듯) 시간은 오래걸렸지만 이 문제를 통해 반복자라는 개념에 대해서 조금 알게되었다. 난 이 문제를 해결하기 위해 리스트를 통해 입력을 받고 "올라가는 위치"와 "내려가는 위치"를 별도의 변수에 담았다. 그리고 벨트를 회전할 때 마다 이 값들을 바꿔주었다. 벨트를 회전하는것은 매우 간단하다. 리스트의 맨 끝에 있는 요소를 맨 앞에다 붙이고, 맨 끝에 있는 요소를 삭제하면 ..

[BOJ 16235(G4) 리뷰] 2021년에 푸는 첫 문제이다..! 문제를 보면 알겠지만 조건에 대한 설명이 아주 친절하게 나와 있다. 그렇기에 문제에서 주어진대로만 구현을 하면 될것같았다. 각 계절마다 함수를 만들어 벡터와 배열을 이용하여 구현하고, 테스트케이스도 다 맞길래 기분좋게 제출을 했다. 하지만 역시.. 이렇게 쉽게 풀릴 문제는 아니였다. 제출하자마자 시간초과가 떴다. 시간초과의 원인이 뭔지 분석을 해봤다. 일단 첫번째 문제로는 봄에 죽은 나무들을 별도의 벡터에 저장을하고, 여름 함수를 만들어서 여름함수에 양분을 추가하는 작업을 했는데 이 작업이 매우 비효율적으로 보였다. 두번째는 나이가 어린 나무부터 양분을 먹기위한 조건을 만족하기 위해 1년이 지날때마다 현재의 나무들을 오름차순으로 정렬했..

[BOJ 14500(G5) 리뷰] 삼성 SW역량테스트 기출문제다. 처음엔 엄청 간단한 문제인 줄 알았다. 그냥 DFS로 구현하면 쉽게 풀릴것같아 쓱 구현해서 돌려보니 문제가 발생했다. DFS로는 이 모양을 만족할 수가 없는것이였다. 어떻게 처리할까 매우 고민했다. 이왕 하는거 논리적이고 깔끔하게 코드를 짜고싶어서 머리를 이리저리 굴려보았는데 답이 잘 안나왔다. 계속 고민하다보니 집중력이 계속 떨어져서 그냥 무식한 방법을 사용하기로 했다. DFS를하면서 두번째 블록에 위치할때, 위 모양이 나올 수 있는 경우의 수를 생각해서 그냥 인덱스로 접근해서 구해버렸다. 그나마 순열로 구현하는게 깔끔할테지만, 넥퍼뮤 사용법도 까먹고해서.. 그냥 무식하게 구해버렸다. 어쨌든 맞았으니 기분은 좋긴한데 왠지모를 찝찝함이 남..

[BOJ 14890(G3) 리뷰] 삼성 SW역량테스트 기출문제다. 요즘 하나씩 풀고있다. 이 문제도 예전에 풀다가 포기했던 문제인데 지금 풀리는걸 보니 실력이 늘고있긴 한가보다. 신기하다. 문제 조건은 다음과 같다. 길을 건너기 위해서는 칸의 높이가 같아야 한다. 높이가 다를때는 경사로를 놓아 길을 지날 수 있다. 경사로의 높이는 1로 고정되어 있다. 경사로는 입력받은 L의 길이만큼 놓을 수 있다. 이것보다 적게,크게 놓을 수 없다. 경사로가 겹치면 안된다 나는 문제를 풀기위하여 천천히 하나하나씩 시뮬레이션하며 경우의 수를 생각해보았다. 일단은 2N만큼의 길을 탐색해야 하므로, 행 우선 탐색을 수행 한 후에 동일한 코드에 행과 열의 위치만 바꿔 열 우선 탐색을 수행 했다. 그리고 값을 하나 하나씩 비교한..

[BOJ 14503(G5) 리뷰] 1월에 있을 삼성SDS 알고리즘 교육을 대비하여 시간이 날때마다 하루 1~2문제씩 풀고있다. 이 문제는 삼성SW역량테스트 기출문제이다. 예전에도 한번 풀려고 했던적이 있는데 그땐 뭣모르고 DFS로만 풀어야하는 줄 알아 이리저리 머리 굴려보다 포기했던 문제다. 시간이 지나고 다시 문제를 천천히 읽어보니 굳이 DFS를 사용하지 않고도 구현을 할 수 있을것같아 시도했다. 푸는데는 1시간정도 걸린거같다. 일단 조건들은 문제에 친절히 설명이 되어있다. 따라서 설명에 맞게만 구현해주면 된다. 다만 방향을 바꾸는 부분, 후진하는 부분에 조금 헷갈리는게 있어 그 부분에서 시간을 꽤 잡아먹었다. 방향을 바꾸는것과 후진하는것은 %연산을통해 하도록했고, cnt변수를 통해 네 방향을 모두 탐..

전에 신청했던 삼성SDS 알고리즘 특강에 선발되었다는 메일을 받았다. 저번 방학때 백준 200문제, 골드 까지 찍고 이번 방학때 알고리즘 공부를 어떻게 해야할까 고민하고 있던 중에 좋은 소식이 찾아왔다. 교육후기를 찾아보니 꽤 수준높은 어려운 문제들을 푸는것 같은데 시작 전까지 백준풀면서 공부좀 해야겠다! 이번 방학은 정말 바쁠것같군 ...

이 포스트는 「Computer Networks: A System Approach , By L.Peterson , 5th, 2011」을 참고하여 작성했습니다. 지금까지 점대점 링크의 계층 1에 속하는 하드웨어 구성요소와 인코딩에 대해 살펴보았다. 프레이밍 프레이밍은 계층2로서 두 노드 사이의 프레임 교환에 이용된다. 패킷 네트워크에서 데이터를 끝없이 보낼 수 없다. 그렇기에 비트를 하나의 묶음으로 자르는 것을 프레임이라고 한다. 즉, 수신하는쪽이 프레임을 인식할 수 있도록 송신하는 쪽에서 봉투를 씌워 묶는 것을 프레이밍이라고 한다. 프레이밍은 전형적으로 네트워크 어댑터에서 구현된다. 네트워크 어댑터는 호스트 메모리로 부터 프레임(데이터+헤더 일부분)을 넣고 가져오는 작업을 진행한다. 프레이밍에는 대표적으로..

이 포스트는 「"Computer Organization and Design -The hardware / software interface" by Patterson and Hennessy, 5th edition, 2013.」을 참고하여 작성했습니다. floating point 이전 강의에서 정수형 자료의 표현방법과 덧셈, 곱셈 등 연산 방법에 대해 살펴보았다. 그렇다면 실수(Real number)는 어떻게 표현해야할까? 예를 들어 1/3은 0.333333으로 계속 끝이 없는 무한소수이다. 이 값을 어떻게 컴퓨터로 표현할 수 있을까? 위 C 코드의 실행결과는 어떻게 될까? 인간의 관점으로 생각해본다면 0.0부터 시작하여 0.1씩 더하므로 총 10번의 반복문이 실행될 것이라고 생각할 수 있다. 하지만 실제로 ..