JH 개발 블로그

https://www.acmicpc.net/problem/1911   음... 그냥 단순하게 정렬한 후 널빤지의 개수를 구하면 된다.주의해야 할 건 널빤지의 길이는 정해져 있기 때문에 물웅덩이가 아닌 위치도 널빤지로 덮을 수 있다는 점. 만약 물웅덩이의 위치가 [1,5] [10,15] 이고, 널빤지의 길이가 20이라면 널빤지의 모든 물웅덩이를 커버 가능하다. 이부분만 생각해서 풀면 되는 간단한(?) 문제였다. 딱히 정렬말고 알고리즘을 쓸 필요도 없음...  물웅덩이는 최대 만개이다. 웅덩이의 위치값은 최소 0에서 최대 10억이다. 시간복잡도를 고려하면 범위를 for문으로 돌리면 안된다는 걸 알 수 있다. import java.io.*;import java.util.*;public class Main { ..

https://www.acmicpc.net/source/80479844 문제를 읽어보면, 서로 바라 볼 수 있는 사람의 쌍의 수를 구해야 한다.조건은 두 사람 사이에, 둘중 아무나보다 키가 큰 사람이 존재하면 안된다는 것이다. ( 키가 동일하면 상관없다 )처음엔 막연하게 이중포문을 생각했지만 N이 최대 50만 이기 때문에.. 절대 안된다 !  어렵다.. 머리 좋아지고 싶다..! 결국 보게 된 풀이.. 스택을 사용한다.   문제풀이 아이디어를 정리하면 다음과 같다.1. 스택 만드는데 내림차순 스택임 (이유는 아래에)2. 내림차순 스택을 만드는 과정에서 분기처리 잘하자  여기서 중요한점은 스택 내에  '앞으로 쌍이 될 가능성이 없는 사람' 은 제거한다. 예를들어 스택에 [3 2 1] 이 쌓여있다고 하자. 네..

https://www.acmicpc.net/problem/1644   문제를 읽어보면, "소수의 연속합"으로 특정 자연수를 나타내야 한다.예시에 나와있듯이 20은 7+13으로 나타낼 수 있지만 "연속된 소수" 들이 아니기 때문에 (7과 13 사이에는 11이 있다)잘못된 경우이다. 그럼 문제를 어떻게 풀어야 할지 생각해보면1. 소수 리스트를 구한다. 특정 값이 소수인가? 가 아닌 범위내의 모든 소수들의 값을 구하는 것이기 때문에에라토스테네스의 체를 사용한다.  시간복잡도는  O(n * log(log n)) 2. 소수 리스트를 구했으면, "연속된 소수" 로 나타내야 하기 때문에 투포인터로 풀이가 가능할 것 같다.  에라토스테네스의 체와 투포인터로 풀이한 코드는 아래와 같다. import java.io.Buf..

https://softeer.ai/practice/6250 Softeer - 현대자동차그룹 SW인재확보플랫폼 softeer.ai 배열에 점수와 인덱스를 잘 담아서 정렬 하면 되는 문제였다. 1. 배열에 점수와 인덱스를 저장한다.2. 배열을 내림차순 정렬한다. ( 점수 기준으로 )3. 내림차순 정렬된 배열의 인덱스를 바탕으로 정답 배열의 인덱스에 rank를 매긴다. (내림차순 배열의 이전 요소가 지금 요소와 같다면 rank 값은 그대로, 아니라면 i+1)  import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader ..

언어별 시간/메모리언어시간메모리JavaScript1초1024MBC1초1024MBC++1초1024MBJava1초1024MBPython2초1024MB대학교 학부생활을 마치고 현대자동차에 프로그래머로 취직한 사회초년생 현빈이는 팀장님에게 보안에 관련한 지식이 하나도 없음을 들키고 말았다. 그래서 현빈이는 업무시간 틈틈이 보안과 관련된 주제들을 공부하고 있다.오늘 공부할 주제는 암호화 방식중 하나인 Playfair cipher(플레이페어 암호)다. Playfair cipher는 알파벳으로 이루어진 어떤 문자열(평문; plaintext)을 암호화하는 방법으로, 이를 위해 알파벳으로 이루어진 문자열인 키(key)가 필요하다. Playfair cipher는 빈도분석을 어렵게 하기 위해 한번에 두 글자 단위로 암호화를..

언어별 시간/메모리언어시간메모리JavaScript1초1024MBC1초1024MBC++1초1024MBJava1초1024MBPython1초1024MBSam은 팀장님으로부터 차량이 이동 가능한 시나리오의 수를 찾으라는 업무 지시를 받았습니다. 이동은 숫자 0과 1로만 이루어져 있는 n x n 크기의 격자 위에서 일어납니다. 숫자 0은 빈 칸을 의미하며, 숫자 1은 해당 칸이 벽으로 막혀 있음을 의미합니다. 아래는 n이 3인 경우의 예시입니다. 0 0 00 0 00 0 1 차량은 n x n 격자 내에서 m개의 지점을 순서대로 방문하려고 합니다. 이 때 이동은 항상 상하좌우 중 인접한 칸으로만 이동하되 벽은 지나갈 수 없으며, 한 번 지났던 지점은 다시는 방문해서는 안 됩니다. 이러한 조건 하에서 차량이 이동 가..

from collections import deque def rotate(lr, lc, rr, rc, board): locs = [] for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)): nlr, nlc, nrr, nrc = lr + dr, lc + dc, rr + dr, rc + dc if board[nlr][nlc] == 1 or board[nrr][nrc] == 1: continue locs.append((nlr, nlc, nrr, nrc)) if lr == rr: if lc < rc: if board[lr - 1][lc + 1] == 0 and board[lr - 1][lc] == 0: # 반시계 locs.append((lr, lc, lr - 1, lc)) if..

1. 순열을 이용하여 완전탐색 from itertools import permutations from bisect import bisect_right def solution(n, weak, dist): l = len(weak) weak_line = weak + [w+n for w in weak] answer = [] for friends in permutations(dist): for i in range(l): cnt = 0 position = weak[i] for friend in friends: cnt += 1 position += friend if position < weak_line[i+l-1]: position = weak_line[bisect_right(weak_line,position)] e..