티스토리

live the life you love

검색하기

블로그 홈

live the life you love

paris-in-the-rain.tistory.com/m

IT 프로그래밍 코딩테스트 Devops

구독자: 12

방명록 방문하기

주요 글 목록

[BOJ 백준, 삼성 SW 역량 테스트 기출 문제] 20058번 : 마법사 상어와 파이어스톰 Python, 파이썬) www.acmicpc.net/problem/20058 20058번: 마법사 상어와 파이어스톰 마법사 상어는 파이어볼과 토네이도를 조합해 파이어스톰을 시전할 수 있다. 오늘은 파이어스톰을 크기가 2N × 2N인 격자로 나누어진 얼음판에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c www.acmicpc.net DFS 함수에서 재귀가 터져서 sys.setrecursionlimit을 사용했다. 실제 삼성 코딩테스트에서는 sys 라이브러리를 사용할 수 없으니, DFS를 재귀로 짜지 않고 스택으로 짜거나 BFS로 대체하여 풀어야 할 듯 하다. 회전하는 부분을 제대로 구하지 못해서 다른 블로그 글을 참조했다. 리스트의 회전은 어렵다.. 소스코드 import sys, copy sys.setrecursionl.. 공감수 0 댓글수 0 2021. 3. 25.
[BOJ 백준] 20056번 : 마법사 상어와 파이어볼 (Python, 파이썬) www.acmicpc.net/problem/20056 20056번: 마법사 상어와 파이어볼 첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치 www.acmicpc.net 문제에서 구현하라는 대로 푸는 전형적인 시뮬레이션 문제였다. 하지만, 시간이 3980ms로 가까스로 TLE를 면한듯 하다. 같은 칸에 파이어볼이 여러개 있을 수 있으므로 board 안에 deque를 넣어서 파이어볼이 추가로 들어오면 append 시켜줬다. 소스코드 import sys, copy from collections import deque dy = [-1, -1, .. 공감수 0 댓글수 0 2021. 3. 25.
[BOJ 백준] 2473번 : 세 용액(Python, 파이썬) www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 투 포인터를 활용해서 문제를 풀었다. 기존의 투 포인터와 다른 점은 확인해야 할 값이 1개 더 있는것인데, 이것은 추가적인 포인터를 1개 더 두어 해결하였다. 포인터가 1개 더 추가 되면서 포인터끼리 겹치는 경우가 발생할 수 있기 때문에 따로 체크를 해줘야 한다. 세 용액의 합이 0이 되는 경우는 여러개 있을 수 있고, 그 중 아무거나 출력하면 되기 때문에 세 지점에서의 값들의 합이 0 이.. 공감수 0 댓글수 0 2021. 2. 20.
[BOJ 백준] 20168번 : 골목 대장 호석 - 기능성(Python, 파이썬) www.acmicpc.net/problem/20168 20168번: 골목 대장 호석 - 기능성 첫 줄에 교차로 개수 N, 골목 개수 M, 시작 교차로 번호 A, 도착 교차로 번호 B, 가진 돈 C 가 공백으로 구분되어 주어진다. 이어서 M 개의 줄에 걸쳐서 각 골목이 잇는 교차로 2개의 번호와, 골목의 www.acmicpc.net 다익스트라 문제를 풀려고 했는데, 백트래킹으로 풀었다. 처음에는 문제의 설명이 조금 헷갈렸는데, 고려해야할 조건은 다음과 같았다. 가진 돈을 목적지까지 도착하기 전에 전부 사용하지 않기 목적지에 도착했다면 지금까지 지나온 노드 중 가장 비용이 큰 값이 어떤 것인가? 목적지에 도착하는 길이 2개 이상인 경우 가장 비용이 큰 값 중 최소가 정답 위의 조건들을 백트래킹에 맞게 풀어주.. 공감수 0 댓글수 0 2021. 2. 14.
[BOJ 백준] 1806번 : 부분 합(Python, 파이썬) www.acmicpc.net/problem/18061806번: 부분합첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.www.acmicpc.net 문제의 이름에서도 알 수 있듯 부분합을 활용하는 문제이다. 부분합이란 시작점과 끝점을 정해서 해당 구간 내에 있는 원소들의 합을 구하는 것이다. for i in range(1, n+1): prefix[i] = prefix[i-1] + _list[i-1] 이 문제는 굳이 부분 합을 사용하지 않고, 투 포인터로도 풀 수 있는 문제였다. 투 포인터 소스코드import sys n,s = map(int, inp.. 공감수 0 댓글수 0 2021. 2. 11.
[BOJ 백준] 9376번 : 탈옥(Python, 파이썬) www.acmicpc.net/problem/9376 9376번: 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 이 감옥은 1층짜리 건물이고, 상근이는 방금 평면도를 얻었다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타 www.acmicpc.net 첫 플레문제였다. 단순히 다익스트라나 BFS로 하면 될 것 같았는데 아무리 고민을 해도 시간복잡도를 알맞게 할 수 없을 것 같아서 다른 블로그를 보고 풀었다. 찾아보니 이런 유형의 문제는 0-1 BFS라고 한다. 가중치가 0과 1만 있는 그래프에서 사용할 수 있는데, 기존의 BFS는 방향탐색을 마치고, 다음에 갈 지점을 큐에 삽입할 때 단순히 큐의 맨뒤에 push 했다. 또한, 다익스트라의 경우도 우선순위 큐를 사용하여 항.. 공감수 0 댓글수 0 2021. 2. 7.
[BOJ 백준] 10711번 : 모래성(Python, 파이썬) www.acmicpc.net/problem/10711 10711번: 모래성 첫째 줄에는 모래성의 가로세로 격자 크기 H, W가 주어진다. (1 ≤ H, W ≤ 1,000) 그 다음 H줄에 걸쳐 W개의 문자로 모래성의 상태를 나타내는 문자가 들어온다. 각 문자는 1~9 사이의 숫자, 또는 '.' 이 www.acmicpc.net 맨 처음에는 단순히 전체 배열을 탐색하는 BFS 코드를 짰더니 시간 초과가 발생했다. 최악의 경우 O(N^3) 까지 들어 올 수 있기 때문에 그렇다. 그래서 조금 다른 방법을 사용했다. 비어있는 부분의 위치를 모두 큐에 삽입하고, 이를 기준으로 BFS 탐색을 한다. 8방 탐색을 하는 동안 모래성을 만나면 해당 모래성에서 1을 빼주고, 큐에서 popleft를 한다. 만약 모래성의 값이.. 공감수 0 댓글수 0 2021. 2. 5.
[BOJ 백준] 14620번 : 꽃길(Python, 파이썬) www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 백트래킹을 활용하는 문제였다. dfs 함수에서 반복문을 돌면서 백트래킹을 하는 부분을 블로그 참고해서 풀었다. 소스 코드 import sys sys.stdin = open("input.txt", "r") flower_dir = [(0,0),(-1,0),(1,0),(0,-1),(0,1)] # 현위치, 상, 하, 좌, 우 n = int(input()) board = [list(map(int, input().spl.. 공감수 0 댓글수 0 2021. 1. 29.
[BOJ 백준] 1747번 : 소수&팰린드롬(Python, 파이썬) www.acmicpc.net/problem/1747 1747번: 소수&팰린드롬 어떤 수와 그 수의 숫자 순서를 뒤집은 수가 일치하는 수를 팰린드롬이라 부른다. 예를 들어 79,197과 324,423 등이 팰린드롬 수이다. 어떤 수 N (1 ≤ N ≤ 1,000,000)이 주어졌을 때, N보다 크거나 같고, www.acmicpc.net 소수 판별과 팰린드롬을 사용하는 문제이다. 파이썬의 경우 팰린드롬은 굉장히 쉽게 판별할 수 있으므로 패스한다. 소수 판별은 에라토스테네스의 체 2부터 제곱근까지 나머지 확인 2가지 방식으로 테스트를 해봤는데, 시간복잡도는 크게 차이나지 않는 것 같다. 다만, 소수의 갯수보다 팰린드롬의 갯수가 더 많으므로 팰린드롬인지 확인해주는 것을 먼저 해주는게 시간복잡도 측면에서 효율적이.. 공감수 0 댓글수 0 2021. 1. 25.
[BOJ 백준] 4358번 : 생태학(Python, 파이썬) 4358번: 생태학 (acmicpc.net) 4358번: 생태학 프로그램은 여러 줄로 이루어져 있으며, 한 줄에 하나의 나무 종 이름이 주어진다. 어떤 종 이름도 30글자를 넘지 않으며, 입력에는 최대 10,000개의 종이 주어지고 최대 1,000,000그루의 나무가 주어 www.acmicpc.net 문제는 골드 4였지만, 딕셔너리를 사용하면 쉽게 풀리는 문제다. 단순한 딕셔너리가 아니라, defaultdict를 썼다면 if, else 분기를 안해도 됐을 것이다. 주의해야할 부분은 다음과 같다. 입력 소숫점 넷째짜리까지 계산 소숫점 넷째짜리까지 출력 우선 입력이 밑도 끝도 없이 들어와서 밑도 끝도 없이 끝난다. 들어오는 나무의 개수라도 알려주면 좋겠지만 그딴게 없다. 더 이상 입력이 들어오지 않을 때 까.. 공감수 2 댓글수 0 2021. 1. 24.
[BOJ 백준] 15565번 : 귀여운 라이언 (Python, 파이썬) www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 슬라이딩 윈도우를 활용하는 문제였다. 문제에서 K개 이상의 라이언 인형을 포함하는 가장 작은 연속된 인형들의 집합의 크기를 구하라고 했으므로 일단 어피치는 신경쓰지말고 라이언 인형이 딱 K개가 되는 구간만 확인해주면 된다. 항상 K개가 되는 것을 확인해야 하므로 슬라이딩 윈도우를 활용할 수 있는 것이다. 예제에서 라이언 인형의 위치는 0, 4, 6, 9 이다. 라이언 인형은 총 4개가 있으며 K가 3이기 .. 공감수 0 댓글수 0 2021. 1. 23.
[BOJ 백준] 11659번 : 구간 합 구하기 4 (Python, 파이썬) www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 누적 합을 구해놓으면 쉽게 풀리는 문제였다. 단, python의 경우 input( )이 아닌 sys.stdin.readline()을 써야 시간초과에 걸리지 않는다. 소스코드 import sys n, m = map(int, sys.stdin.readline().split()) _list = list(map(int, sys.stdin.readline().split())) _sum = [0 f.. 공감수 0 댓글수 0 2021. 1. 23.
[BOJ 백준, 삼성 SW 역량 테스트 기출 문제] 14500번 : 테트로미노 (Python, 파이썬) www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 문제를 잘 읽자! 문제를 잘 못 읽어서 1시간을 고민하다가 질문검색을 통해 코드를 보고 문제를 잘못 읽은것을 깨달았다. 테트로미노 "하나"를 적절히 놓아서 테트로미노가 놓인 칸에 쓰여 있는 수들의 합을 최대로 하는 프로그램을 작성하시오. 주어진 종이에 여러 종류의 테트로미노를 놓고 그 중에 최대를 구하는 것이 아니다. 최대 500x500 크기의 종이에 테트로미노 1개를 놓고 놓인 부분의 합이 최대가 되는 것을 .. 공감수 0 댓글수 1 2021. 1. 15.
[BOJ 백준] 13913번 : 숨바꼭질4 (Python, 파이썬) www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 기본적인 BFS에 방문했던 경로를 따로 저장하여 경로를 역순으로 탐색하는게 추가된 문제였다. 수빈이가 갈 수 있는 3가지 경로을 모두 큐에 같이 저장하고 해당 경로마다 탐색을하면 분명 시간초과 또는 메모리 초과가 발생할 것이다. 기본적으로 수빈이가 이미 갔던 경로는 파악하기 위해서는 bool 타입의 visited 배열로 단순히 방문체크만 해주는 것에 한가지를 더 추가해야한다. .. 공감수 0 댓글수 0 2021. 1. 13.
[BOJ 백준] 9019번 : DSLR (Python, 파이썬) www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 카테고리 분류에 BFS가 있어서 당황했던 문제이다. 이런류의 문제를 BFS에 접목시킨다는 발상을 하기가 어렵다. 실제 코테에 나왔다면 못풀었을 것이다. 어려웠고 놓쳤던 부분은 다음과 같다. '123' 을 R 연산하면 312가 아니라, '2031'이된다. 숫자는 무조건 4자리로 고정되어있기 때문이다. 숫자 하나당 4가지의 경우의 수가 발생해서 4^n 만큼의 경우의 수가 나올 거 같은데, 어떻게 시간 .. 공감수 3 댓글수 0 2021. 1. 11.
[BOJ 백준] 10825번 : 국영수 (Python, 파이썬) www.acmicpc.net/problem/10825 10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 간단한 문제였지만 파이썬에서 람다를 활용하여 정렬하는 법을 알 수 있었다. 리스트에 들어오는 원소는 (Junkyu, 50, 60, 100)이다. 맨 앞에 문자가 있으므로 뒤에 숫자들도 문자로 인식된다. 그렇기 때문에 람다식에서 숫자들을 int로 형변환 해줘야 한다. 정렬순서는 문제에 나와있는 것과 동일하게 하면된다. 국어 점수가 감소하는 순서로 국어 점수가 같으면 영어 점수가 증가하는 순서.. 공감수 0 댓글수 0 2021. 1. 9.
[BOJ 백준] 2580번 : 스도쿠(Python, 파이썬) www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net 백트래킹을 활용하는 문제였다. 스페셜 저지이므로, 답이 여러개 나올 수 있다. 3x3으로 처리된 부분을 어떤식으로 검사 해야할 지 아이디어가 잘 안떠올랐다. 구현 로직 입력받은 스도쿠에서 0이 들어간 곳의 좌표를 따로 저장한다 0이 있는 위치에 들어갈 수 있는 후보 숫자들을 리스트에 저장한다 1부터 9까지 저장된 리스트(numbers)를 생성한다. 스도쿠 전체를 탐색하며 행, 열, 3x3 배열에 있는 0이 아닌.. 공감수 0 댓글수 1 2021. 1. 9.
[BOJ 백준] 2638번 : 치즈 - 파이썬, Python www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 문제의 구현 로직은 다음과 같다. 모든 치즈가 다 녹았는지 확인한다. 남은 치즈가 있다면 전부 녹을 때 까지 아래의 과정을 반복한다. 다른 치즈 내부 공간에 있지 않은 치즈들 중 외부 공기와 2개 변 이상 접촉한 치즈를 체크한다. 체크된 치즈를 녹인다. 1, 3번은 크게 어렵지 않은데 2번이 조금 까다로운 편이었다. 단순히 상,하,좌,우 중 공기인 칸이 2개 이상인지만 확인하면 안된다. 왜냐하면 상하좌.. 공감수 0 댓글수 4 2021. 1. 8.
[BOJ 백준] 9205번 : 맥주 마시면서 걸어가기 - 파이썬, Python https://www.acmicpc.net/problem/9205 9205번: 맥주 마시면서 걸어가기 송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. www.acmicpc.net 전형적인 BFS 탐색을 활용해서 푸는 문제였다. 상근이는 무조건 집 -> 편의점 -> 편의점 .. -> 페스티벌 로 움직이기 때문에 다음번 편의점에 가서 항상 맥주를 최대로 살 수 있다. 굳이, 이동할 때 마다 이동거리를 50m로 나누면서 이동 가능 여부를 판단하지 않고 맥주를 20개 먹었을 때 갈 수 있는 최대 거리인 1,000m를 기준으로 다음번 편의점 또는 페스티벌 장 까지의 거리가 1.. 공감수 0 댓글수 0 2021. 1. 7.
[BOJ 백준] 9466번 : 텀 프로젝트 - 파이썬, Python www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net DFS를 활용해 사이클 여부를 판단하는 문제이다. 사이클 여부를 판단하는데 익숙하지 않아서 다른 사람들의 코드를 보고 풀었다. 꼭 복습해야한다, 소스코드 import sys sys.setrecursionlimit(111111) # 재귀 깊이 설정 sys.stdin = open("input.txt", "r") def dfs(cur): global cnt, visited, done visited[cur] = True n.. 공감수 0 댓글수 0 2021. 1. 6.
[BOJ 백준, 삼성 SW 역량 테스트 기출 문제] 14888번 : 연산자 끼워넣기 - Python www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 모든 경우의 수를 전부 확인해서 원하는 답을 구하는 전형적인 완전탐색 문제였다 숫자의 위치는 고정되어있고 모든 연산자를 사용해야 하므로 연산자의 순서만 정해주면된다. 사용 할 수 있는 연산자의 순서를 정할 때는 순열을 사용한다. 연산자가 최대 10개까지밖에 없으므로 파이썬 내장 라이브러리를 활용하여 풀었다. 주의할 점은 나누기 연산의 경우 음수로 나눠지는 .. 공감수 0 댓글수 1 2021. 1. 4.
[BOJ 백준] 15655번 : N과 M(6) - Python www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 조합을 구하는 문제이다. 순열과 달리, 사용했던 원소를 체크해주는게 관건이다. # 조합 n, m = map(int, input().split()) data = list(map(int, input().split())) data.sort() result = [] checked = [False]*n def dfs(idx, count): if count == m: print(*result) return for.. 공감수 0 댓글수 0 2021. 1. 3.
[BOJ 백준] 15654번 : N과 M(5) - Python www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 순열을 구하는 문제이다. N과 M(1)이 순열이었는데, 이와 다른점은 N과 M(5)의 경우 순열을 만들어야 할 숫자가 따로 주어진다는 점이다. 문제 조건에서 오름차순으로 출력하라고 했기 때문에 입력받은 숫자를 정렬해주기만 하면, 일반적인 순열을 구하는 것과 동일하다 이번에도 백트래킹으로 풀었다. n, m = map(int, input().split()) data = list(map(int, input(.. 공감수 0 댓글수 0 2021. 1. 3.
[BOJ 백준] 15652번 : N과 M(4) - Python www.acmicpc.net/problem/15652 15652번: N과 M (4) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N과 M(4)는 중복 조합을 구하는 문제이다. 이번에도 내장 라이브러리를 사용하지 않고 백트래킹 방식으로 직접 구현하였다. n, m = map(int, input().split()) result = [] def dfs(idx, count): if count == m: print(*result) return for i in range(idx, n): result.append(i+1) dfs(i, count+1).. 공감수 0 댓글수 0 2021. 1. 3.
[BOJ 백준] 15651번 : N과 M(3) - Python www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 백트래킹을 연습하기 위해 내장 함수를 사용하지 않고 직접 함수를 구현해서 문제를 풀었다 N과 M(3)는 중복순열을 구하는 문제이다. 순열을 구하는 것과 크게 차이는 없고 중복된 값을 따로 체크하지 않기 때문에 따로 체크할 부분은 없다. 소스코드 n, m = map(int, input().split()) result = [] def dfs(count): if count == m: print(*result) re.. 공감수 0 댓글수 0 2021. 1. 3.
[BOJ 백준] 2467번 - 용액 www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 이전의 문제 두 용액(paris-in-the-rain.tistory.com/59)에서는 절댓값 대소 비교로 문제를 풀었다. 두 문제의 차이는 정렬 여부인데, 두 용액 문제는 정렬이 안되어 있고, 이 문제는 정렬이 되어있다. 이 문제는 투포인터를 활용했다. 포인터의 시작점을 맨 처음 인덱스(p1), 맨 끝 인덱스(p2)로 두었다. 해당 인덱스의 숫자를 더하여 값을 확인한다. 두 숫자를 더해서 0에 가까운 값.. 공감수 0 댓글수 0 2020. 10. 21.
[BOJ, 삼성 SW 역량 테스트 기출 문제] 19238번 : 스타트 택시 www.acmicpc.net/problem/19238 19238번: 스타트 택시 첫 줄에 N, M, 그리고 초기 연료의 양이 주어진다. (2 ≤ N ≤ 20, 1 ≤ M ≤ N2, 1 ≤ 초기 연료 ≤ 500,000) 연료는 무한히 많이 담을 수 있기 때문에, 초기 연료의 양을 넘어서 충전될 수도 있다. 다 www.acmicpc.net 구현사항만 잘 지키면 되는 전형적인 시뮬레이션 문제였다. 손님을 태우러 택시가 가는 것과, 손님을 태우고 목적지로 가는 것은 같은 방식으로 구현을 할 수 있으므로 flag 변수를 통해 1개의 함수로 처리했다. 문제해결 현재 손님의 위치, 목적지를 입력받고 각각 다른 배열에 저장한다. 비교함수를 만들어 문제의 조건을 처리한다. 가장 가까운 승객 / 행 번호 작은 승객 / 열.. 공감수 0 댓글수 0 2020. 10. 9.
[BOJ, 삼성 SW 역량 테스트 기출 문제] 16236번 : 아기상어 www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가�� www.acmicpc.net 문제 조건을 잘 읽고 그대로 구현하면 되는 문제이다. 구현 자체는 쉬운데, 문제를 제대로 안읽어서 놓친 조건과 문제에서 정보를 안준 것이 하나 있어서 좀 오래 걸렸다. 문제 조건을 요약하면 아래와 같다. 아기 상어의 이동 자신의 크기보다 큰 물고기가 있는 칸은 지나갈 수 없음 나머지 칸은 모두 지나갈 수 있다. 물고기 먹기 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있다. 크기가 같은 물고기.. 공감수 0 댓글수 0 2020. 10. 9.
[BOJ 백준] 2470번 : 두 용액 www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 처음에는 산성, 알칼리 용액을 나눠서 계산하다 보니 계속 틀려서 블로그를 참고하여 풀었다. 투 포인터를 활용해서 풀려고 했는데, 풀고나니 이 문제는 절댓값을 활용해서 푸는 것이 더 효율적이라고 생각한다. 기존 접근 방식(오답) 산성 용액과 알칼리 용액을 나눠서 저장 후 정렬한다 알칼리 용액만 있는 경우, 산성 용액만 있는 경우 각 배열의 첫번째, 두번째 원소의 값이 최솟값이므로.. 공감수 0 댓글수 0 2020. 10. 3.
[BOJ 백준] 12757번 : 전설의 JBNU www.acmicpc.net/problem/12757 12757번: 전설의 JBNU 첫 줄에는 초기 데이터의 개수인 \(N(1 \le N \le 100,000)\) 과 명령 횟수인 \(M(1 \le M \le 100,000)\), 가장 근접한 Key까지의 거리의 제한인 \(K(1 \le K \le 10,000)\)가 주어진다. 입력의 둘째 줄부터 N개의 줄에 www.acmicpc.net map과 이분탐색을 활용해서 조건에 맞게 푸는 문제이다. 8번의 시도 끝에 풀었다. 문제 해결 문제를 읽어보면 다음과 같은 조건이 있다. 1 Key Value : 해당 Key와 Value를 가진 데이터를 추가한다. Key가 이미 존재하는 입력은 주어지지 않는다. 2 Key Value : 해당 Key로 검색된 데이터를 Va.. 공감수 0 댓글수 0 2020. 9. 29.

문의안내

티스토리
로그인
고객센터

티스토리는 카카오에서 사랑을 담아 만듭니다.