전체 글

2485 가로수

문제 https://www.acmicpc.net/problem/2485 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 접근 모든 가로수의 간격이 같으려면 주어진 가로수의 간격의 최대공약수를 구해야 한다고 생각해서 유클리드 호제법을 이용했다. 각 간격을 저장하고 저장된 모든 간격에 대한 최대공약수를 계산한 후, 각 간격을 최대공약수로 나눈 몫 - 1을 합해서 정답을 구한다. 풀이 def gcd(x, y): if x % y == 0: return y return gcd(y, x % y) n = int(i..

소켓 프로그래밍 (JAVA)

소켓 프로그래밍은 소켓을 이용한 통신 프로그래밍을 말한다. 소켓이란 프로세스간의 통신에 사용되는 양쪽의 endpoint를 의미하며, 소켓 통신에 사용되는 프로토콜이 TCP냐 UDP냐에 따라 다른 종류의 소켓을 이용한다. TCP와 UDP TCP/IP 프로토콜은 이기종 시스템간의 통신을 위한 표준 프로토콜로, 프로토콜의 집합이다. TCP와 UDP 모두 TCP/IP 프로토콜에 포함되어 있으며, OSI 7계층의 전송계층에 해당한다. TCP UDP 연결방식 연결기반 - 연결 후 통신 - 1:1 통신 비연결기반 - 연결없이 통신 - 1:1, 1:N, N:N 통신 특징 데이터의 경계를 구분하지 않는다. (byte-stream) UDP보다 전송속도가 느리다. 신뢰성 있는 데이터 전송 - 데이터의 전송순서 보장 - 데이..

네트워킹 기본지식

네트워킹이랑 두 대 이상의 컴퓨터를 케이블로 연결하여 네트워크를 구성하는 것을 말하며, 컴퓨터들을 서로 연결하여 데이터를 주고받거나 주변기기를 공유할 수 있다. 전 세계의 컴퓨터가 인터넷이라는 하나의 거대한 네트워크를 구성하며, 인터넷을 통해 다양하고 방대한 양의 데이터를 공유하는 것이 가능해졌다. ※참고: 자바에서 제공하는 java.net 패키지를 사용하면 네트워크 애플리케이션의 데이터 통신 부분을 쉽게 작성할 수 있다. 클라이언트/서버 클라이언트/서버는 컴퓨터 간의 관계를 역할로 구분하는 개념으로, 서버는 서비스를 제공하는 컴퓨터이고, 클라이언트는 서비슬르 사용하는 컴퓨터가 된다. 일반적으로 서버는 다수의 클라이언트에게 서비스를 제공하는 소프트웨어가 실행되는 컴퓨터로, 고사양의 하드웨어를 갖추고 있다..

19235 모노미노도미노

문제 https://www.acmicpc.net/problem/19235 19235번: 모노미노도미노 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 접근 문제에 주어진 대로 구현하면 되는 시뮬레이션 문제 어떻게 풀어야 간단할까?? 초록색 보드와 파란색 보드에 대한 처리를 함수 하나로 구현하면 편하기 때문에 파란색 보드를 시계방향으로 90도회전시켜서 생각한다. 풀이 1. 블록 처리 1번 블록: 초록색 보드와 파란색 보드 모두 1번 블록으로 처리 2번 블록: 초록색 보드는 2번 블록으로 파란색 보드는 3번 블록으로 처리 3번 블록: ..

16960 스위치와 램프

문제 https://www.acmicpc.net/problem/16960 16960번: 스위치와 램프 첫째 줄에 스위치의 수 N, 램프의 수 M이 주어진다. 둘째 줄부터 N개의 줄에는 스위치에 대한 정보가 주어진다. 스위치 정보의 첫 번째 정수는 그 스위치와 연결된 램프의 수이고, 이후 연결된 램 www.acmicpc.net 접근 N개의 스위치마다 해당 스위치를 누르지 않았을 때 M개의 모든 램프를 켤 수 있는지 확인한다. 한 스위치에 M개의 램프가 연결된 경우에는 항상 N-1개의 스위치로 모든 램프를 켤 수 있기 때문에, 실제 시간 복잡도는 이론상 계산한 O(N^2 * M) 보다 훨씬 작을 것이다. 풀이 각 스위치에 연결된 램프를 저장하기 위해 딕셔너리 사용 각 스위치를 누르지 않았을 때 N-1개의 스..

1781 컵라면

문제 https://www.acmicpc.net/problem/1781 1781번: 컵라면 상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라 www.acmicpc.net 접근1 (틀림) 가장 먼저 생각한 방법은 딕셔너리를 사용해서 데드라인 별로 얻을 수 있는 컵라면을 리스트 형태로 저장한 후 정렬해서 각 데드라인 일자마다 문제 풀이가 가능한 갯수만큼 더하는 방법으로 작성 But, 많은 컵라면을 얻을 수 있는 문제의 데드라인 값이 큰 경우, 해당 문제를 풀기 전 데드라인 값이 작은 문제들을 먼저 풀어버려서 많은 컵라면을 얻을 수 있는 문제는 못 풀게될 가능성) 접근2 ..

17175 피보나치는 지겨웡~

문제 https://www.acmicpc.net/problem/17175 17175번: 피보나치는 지겨웡~ 혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서 www.acmicpc.net 접근 출력을 1000000007로 나눈 나머지로 하라는 것은 피보나치 함수 호출의 숫자가 1억보다 큰값이 존재한다는 뜻이므로, 실제로 피보나치 함수를 구현해서 호출 횟수를 세는 방법은 시간초과가 난다. (제한시간 1초) 어떠한 값 i에 대한 피보나치 함수 호출 횟수는 i-1의 피보나치 함수 호출 횟수와 i-2의 피보나치 함수 호출 횟수의 합이므로 다이나믹 프로그래밍으로 접근 풀이 dp[i]를..

15918 랭퍼든 수열쟁이야!!

문제 https://www.acmicpc.net/problem/15918 15918번: 랭퍼든 수열쟁이야!! 세 자연수 n, x, y가 주어진다. (2 ≤ n ≤ 12, 1 ≤ x < y ≤ 2n, 1 ≤ y-x-1 ≤ n) www.acmicpc.net 접근 비슷한 문제를 풀었던 적이 있어서 바로 백트래킹으로 접근 풀이 먼저 x와 y 사이에 숫자가 몇개(diff) 들어가는지 계산해서, 결과 배열의 x번째와 y번째를 diff로 채우고 시작 결과 배열의 idx를 기준으로 1부터 n까지의 숫자 중 이전에 사용하지 않았던 숫자(i)에 대해 idx번째와 idx+i+1번째에 해당 숫자를 집어넣을 수 있는지 확인하고, 집어넣을 수 있으면 결과 배열에 숫자를 채우고 idx+1로 넘어간다. 만약 해당 idx번째에 이미 ..

11411 합 구하기

문제 https://www.acmicpc.net/problem/11441 11441번: 합 구하기 첫째 줄에 수의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (-1,000 ≤ Ai ≤ 1,000) 셋째 줄에는 구간의 개수 M이 주어진다. (1 ≤ M ≤ 100,000) 넷째 줄부터 M개의 줄에는 www.acmicpc.net 접근 주어진 수의 개수 n과 구간의 수 m의 범위가 1