Devjo의 코딩

인터넷 인터넷은 수십억 대의 컴퓨터를 모두 연결하는 기술 인프라입니다 물리적(이더넷 케이블) 또는 무선(WIFI, Bluetooth)으로 서로를 연결할 수 있는데 그림처럼 하나씩 서로를 연결하면 천문학적인 비용이 듭니다 이를 해결하기 위해 라우터(패킷 전송 장치)라는 중간 장치를 사용해 연결을 효율적으로 만듭니다 그리고 다시 그 라우터들을 하나의 라우터에 연결하는 것이죠 전세계의 라우터들을 연결하기 위해서 서로 멀리 떨어져 있는 라우터까지 연결해야합니다 하지만 장거리 전송에서 디지털 신호는 손상될 수 있으므로 모뎀을 이용해 아날로그 신호로 변환한 다음 전화 시설을 통해 전송합니다 ​ 네트워크의 디지털 신호 → 전화선의 아날로그 신호 모뎀에서 어느 라우터로 보내야 하는지 모르고 그 라우터에 액세스(접근) ..

스타트와 링크 2 초 512 MB 49286 24988 14525 47.398% 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Si..

백트래킹 해를 찾는 중에 현재 선택한 루트(노드)가 해와 관련이 없다는 것을 알아차리면 중단하고(가지치기) 이전 단계로 돌아가 다른 루트를 탐색한다 해가 될 수 있는 노드(유망한 노드)만을 이용해 부분 탐색을 수행한다 ​​ DFS 깊이 우선 탐색(Depth-First-Search), 맨 위 노드(루트)에서 하나의 가지(branch, 분기)를 완전히 탐색하고 다음 가지(분기) 넘어가는 방법 전체 탐색을 전제로 한다 ​ DFS의 사용 자기 자신을 호출(재귀 호출)하는 순환 알고리즘 형태이다 무한 루프에 빠지지 않기 위해 방문했다는 기록을 남겨준다 ​ 예시 위의 트리를 탐색하는 메소드를 논리로 만들어보자(전위순회) 1. 현재 위치를 탐색하고 왼쪽 아래 노드로 이동합니다 2. 만약 왼쪽 아래 노드가 없거나 방문..

연산자 끼워넣기 2 초 512 MB 50821 26712 16789 49.337% 문제 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이때, 주어진 수의 순서를 바꾸면 안 된다. 예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다. 1+2+3-4×5÷6 1÷2..

N-Queen 10 초 128 MB 50440 25920 16972 50.773% 문제 N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N이 주어진다. (1 ≤ N < 15) 출력 첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다. 풀이 백트래킹의 대표 문제 중 하나라고 한다. N-Queen에 규칙에 의해 NxN 체스판에 N개의 퀸을 놓기 위해서는 각 줄에 하나씩 퀸을 놓아야만 한다. 즉 첫째줄이든, 둘째줄이든 퀸은 무조건 존재한다는 뜻이다. 이 규칙에 의해 첫째줄에 퀸은 무조건 놓일 수 밖에 없으므로 첫째줄(1행)에 퀸이 어느 자리(열)에 오..

Stream Java 8부터 람다 표현식(lamda expression)을 사용할 수 있게 되었고 같은 시기에 Collection의 Stream 클래스를 사용할 수 있게 되었다 Stream 동작 Collection(ArrayList, Set, Map 등), 배열, 가변 매개변수, 특정 타입 난수, 람다 표현식, 파일, 빈 스트림 등 다양한 범위의 데이터를 가공할 수 있다. Iterator과 비슷한 방식으로 동작한다. 데이터를 복사해서 가져온 뒤 사용자가 원하는 연산을 수행한다. 원본 자료 → Stream 데이터 형식으로 복사 → 내부 연산 → 출력 (데이터 소모) *이미 원본을 복사한 자료이기 때문에 최종 연산 이후 내부 자료들이 소모된다(재사용X) 즉, Stream은 복사한 원본을 이용해 사용자가 원하..

N과 M (4) 1 초 512 MB 22116 17594 14249 79.603% 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 고른 수열은 비내림차순이어야 한다. 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이 이전 문제들을..

N과 M (3) 1 초 512 MB 29116 19087 14588 65.914% 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 M개를 고른 수열 같은 수를 여러 번 골라도 된다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이 어떤 조건 없이 반복문을 통해 계속 재귀호출을 하면 된다. 하지만 System.out.print(); 를 사용할 경우 시간초과(1초 경과)되기 때문에 버퍼..

N과 M (2) 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 30507 22946 16718 74.714% 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 고른 수열은 오름차순이어야 한다. 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이 순열을 떠올릴 수 있는 문제다. 예제 2을 참고하면, 다음을 반복한다 1을 선택한 후 1보다 큰 ..

N과 M (1) 시간 제한메모리 제한제출정답맞힌 사람정답 비율 1 초 512 MB 45383 27724 18525 60.385% 문제 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열 입력 첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 출력 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. 풀이 M에 따라서 반복문의 수가 달라지기 때문에 재귀없이 반복문으로 풀이하기 매우 어려워보인다. 백트래킹의 개념을 참고한 메소드 재귀 호..