티스토리

원
검색하기

블로그 홈

원

wonsjung.tistory.com/m

JWonK 님의 블로그입니다.

구독자
4
방명록 방문하기
728x90
반응형

주요 글 목록

  • [C/C++] 백준 - 15684번 : 사다리 조작 및 4-1학기 코딩 테스트 복기 약 2년 전에 풀었던 문제를 다시 풀어보았다. 기억보다는 기록에 의존하라는 말이 이래서 있는건가. 풀 때는 몰랐는데 당시에 풀었던 게시글을 보니 2일이나 걸려 해결했던 문제였다. 이번 4학년 1학기 때 정확히 기억은 안나지만 대략 5-6회 코딩테스트를 응시했다. 프로그래머스 ,유니콘 기업, 우테캠 등등 적지 않은 코딩테스트를 응시했다. 난 2023년 2월까지만 코딩테스트를 공부하고 그 뒤로는 한 번도 문제를 풀지 않았고 그 전까지 공부했던 내 기억에만 의존한 채 할 수 있을거라는 근자감으로 코딩테스트를 응시했었다. 결과는 당연히 처참했다. C++ 문법도 헷갈려서 많은 시간을 뺏기고 구현 문제 외에는 다른 알고리즘을 해결할 수 없었다. 약 2년 간 양치기로 해결했던 문제들은 모두 나 자신도 속이는 겉핥기식.. 공감수 0 댓글수 0 2023. 7. 2.
  • [C/C++] 순열 / 조합 구현하기 c언어 알고리즘 문제를 풀면서 재귀함수 파트를 풀다보면 피할 수 없는 파트이다. 지금까지는 재귀 학습 자체를 안하다가 요즘 하게 되었는데 이제는 피할 수 없는 숙명이라고 받아들이고 이왕 공부하는 거 다시는 찾아보지 않도록 내 블로그에 내가 정리해보려고 한다. 1. 순열이란, - 순열이란 서로 다른 n개 중에서 r개를 택하여 배열하는 경우를 말한다. 기호로는 nPr로 나타낼 수 있다. - 순열의 예) 1) 1, 2, 3, 4, 5가 적혀 있는 숫자 카드가 있다, 이를 이용하여 세자리 수를 만들 수 있는 방법은 몇가지 인가? -> 이 문제를 풀 때 어떻게 할 것인가. 세자리수면 백의 자리, 십의 자리, 일의 자리가 존재하고 각 자리에 올 수 있는 카드의 개수를 곱해줄 것이다. 즉, 백의 자리에는 카드의 개수.. 공감수 3 댓글수 4 2022. 9. 5.
  • [C/C++] 백준 - 2239번 : 스도쿠 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 문제 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자. 위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(.. 공감수 0 댓글수 0 2022. 3. 14.
  • [C/C++] 백준 - 10597번 : 순열 장난 https://www.acmicpc.net/problem/10597 10597번: 순열장난 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순 www.acmicpc.net 문제 kriii는 1부터 N까지의 수로 이루어진 순열을 파일로 저장해 놓았다. 모든 수는 10진수로 이루어져 있고, 모두 공백으로 분리되어 있다. 그런데 sujin이 그 파일의 모든 공백을 지워버렸다! kriii가 순열을 복구하도록 도와주자. 입력 첫 줄에 공백이 사라진 kriii의 수열이 주어진다. kriii의 순열은 최소 1개 최대 50개의 수로 이루어져 있다. 놓쳤던 부분.. 공감수 1 댓글수 0 2021. 12. 31.
  • [C/C++] 백준 - 16938번 : 캠프 준비 https://www.acmicpc.net/problem/16938 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net 이 문제도 백트래킹으로 완전 탐색을 하는 문제이다. 개인적으로 전에 풀었던 문제가 더 까다로웠던 것 같은데 이 문제가 난이도는 더 높게 등록되어있다. 이 문제는 조건이 구간으로 나누어져 있어서 정렬을 먼저 한 후 몇 개를 최대로 뽑을 수 있는지 먼저 구해주었다. 만약 입력되는 난이도의 개수가 15개인데, 사실상 조건에 만족하는 개수는 2개 뿐이라면 나머지는 필요없는 연산이기 때문이다. 그래서 가장 먼저 범위에 만족하는 최대 개수를 구해주었다. 그리고 그 후는 똑같이 백트래킹 -> 완전탐색으로 구한 후 최종적으.. 공감수 0 댓글수 0 2021. 9. 20.
  • [C/C++] 백준 - 18290번 : NM과 K(1) https://www.acmicpc.net/problem/18290 18290번: NM과 K (1) 크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접 www.acmicpc.net N과 M을 응용한 문제로 2차원 배열에서 사용해야한다. 인접한 구간끼리는 합을 구하지 않으므로 방문 처리 표시를 통해 인접한 칸을 더하는 것을 방지한다. 그리고 백트래킹을 통해 완전탐색을 해야하므로 한 번 확인하고 나면 방문처리를 원래대로 돌려주어야 하는데 나는 스택으로 몇 개의 인접한 칸을 방문 처리 표시했는지 기억해두고 다시 되돌려야할 경우 기억했던 개수만큼 다시 스택에서 꺼내 방문.. 공감수 0 댓글수 0 2021. 9. 20.
  • [C/C++] 백준 - 15658번 : 연산자 끼워넣기 (2) https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net 연산자는 +, -, *, / 총 4개가 가능하고 그 개수는 입력으로 주어진다. 수의 개수의 최대 크기가 11로 작고 특별한 조건으로 값을 구하는 게 아니므로 완전탐색을 이용해서 문제를 해결할 수 있다. 나는 순열을 이용해서 N-1개의 기호를 뽑아 값을 계산한 후 최대값과 최소값을 갱신하는 방법으로 문제를 해결하였다. 처음에는 조합처럼 해결.. 공감수 0 댓글수 0 2021. 9. 6.
  • [C/C++] 백준 - 2309번 : 일곱 난쟁이 https://www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 이 문제는 9명 중 7명을 뽑았을 때, 그 7명 키의 합이 100인 경우 정렬한 후 출력해주면 끝나는 문제이다. n명 중 m명을 뽑는 알고리즘을 설계해서 해결해주었다. bool visited[10]; int od[10]; int nanj[10]; #include #include #include #include #include #include #include #include #define ll long lo.. 공감수 0 댓글수 0 2021. 9. 6.
  • [C/C++] 백준 - 10971번 : 외판원 순회2 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자. 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다... 공감수 0 댓글수 0 2021. 9. 6.
  • [C/C++] 백준 - 10819번 (차이를 최대로) https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 문제 N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오. |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]| 입력 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보.. 공감수 0 댓글수 0 2021. 7. 3.
  • [C/C++] 백준 - 17829번 (222 - 폴링) https://www.acmicpc.net/problem/17829 17829번: 222-풀링 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 22 www.acmicpc.net 문제 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다. 다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다 행렬을 .. 공감수 0 댓글수 0 2021. 6. 20.
  • [C언어 / 백준 - 1941번] 소문난 칠공주 (백트래킹 -> DFS/BFS) https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 문제 총 25명의 여학생들로 이루어진 여학생반은 5*5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작했다. 곧 모든 여학생이 ‘이다솜파’와 ‘임도연파’의 두 파로 갈라지게 되었으며, 얼마 지나지 않아 ‘임도연파’가 세력을 확장시키며 ‘이다솜파’를 위협하기 시작했다. 위기의식을 느낀 ‘이다솜파’의 학생들은 과감히.. 공감수 0 댓글수 0 2021. 5. 28.
  • [C언어 / 백준 - 1759번] 암호 만들기 (백트래킹) https://www.acmicpc.net/problem/1759 문제 바로 어제 최백준 조교가 방 열쇠를 주머니에 넣은 채 깜빡하고 서울로 가 버리는 황당한 상황에 직면한 조교들은, 702호에 새로운 보안 시스템을 설치하기로 하였다. 이 보안 시스템은 열쇠가 아닌 암호로 동작하게 되어 있는 시스템이다. 암호는 서로 다른 L개의 알파벳 소문자들로 구성되며 최소 한 개의 모음(a, e, i, o, u)과 최소 두 개의 자음으로 구성되어 있다고 알려져 있다. 또한 정렬된 문자열을 선호하는 조교들의 성향으로 미루어 보아 암호를 이루는 알파벳이 암호에서 증가하는 순서로 배열되었을 것이라고 추측된다. 즉, abc는 가능성이 있는 암호이지만 bac는 그렇지 않다. 새 보안 시스템에서 조교들이 암호로 사용했을 법한 .. 공감수 0 댓글수 0 2021. 5. 27.
  • [C언어 / 백준 - 14889번] 스타트와 링크 (백트래킹) https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 문제 오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속.. 공감수 0 댓글수 0 2021. 5. 25.
  • [C언어 / 백준 - 10870번] 피보나치 수 5 (재귀) https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 재귀함수를 통해 피보나치 수를 구현하는 문제이다. #include #include #include #include #include #include using namespace std; int N; int fibo[20 + 1]; int Fibo(int x) { if (x == N) { return fibo[x-1]+fibo[x-2]; } fibo[x] = f.. 공감수 0 댓글수 0 2021. 5. 22.
  • [C언어 / 백준 - 1914번] 하노이 탑 (재귀) www.acmicpc.net/problem/1914 1914번: 하노이 탑 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다. 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟.. 공감수 0 댓글수 0 2021. 5. 12.
  • [C언어 / 백준 - 6603번] 로또 (재귀함수 - 조합) www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 6)개의 수를 골라 집합 S를 만든 다음 그 수만 가지고 번호를 선택하는 것이다. 예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 수를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,.. 공감수 0 댓글수 0 2021. 5. 10.
    728x90
    반응형
    문의안내
    • 티스토리
    • 로그인
    • 고객센터

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

    © Kakao Corp.