기록하는 습관을 들이자

참고 https://m.blog.naver.com/kks227/220795165570 투 포인터(Two Pointers Algorithm), 슬라이딩 윈도우(Sliding Window) (수정: 2019-09-09) 조금 성향이 비슷하다고 생각하는 기법 2개를 함께 쓰려 합니다.첫 번째로 소개해드릴 기법은 투 포인터(tw... blog.naver.com 투 포인터 알고리즘에 대해 알아보겠습니다. 가끔 브루트 포스로 문제를 풀다보면 N이 큰 경우에는 시간초과가 발생하게 되는데, 그 때 완전 탐색이 아닌 다른 방법으로 어떻게 풀까하다가 알게 된 알고리즘입니다. ★ 완전 탐색 시 시간 초과가 나는 경우 ★ 1. 투 포인터 알고리즘 시도해보기 2. 이분 탐색 시도해보기(binary search) 3. dp(Dy..

보호되어 있는 글입니다.

시뮬레이션 문제를 풀어보았습니다. 어렵진 않지만 시간초과에 주의해야하는 문제입니다. 문제 설명 후 시간초과 났을 때 제가 주로 시도해보는 방법들도 같이 포스팅해보도록 하겠습니다. 문제보기 https://www.acmicpc.net/problem/5397 5397번: 키로거 문제 창영이는 강산이의 비밀번호를 훔치기 위해서 강산이가 사용하는 컴퓨터에 키로거를 설치했다. 며칠을 기다린 끝에 창영이는 강산이가 비밀번호 창에 입력하는 글자를 얻어냈다. 키로거는 사용자가 키보드를 누른 명령을 모두 기록한다. 따라서, 강산이가 비밀번호를 입력할 때, 화살표나 백스페이스를 입력해도 정확한 비밀번호를 알아낼 수 있다. 강산이가 비밀번호 창에서 입력한 키가 주어졌을 때, 강산이의 비밀번호를 알아내는 프로그램을 작성하시오...

삼성 SW역량테스트 기출 '드래곤 커브' 문제를 풀어보았습니다. 규칙을 찾아서 0~10세대 드래곤 커브 방향을 모두 구해놓고 시작하는 게 중요한 문제입니다. (역시 규칙 찾는 시뮬레이션 문제는 어려워,,,,) 문제보기 https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커브의 시작 점, d는 시작 방향, g는 세대이다. (0 ≤ x, y ≤ 100, 0 ≤ d ≤ 3, 0 ≤ g ≤ 10) 입력으로 주어지는 드래곤 커브는 격자 밖으로 벗어나지 않는다. ..

오늘은 삼성 SW역량테스트 기출 '사다리 조작' 문제를 풀어보았습니다. 백트래킹과 시뮬레이션 관련 문제로 시간 초과에 주의해야하는 문제입니다!! (완전탐색했다가 시간초과로 고생했다,,,) 문제보기 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선이 같은 위치를 갖는다. 아래 그림은 N = 5, H = 6 인 경우의 그림이고, 가로선은 없다. 초록선은 세로선을 나타내고, 초록선과 점선이 교차하는 점은 가로선을 놓을 수 있는 점이다. 가로선은 인접한 두 세로선을 연결해야 한다..

보호되어 있는 글입니다.

어렵진 않은 문제이나 실수하기 좋은 시뮬레이션 문제입니다! 틀리면 디버깅하기도 어렵,,,, 문제보기 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변끼리 연결되어 있어야 한다. 즉, 꼭짓점과 꼭짓점만 맞닿아 있으면 안 된다. 정사각형 4개를 이어 붙인 폴리오미노는 테트로미노라고 하며, 다음과 같은 5가지가 있다. 아름이는 크기가 N×M인 종이 위에 테트로미노 하나를 놓으려고 한다. 종이는 1×1 크기의 칸으로 나누 www.acmicpc.net 나의 풀이 테트로미노 블록을 올..

오늘은 백준 14999 주사위 굴리기 문제를 풀어보았습니다. 별도의 알고리즘이 필요하지 않은 시뮬레이션 문제입니다. 문제보기 https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지도에 쓰여 있는 수가 북쪽부터 남쪽으로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 주사위를 놓은 칸에 쓰여 있는 수는 항상 0이다. 지도의 각 칸에 쓰여 있는 수는 10을 넘지 않는 자연수 또는 0이다. 마 www.acmicpc.net 나..

시뮬레이션 문제를 연습해보고자 푼 문제입니다! 백준 1057번 토너먼트 문제입니다. 문제 보기 https://www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 한다. 이긴 사람은 다음 라운드에 진출하고, 진 사람은 그 라운드에서 떨어진다. 만약 그 라운드의 참가자가 홀수명이라면, 마지막 번호를 가진 참가자는 다음 라운드로 자동 진출한다. 다음 라운드에선 다시 참가자의 번호를 1번부터 매긴다. 이때, 번호를 매기는 순서는 처음 www.acmicpc.net 나의 풀이 처음 생각> 리스트를 이용하면 ..