목록전체 글 (291)

반갑습니다!

[백준] 2631줄 세우기

2631번: 줄세우기 boj.kr 풀이 이 문제는 LIS 알고리즘을 통해 해결할 수 있다. 키 순서가 오름차순으로 정렬된 아이들은 이동시킬 필요가 없다. 나머지 아이들을 최장 증가 수열에 속해있는 아이들 사이에 넣어주면 되기 때문에 LIS 알고리즘을 통해 최장 증가 수열의 길이를 계산한 뒤, 전체 어린이 숫자에서 빼주면 정답이 된다. 아래의 코드는 O(nlogn)의 복잡도를 갖는 LIS 알고리즘을 구현했다. 코드 C++
알고리즘 문제 풀이 2020. 10. 22. 15:28
[프로그래머스] 최고의 집합

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 이 문제는 그리디하게 해결했다. 이 문제의 핵심 아이디어는 곱하는 수들 간의 차이가 가장 적게 하는 것이다. 만약 s가 9이고, n이 3이라고 가정해보자. 이 때는 3, 3, 3을 곱해야 가장 크다는 것을 직관적으로 알 수 있을 것이다. 이번엔 s가 24이고 n이 6을 생각해보자. 이 역시 4, 4, 4, 4, 4, 4를 곱해야 최대값이 된다는 것을 알 수 있다. 지금까지의 예시는 모두 s를 n으로 나눈 나머지가 0인 경우였다. 이번엔 s가 n으로 나누어떨어지지 않는 경우를 생각해보자. s가 11이고 n..
알고리즘 문제 풀이 2020. 10. 22. 00:00
[프로그래머스] 섬 연결하기

프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 모든 섬을 연결하라는 의미는 결국 MST를 만들라는 말과 같다. 아래의 코드에서는 입력으로 들어온 costs 벡터를 edges 벡터에 저장하고 kruskal 알고리즘을 사용해 MST를 생성해서 해결했다. 코드 C++
알고리즘 문제 풀이 2020. 10. 21. 23:40
[백준] 1915 가장 큰 정사각형

1915번: 가장 큰 정사각형 boj.kr 풀이 이 문제는 동적 계획법을 사용해야한다. 이 문제의 핵심 아이디어는 위에서부터 탐색하면서 최대 크기의 정사각형을 갱신하는 것이다. 즉 dp[i][j] = (j, i)에서의 최대 정사각형의 길이가 된다. (수학에서 사용하는 좌표계를 기준으로 x, y 순으로 좌표를 표현했음을 참고할 것) 배열을 board[][]라고 하겠다. 그러면 board[i][j]가 1인 곳은 변의 길이가 1인 정사각형이다. 변의 길이가 2인 정사각형은 board[i][j], board[i-1][j], board[i][j-1], board[i-1][j-1]이 모두 1이어야 한다. 이 문제의 풀이는 여기서 힌트를 얻을 수 있다. 아래의 예시를 보면서 좀 더 알아보자. (0, 0 ~ 3, 0)..
알고리즘 문제 풀이 2020. 10. 20. 14:21
[Network] OSI 7 Layer

우연히 네트워크 계층에 대해 잘 설명된 영상을 보게되어 정리하게 되었습니다. 1. Pysical Layer 두 대의 컴퓨터가 통신하려면? 모든 파일과 프로그램은 0과 1의 나열 0과 1만 주고받으면 된다. 1을 보낼 때는 +5V의 전기를 전선으로 흘려보내고 0을 보낼 때는 -5V의 전기를 전선으로 흘려보내면 0과 1의 전송이 가능. → 이론상으로는 간단하지만 실제로는 잘 작동하지 않음 왜 그런지는 다음 그림을 보며 생각해보자. 만약 전자기파가 위의 그림과 같다면? → 주파수 값이 숫자 하나로 고정되지 않는다. 그런데 전선은 모든 주파수를 다 통과시킬 수 없기 때문에 데이터가 유실될 것이고, 데이터를 받는 컴퓨터에서는 전송한 데이터와 다른 데이터를 받게 될 것이다. 이런 수직선과 수평선이 있는 전자기파는 ..
CS 2020. 10. 20. 00:26
이전 Prev 1 ··· 4 5 6 7 8 9 10 ··· 59 Next 다음