개발 이야기/Problem Solving
[묘공단] 코딩테스트 스터디 2주차
[묘공단] 코딩테스트 스터디 2주차
2023.11.30이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 0장 ~ 4장 써머리입니다. 배열 개념 인덱스와 값을 일대일 대응해 관리하는 자료구조 인덱스만 알면 빠르게 탐색 가능 (Random access) 배열 선언 # 1차원 배열 vector = [0] * 6 # 2차원 배열 (e.g., 3 by 4 matrix) matrix = [[0] * 3 for _ in range(4)] 배열 차원 중첩 리스트 형태로 다차원 배열을 표현 가능 그러나 실제 메모리는 1차원 구조로 저장된다 또한 2차원 배열을 1차원 배열로 표현해서 풀이하는 문제도 꽤 자주 출제됨 matrix1 = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] matrix2 = [1, 2, 3, 4, 5, 6, 7, 8, 9] # 2행 ..
[묘공단] 코딩테스트 스터디 1주차
[묘공단] 코딩테스트 스터디 1주차
2023.11.20이직을 한 이후로 면접관으로 들어가기 전 문제 검토 때가 아니면 자료구조/알고리즘 공부를 따로 하지는 않았는데, 좋은 기회로 스터디를 진행할 수 있게 되어서 대학생 때로 돌아간 것처럼 바짝 열심히 해보려고 한다. 목표는 AtCoder 청록색 레이팅인데 그동안 머리가 많이 굳어서 정말 열심히 하지 않으면 쉽지는 않을 것 같다. 그래도 공개적으로 이렇게 적어야 바로 아래 단계까지라도 가능하지 않을까, 화이팅! 이 글은 골든래빗 코딩 테스트 합격자 되기 파이썬 편의 0장 ~ 4장 써머리입니다. 0장. 코딩 테스트를 준비하기 전에 타인의 풀이를 보면 사고의 폭을 넓힐 수 있다 더 나은 시간 복잡도 풀이, 또는 언어의 문법을 잘 활용한 간결한 코드 등 비단 코딩 테스트뿐만 아니라 우리는 다른 사람의 코드를 수없이..
C++11/14 관련 Problem solving tip
C++11/14 관련 Problem solving tip
2016.12.03https://www.acmicpc.net/blog/view/46 나중에 읽어봐야지
1076: 저항
1076: 저항
2015.11.05문제: https://www.acmicpc.net/problem/1076 문제에 주어진 조건을 그대로 구현하면 된다. 다만 예외처리가 필요한데 최종값은 32bit int 범위를 넘어갈 수 있는 것만 조심하면 된다.
1913: 달팽이
1913: 달팽이
2015.04.29문제: https://www.acmicpc.net/problem/1913N이 3일 때와 5일 때를 직접 그려보면 규칙성이 보인다.해결 방법은 여러가지가 있겠지만, 나는 ↑, →, ↓, ← 를 하나의 사이클로 보고 해결하였다.예를 들어 N = 5일 때처음 시작하는 행과 열의 index는 2, 2이며 (0 Based)첫 번째 사이클에서↑ 1칸, → 1칸, ↓ 2칸, ← 2칸두 번째 사이클에서↑ 3칸, → 3칸, ↓ 4칸, ← 4칸으로 움직이고 세 번째 사이클에서↑ 4칸으로 가면서 끝나는 것으로 알 수 있다. 이것을 조금 일반화 하면 달팽이 배열의 끝은 항상 ↑에서 종료됨을 확인할 수 있기 때문에↑ 반복문에서 달팽이 배열이 끝나는 지만 체크하면 된다.소스 코드를 참고하세요. 소스 코드12345678910111..
8741: 이진수 합
8741: 이진수 합
2015.04.01문제: https://www.acmicpc.net/problem/8741k를 1, 2, 3, 4로 올려가면서 직접 손으로 써보면 규칙성이 보인다.처음에 문제 접근은 수열의 합공식?을 이용해서 합을 구한 후 Java에서 이진법으로 변환 후 출력했더니 시간 초과가 났다.그래서 이번에는 k가 1, 2, 3, 4 증가함에 따라 이진수의 형태도 규칙이 있는 것을 보고그 규칙대로 출력했는데 Java에서는 여전히 시간 초과가 났다(아마도 내가 Java에서 제공하는 메소드에 익숙하지 않아서 그런 것 같음)같은 방법으로 C++로 다시 작성하여 Accept를 받았다.소스 코드를 참고하세요. 소스 코드12345678910#include #include int main() { int k = 0; scanf(" %d", &k)..
9094: 수학적 호기심
9094: 수학적 호기심
2015.03.31문제: https://www.acmicpc.net/problem/9094주어진 조건을 잘 읽고 구현하면 되는 문제다.정수인 쌍의 개수를 구하는 문제이므로 %(나머지) 연산자를 이용해서 0이 나오면 카운트를 증가하면서 세면 된다.입력이 최대 100이고 2중 루프로 충분히 시간 내에 풀 수 있다.수학적으로도 풀 수 있는지는 잘 모르겠다.소스 코드를 참고하세요. 소스 코드12345678910111213141516171819202122232425import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int numOfTestCases = s..
1978: 소수 찾기
1978: 소수 찾기
2015.03.30문제: https://www.acmicpc.net/problem/1978이 문제의 원래 의도는 입력이 1,000 이하의 자연수이므로 1부터 1,000까지의 숫자에 대해서 에라토스테네스의 체를 이용해서 소수만 남기고 입력으로 들어오는 숫자들이소수인지 아닌지 판별하는 것이 원래 목적인 것 같지만Java의 BigInteger 클래스에서 소수를 판별하는 Method를 제공하므로 그걸 이용해서 풀어보았다.중간의 isProbablePrime Method에 대한 설명은 다음 링크를 참고하세요.소스 코드를 참고하세요. 소스 코드1234567891011121314151617181920import java.math.BigInteger;import java.util.Scanner; public class Main { pub..
5586: JOI와 IOI
5586: JOI와 IOI
2015.03.29문제: https://www.acmicpc.net/problem/5586입력의 제한이 10,000자 이내의 문자열이므로 루프를 돌면서 substring이 "JOI"나 "IOI"인지 확인하는 방식으로 해결했다.다른 좋은 방법 혹은 더 깔끔한 코드(언어 차원에서 substring의 개수를 세는 메소드라던가...)가 있을 것 같지만우선은 Accept 되었으므로...소스 코드를 참고하세요. 소스 코드123456789101112131415161718192021222324import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String in..
5522: 카드 게임
5522: 카드 게임
2015.03.27문제: https://www.acmicpc.net/problem/5522너무 쉽다. 5개의 정수 입력을 다 더한 다음 출력하면 된다.이런 문제도 있다니 ㅡ_ㅡ소스 코드를 참고하세요. 소스 코드12345678910111213141516import java.util.Scanner; public class Main { public static void main(String[] args) { final int NUM_OF_GAMES = 5; Scanner scanner = new Scanner(System.in); int totalScore = 0; for (int i = 0; i
4134: 다음 소수
4134: 다음 소수
2015.03.27문제: https://www.acmicpc.net/problem/4134이 문제는 Java의 BigInteger 클래스에서 제공하는 메소드로 쉽게 해결 가능하다.C++로 작성하면 직접 소수를 구하는 로직을 작성해야 하지만 Java의 BigInteger에서는 해당 로직을 메소드로 제공합니다.다만 문제를 제대로 안 읽으면 틀리는데 입력값보다 크거나 '같은' 소수를 찾는 것이므로입력 값이 바로 소수라면 해당 값을 출력해야 합니다.특히 현재 값이 소수인지 아닌지 판단하는 메소드인 isProbablePrime의 파라미터값이 있는데해당 내용은 다음 링크를 참고하세요.소스 코드를 참고하세요. 소스 코드12345678910111213141516171819202122import java.math.BigInteger;im..
3447: 버그왕
3447: 버그왕
2015.03.27문제: https://www.acmicpc.net/problem/3447Java를 이용해서 새로운 문장이 들어오지 않을 때까지 문장 단위로 입력받고String의 replace method로 BUG를 재귀적으로 제거하면 원하는 정답이 나옵니다- 출력하는 소스 코드에는 BUG가 있으면 안된다. 즉, ABUBUGGB와 같은 경우는 AB가 되어야 한다는 것이 핵심소스 코드를 참고하세요. 소스 코드123456789101112131415161718192021222324import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); while (scan..