티스토리

승쨩개발공부

검색하기

블로그 홈

승쨩개발공부

enom01.tistory.com/m

개발공부 기록 및 끄적임

구독자: 1

방명록 방문하기

주요 글 목록

[BJ] 17478 - 재귀함수가 뭔가요? (재귀) 유명한 재귀 문제이다.1번예제에 첫번쨰 줄을보자 어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다. 재귀 함수는 자기 자신을 호출하는 함수라네 그러고 2 -> 1 -> 0 순으로 종료되며 라고 답변하였지. 를 출력한다. 아직은 쉽지만 Z문제같은 부분탐색같은경우도 정확히 식을 세우고 쪼개서 풀 줄 알아야추후에 풀을 DP,백트레킹이 수월하다. 공감수 0 댓글수 0 2025. 3. 8.
[BJ] 1074 - Z (재귀) 2^n * 2^n 인 2차원 배열에 r(행)과 c(열) 을 입력받고 몇 번쨰로 방문했는지 출력하는 문제이다. N = 0일떄 최소갯수는 2x2칸이니 총 4칸이다그럼 1번사각형 위치 2번사각형 위치 3번사각형위치 4번사각형 위치마다 각 값을 리턴받으면 되지않을까? 각 위치에 맞게 재귀식을 짜주면된다 만약 해당 문제가 어려울경우 재귀함수에대한 이해가 부족한거기떄문에 재귀를 기초부터 다시 공부하기 바란다. 국가문화제급 설명을 발견했는데 해당 영상으로 공부하면 좋을것 같다. https://youtu.be/R_UKR1BMPRo 공감수 0 댓글수 0 2025. 3. 8.
[BJ] 11729 - 하노이 탑 이동 순서 (재귀) 재귀를 안쓰다가 이걸 풀려니까 기억이 안났다 하노이탑의 규칙은 1,2,3번 기둥이 있고 N개의 원판들이 1번원판에 모두 꽃혀있다 이 N개의 원판을 3번 기둥에모두 꽃으면 되는데 큰 원판은 작은원판 위에 올 수 없다. 옮긴 횟수 K를 구하려면N개의 원반이 있으면 1번부터 N-1번 원반까지 모두 2번쨰 기둥에 들어가야한다.N번 원반이 3번기둥에 한번 이동하고 1 ~ N-1번 원반이 2번기둥에서 N번원반이 올려져있는3번기둥으로 이동해야하니 총 이동 횟수는 f(n) = 1 + 2f(n-1)이 된다 즉 (2^n) - 1 번 이동을 하게 된다. 즉N-1개의 원판을 기둥 1에서 기둥 2로 옮긴다N번 원판을 기둥 1에서 기둥 3으로 옮긴다N-1개의 원판을 기둥 2에서 기둥 3으로 옮긴다-> 원판이 n-1개일떄 옮길 수.. 공감수 0 댓글수 0 2025. 3. 6.
[BJ] 1629 - 곱샘 (재귀기초, 모듈러 성질, 귀납적사고) 0. 수학적 귀납법내가 재귀를 풀떄마다 절차지향적으로 항상 생각했는데, 이젠 수학적 귀납법으로 생각을 해야한다.도미노가있다 그러면 절차지향적 사고와 수학적 귀납법 사고를 생각해보자 1) 절차 지향적 사고1번 도미노가 쓰러지면 2번 도미노도 쓰러지고 2번 도미노가 쓰러지면 3번 도미노도 쓰러진다.1 -> 2 -> 3 -> 4 -> .... 이런식으로 모든 도미노가 쓰러진다 이건 절차지향적인 생각이다. 2) 수학적 귀납법 사고1번 도미노가 쓰러진다 K번 도미노가 쓰러지면 K + 1번 도미노도 쓰러진다.이것이 수학적 귀납법 사고이다. 1. 문제 설명A^B % C (A^B mod C) 를 구하는건데 입력 조건을 보면 A,B,C모두 최대범위가 int의 최대 범위이다즉 약 21억^21억을 한 변수에 담을 수 있을까.. 공감수 0 댓글수 0 2025. 3. 6.
[BJ] 5427 - 불 (BFS Queue초기화) Queue는 Vector나 다른 STL같은 clear함수가 없다. 따라서 Pop으로 다 뺴주거나 재정의를 해줘야한다. 공감수 0 댓글수 0 2025. 3. 5.
[BJ] 7569 - 토마토 (BFS 3차원배열) 기본 원리는 전에 올렸던 토마토 문제에서 Z축이 추가된 문제이다. 그래서 따로 문제 설명은 하지않고 사용한 함수 설명을 하겠다.pair가 2가지 변수를 대입할 수 있었다면 tuple은 3가지 변수를 대입할 수 있다.tuple은 pair함수처럼 first,second가 없다.따라서 tie 함수를 이용해 각자 값을 새로 대입해야한다. tuple헤더를 추가해주자 공감수 0 댓글수 0 2025. 3. 4.
[BG] 7562 - 나이트의 이동 (BFS 상하좌우가 아닌 이동) 나이트는 (2,1),(1,2),(-1,2)(-2,1), (-2,-1),(-1,-2)(1,-2)(2,-1) 을 이동할 수 있다보드판을 직접 입력할 필요는 없고 Check에 이동거리를 q.front에 + 1씩 저장해주면 된다. 첫쨰줄은 테스트케이스 갯수둘쨰줄은 체스판의 한변의 길이 n(정사각형)셋째줄에는 시작 인덱스넷쨰줄에는 목적지 인덱스를 입력 받으면 된다. 어떻게 풀어야하는지 그림을 한번 보자 그냥 전에 풀었던 BFS처럼 시작지점에서 폰 이동범위 마다 거리를 기록해주면 된다. 공감수 0 댓글수 0 2025. 3. 4.
[BJ] 10026 - 적록색약 (BFS 함수쪼개기) 각 구역마다 돌면서 R갯수 G갯수 B갯수를 구해서 갯수를구하고그 다음 RG갯수 B갯수를 구하면 된다모든 구역을 돌고 같은 문자만 BFS를 돌고 BFS를 나오게되면 카운트를 증가해주면된다. 이번엔 열 갯수만 입력으로 주어진다. 공감수 0 댓글수 0 2025. 3. 3.
[BJ] 1012 - 유기농 배추 (BFS) 이번 문제는 t와 2차원 인덱스를 직접 삽입해야해서 아주 조금 변형이 있었다.n,m 위치를 잘 생각하고 풀어야 했었다. 예제2번 그림이런식으로 2개의 지렁이가 나오게 된다.t도 있으니 BFS가 다 끝나고 지렁이를 출력하면 보드판과 체크도 초기화를 해줘야한다.그리고 t가 있을경우 출력하고 열바꿈을 해주자. 이거 안해서 계속 틀렸었다..(\n) 공감수 0 댓글수 0 2025. 3. 2.
[BJ] 1697 - 숨바꼭질 (BFS 1차원) 자 수빈이와 동생은 0 수빈이는 앞과 뒤 로 이동할수있고 현재위치 * 2 의 위치로 이동할수있다. 이걸 생각해보면 배열이고 이동거리를 저장해야하니 BFS로 풀 수 있겠다 라는 생각이 들것이다. 일단 배열을 모두 -1로 초기화해주고 수빈이의 초기위치를 0으로 만든다 그리고 Queue에 집어넣는다배열을 모두 -1로 초기화 했으니 수빈이의 거리가 -1이 아니라 양수로 바뀔떄까지 반복을 돌리면 되겠다. 그림으로 한번 거리를 봐보자. .5번은 수빈이의 초기 위치고 17번은 동생의 위치이다.5 -> 10 -> 9 -> 18 -> 17 로 간다면 4초가 걸리게 될것이다. 공감수 1 댓글수 0 2025. 3. 1.
[BJ] 4179 - 불! (BFS 시작점이 두 종류) 이번엔 불과 지훈이가 동시에 있다 지훈이가 불에 타기전에 탈출을 할 수 있는지 체크를 해야한다. 현재 보기 TK가 4,4밖에 없으니 5,5로 예를들어 설명을 해보겠다.열과 행이 5,5인 Board가 다음과 같이 입력이 주어졌다고 치겠다. 저번에 토마토 문제처럼 전부 거리를 -1로 만들고지훈이 위치를 거리 0으로 만들고 시작해보자 지훈이의 이동 거리의 경로가 불번짐에 이동 거리보다 적기떄문에 무사히 탈출이 가능하다. 그럼 이렇게 그려보면 유추가 가능하다큐를 두개(지훈,불),거리측정을 두개(지훈,불) DFS를 두번(지훈,불) 돌리고 지훈이 DFS에서 불번짐 거리를 재면 되겟구나?범위를 벗어나면 탈출이고 큐가 빌떄까지 범위를 못 벗어나면 탈출을 못 하는구나? 여기서 중요한 포인트는 Distance가 벽도 -.. 공감수 0 댓글수 0 2025. 3. 1.
[BJ] 7576 - 토마토 (BFS 시작점이 여러개) 일단 상하좌우로 퍼져나가니 BFS로 풀수있다는걸 눈치를 챌 수 있다.하지만 여지껏 풀었던 BFS문제와 다르게 시작점이 여러개일수있다 TK 3번을 보자. 이렇게 input이 들어오게 되는데.-1이 있는곳을 제외하고 퍼지면서 1씩 증가해야하니이런식으로 되어야 할것이다. 근데 출력에서 0 = 처음부터 모두 토마토가 익어있는거고, -1은 모두 익지 못하는 상황이고,나머지는 토마토가 익을 수 있는 일 수를 출력하는 것 이다. 그러면 여기서 input을 보면 생각을 해 볼 수 있다.그러면 상하좌우로 갈 수 있는 부분만 -1로 미리 표시를 해놓으면 되지 않을까?이런식으로 말이다.-1만 움직일 수 있도록 해놓고 만약 -1일이 모두 상하좌우로 이어져 있지 않아서 BFS를 하고나서도 -1이 남아있다면?모두 익지 못하는 상.. 공감수 0 댓글수 0 2025. 2. 27.
[MS] 문자입력,문자열입력 개념 코딩테스트를 볼떄 내가 문제를 풀다가 멈칫한 개념인데 위 1926번 문제 그림 같이 입력이 띄어서 입력을 받으면 한글자씩 입력받으라는뜻 즉 배열(문자)로 입력받으라는 뜻이고. 위 2178 문제 미로 탐색 처럼 입력이 붙어서 입력을 받으면 문자열로 입력을 받으라는 뜻이다. String 으로 입력을 받아도 문자열이기에 위 그림처럼 입력을 받으면 2차원 배열로 등록이 된다. 알아보기 쉽게 board[n-1][m-1]은 9로 저장한다. 결과값 공감수 0 댓글수 0 2025. 2. 27.
[BJ] 2178 - 미로 탐색 (BFS 거리탐색) 0,0에서 시작해서 n-1,m-1까지 최단거리를 구하는 방법이다BFS는 전에 문제 그림에서 설명한것처럼 구하면 되는데 일단 그림을 먼저 그려보자.인접한곳에 상하좌우 카운트를 늘려주면 되는데 처음엔 배열로 문제를 풀어서 오답이 나왔다 입력을 잘 보니각각의 수들은 붙어서 입력으로 주어진다라고 써져있었다 문제를 풀다보니 저걸 못봐서 오답이 나왔다.배열에서 문자열로 바꿔주니 정답이 나왔다. 틀린 배열 코드 정답 문자열 코드문자열이니 조건도 != 1 이아니라 != '1' 로 해줘야한다. 공감수 0 댓글수 0 2025. 2. 27.
[BJ] 1926 - 그림 (BFS) 문제를 쪼개서 생각해보자 항상 문제를 쪼개서 생각하는 습관을 들이자.자 열과 행이 최대 1 그리고 그림의 개수, 최대 그림 넓이를 출력하는 문제이다.1. 열과 행 입력 및 열과 행에 크기에 맞는 입력이 필요함. = 2중for문그리고 시작점이 없으니 1이 적힌 인덱스를 찾아야한다 또 열과 행을 돌아야함.2. 2중for문으로 1이 적인곳을 찾아냄 대신 0이거나 이미 방문했다면 건너뛰면됨찾아냈다면 그쪽은 1이 있는곳이므로 즉 그림의 개수의 count를 늘리면됨3. 1을 찾았다면 방문했다고 해주고 q에 삽입함.4. q의 front를 다른 변수에 넣어주고 q의값을 뻄 그리고 q의 x값 y값을 동서남북으로 비교하며 동서남북에 1이 있다면 방문했다고 넣어주고 q의 삽입함 이 과정에서 인접한곳이 없어서 끝나게된다면.. 공감수 0 댓글수 0 2025. 2. 24.
[BJ] 4949 - 균형잡힌 세상 나중에 들어온 값이 열린 괄호인지 체크해서 지우면 문제를 풀수있다LIFO구조로 풀어야하니 스택을 이용하면 된다.GetLine과 스택을 이용해서 문제를 풀면 된다. 공감수 0 댓글수 0 2025. 2. 22.
[BJ] 1021 - 회전하는 큐 N개의 크기를 가진 deque에서 M개의 수를 뽑아내는 문제이다1번,2번,3번의 연산을 모두 사용해서 2번,3번 연산을 가장 적은 연산으로 모든 수를 뽑아내야한다.(1번연산은 제외) 예제 2번으로 설명을하겠다1 ~ 10 을 가진 큐가 있다 여기서 3개의 숫자를뽑아야하는데 뽑아야 하는 수 는 2,9,5이다 2값을 뽑아 내려면 2번연산 -> 1번연산으로 가장 빠르게 2를 없앨수있다. 5값을 뽑아 내려면 3번연산 -> 3번연산 -> 3번연산 -> 1번연산 으로 9을 맨 앞으로 보낸후 없앤다. 문제는 이런식으로 풀면 된다. 문제 이해가 안갈떄는 하나씩 그려보면서 풀어보고 조건을 생각해보자. 공감수 0 댓글수 0 2025. 2. 21.
[BJ] 10866 - 덱(Deque) 이것도 상당히 쉽다 deque를 이용해 push를뺴고 출력하라는것만 출력하면된다. 공감수 0 댓글수 0 2025. 2. 19.
[BJ] 2164 - 카드2 이것도 아주 쉽다 queue에 1~n까지 삽입후 첫번쨰 원소를 지우고 첫번쨰원소를 뒤로보내고 첫번쨰원소를 삭제하면 된다. 공감수 0 댓글수 0 2025. 2. 19.
[BJ] 15845 - 큐 이것도 굉장히 쉽다 push를뺴고 나머지를 다 출력하면 된다. 공감수 0 댓글수 0 2025. 2. 19.
[BJ] 2493 - 탑 (스택,시간부족) ★ 내가 국어능력이 딸리는건지 문제 이해만 30분이 넘게 걸린것같다. 탑엔 몇번쨰 탑인지, 높이가 얼마인지 있어야하는데 왼쪽으로 레이저를 쏴서 충돌한 첫번쨰 인덱스를 출력하면 된다.그림으로 설명하자면이런 그림이 나온다. 탑의 인덱스는 500,000까지 높이는 100,000,000까지 있어서 속도를 빠르게 풀어야할 것 같았다.제한시간 1.5초삽입 삭제가 O(1)인 스택을 활용했다.하지만 자꾸 시간 초과가뜨는데..cin.tie(0)과 ios_base를 넣어주니 통과가됬다..백준은 시간이 부족하다면 저것들과 endl사용을 지양해야할것같다.. 공감수 0 댓글수 0 2025. 2. 18.
[BJ] 10828 - 스택 굉장히 easy한 문제다 스택의 특성을 그대로 이용하면된다.STL로 사용해도 되지만 내가 구현한 스택으로 해도 무관하다.하지만 empty()조건을 잘 이용해야한다. 공감수 0 댓글수 0 2025. 2. 18.
[BJ] 1158 - 요세푸스 문제 푸는방법은 여러가지가있다. 공식은 그림을 그려보면 쉬운데입력예제와 같을경우 저 순서대로 출력이 되면 된다. FIFO구조인 큐를 사용하면 간단하게 처리가 가능하다K - 1번을 출력후 삭제해주면된다. 공감수 0 댓글수 0 2025. 2. 14.
[BJ] 1406 - 에디터 (리스트) 임의의 위치에 삽입/삭제를 해야한다.배열형 자료구조는 원소 접근은 O(1)이지만 임의의 원소 삽입 삭제가 O(N)이다노드형 자료구조는 원소 접근은 O(N)이지만 원소의 삽입 삭제는 O(1)이다시간제한이 0.3초이니 노드형 자료구조를 사용해야겠다. 공감수 0 댓글수 0 2025. 2. 14.
[BJ] 2577 - 숫자의 개수 두가지 방법이있다.String으로 a*b*c를 각 인덱스마다 숫자 하나씩 자릿수를 받아오는 것.Array로 %10 해서 값을받아오고 / 10해서 자릿수를 줄이면서 자릿수를 받아오는 것. String 이 1,7,0,3,7,3,0,0 일때 Arr가 3,1,0,2,0,0,0,2,0,0 이 되어야 하는데.숫자만들어가니 아스키코드 값인 '0' = 48을 뺴개되면 현재 String[0] = 1('1' = 49)이니까49 - 48을하고 해당 1번 인덱스를 증가시키면 될것같다. 공감수 0 댓글수 0 2025. 2. 12.
[BJ] 10811 바구니 뒤집기 (for문에 조건을 생각) 1. 문제를 글로 이해를 못하겠으면 그림으로 그려보자.2. for문에 조건을 하나만 생각하지말자. 역순으로 swap하라는것까진 알겠는데 범위로 Swap을 하는것에서 많은 고민이 있었다 저 예재대로 Swap을 한다면1,2,3,4,5 일때2,1,3,4,52,1,4,3,53,4,1,2,53,4,1,2,5가 되어야한다 뇌가 굳어서 한번에 for문에 증감과 감소를 동시에 쓸생각을 못하고있었다..홀수범위로 swap한다면 어차피 뒤집이도 가운데 숫자의 위치는 변하지 않으니 i증감 j감소 해주면 된다.공부용으로 swap을 계속 직접 구현하고있는데 swap함수를 사용해도 된다. 공감수 0 댓글수 0 2025. 2. 7.
[BJ] 2523번 오븐시계 (나머지 연산자 활용) Coding Test 게시판은 내가 놓치기 쉬운 개념들로만 작성할것이다. 조건은 0 CookTime은 분단위로 0 Hour은 23이 넘어가면 0이되어야하고 Min은 59가 넘어가면 0이 되어야 한다. 하나의 방법만 생각하지말고 여러가지 방법을 생각해야하고 기초지만 놓치기 쉬운 개념인 나머지 연산자를 활용하였다. 시간,분,조리시간을 모두 분으로 바꾸어서 나눗샘,나머지 연산자를 활용해 간단하게 코드가 끝난다.공학을 배운다면 놓치기 쉬운 개념인 나머지 연산자의 활용법을 염두해야한다고 느꼈다. 공감수 0 댓글수 0 2025. 2. 7.
[DS] 그래프(Graph) / 트리(Tree) 그래프, 트리노드의 관계를 저장하는 자료구조이다.일반적으로 탐색을 하기 위해선 반복문같은 프로그래밍 문법이 아니라 (for, while..)DFS-깊이탐색,BFS-너비탐색 알고리즘을 사용해야한다 트리 (Tree)트리는 노드가 나무 가지처럼 연결괴어 있는 비선형 자료구조이다.마치 나무를 뒤집어 놓은 모습과 유사하다.트리 내 또 다른 하위 트리가 있고, 그 안에 또 다른 하위 트리가 있는 재귀적인 구조를 가진다.컴퓨터의 디렉토리 구조가 트리 구조이다.보통 최상단 노드를 RootNode(뿌리 노드), 나머지 노드를 LeafNode(잎 노드) 라고 한다. 그래프 (Graph)그래프는 노드와 노드를 연결하는 간선을 모아놓은 자료구조이다.트리와 많이 비교가 되는데 트리 역시 그래프의 형태이나, 그래프는 방향이.. 공감수 0 댓글수 0 2025. 1. 5.
[DS] 스택(Stack) / 큐(Queue) 스택(Stack)Stack이란 자료구조는 규칙이 다음과 같다.1. 저장 : 항상 위에만 저장한다.2. 읽기 : 항상 제일 위에 있는 데이터만 읽을 수 있다.3. 삭제 : 항상 제일 위에 있는 데이터만 삭제 할 수 있다. STACK은 위 규칙을 가진 전용 자료구조 이고 배열을 이용해서 구현해도 좋고또는 LIST 를 이용해서 구현해도 좋다. 구현 방벙은 개발자의 자유다. 데이터 방식 : LIFO(Last In First Out) 후입 선출마지막에 들어온 데이터가 먼저 나간다. 게임에서의 활용 : 역순으로 객체나 이벤트를 처리해야 할 떄 유용하다.UI같은거 유용함. 리스트 기반 스택 코드첫번쨰 Push의 Next는 m_Head = null이다 그림설명 큐(Queue)스택과 비슷한 자료구조이며 현업에서 굉.. 공감수 0 댓글수 0 2024. 12. 30.
[DS] STL List push_back, push_front 구현 list를 만들어보자구현하는 방식 구현코드 공감수 0 댓글수 0 2024. 12. 29.

문의안내

티스토리
로그인
고객센터

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